n_factor_pollard_brent_single, n_factor_pollard_brent
Synopsis
#include <flint/ulong_extras.h>int n_factor_pollard_brent_single(ulong * factor, ulong n, ulong ai, ulong xi, ulong max_iters)sourceint n_factor_pollard_brent(ulong * factor, flint_rand_t state, ulong n_in, ulong max_tries, ulong max_iters)sourcePollard's rho method [Pol1975] with Brent's cycle detection [Bre1980], for composite n. Return 1 and set *factor to a nontrivial (not necessarily prime) factor on success, otherwise 0. The first function uses the polynomial x^2 + a_i and starting value x_i; the second tries up to max_tries random choices.
References#
- [Pol1975] J. M. Pollard, "A Monte Carlo method for factorization", BIT 15 (1975), 331–334
- [Bre1980] R. P. Brent, "An improved Monte Carlo factorization algorithm", BIT 20 (1980), 176–184
Cite this page
The FLINT team, “n_factor_pollard_brent_single, n_factor_pollard_brent (ulong_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/ulong_extras/n_factor_pollard_brent_single.html (generated 2026-10-20).
@misc{flint-doc-ulong-extras-n-factor-pollard-brent-single,
author = {{The FLINT team}},
title = {{n\_factor\_pollard\_brent\_single, n\_factor\_pollard\_brent (ulong\_extras.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/ulong_extras/n_factor_pollard_brent_single.html},
note = {Generated 2026-10-20}
}