fmpz_factor_pollard_brent
#include <flint/fmpz_factor.h>int fmpz_factor_pollard_brent(fmpz_t factor, flint_rand_t state, fmpz_t n, ulong max_tries, ulong max_iters)sourceLooks for a factor of the composite odd n by Pollard's rho method with Brent's cycle detection [Pol1975; Bre1980], using up to max_tries random polynomials x^2 + a and starting points, each for about max_iters iterations. If a nontrivial factor is found, sets factor to it and returns its number of limbs; otherwise returns 0. The factor need not be prime. For even n it returns 1 and the factor 2. Single-word n are passed to n_factor_pollard_brent. The expected number of iterations to find a prime factor p is O(\sqrt p).
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
The FLINT team, “fmpz_factor_pollard_brent (fmpz_factor.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_factor/fmpz_factor_pollard_brent.html (generated 2026-10-20).
@misc{flint-doc-fmpz-factor-fmpz-factor-pollard-brent,
author = {{The FLINT team}},
title = {{fmpz\_factor\_pollard\_brent (fmpz\_factor.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fmpz_factor/fmpz_factor_pollard_brent.html},
note = {Generated 2026-10-20}
}