FLINT3.7.0-dev
/

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)source
int n_factor_pollard_brent(ulong * factor, flint_rand_t state, ulong n_in, ulong max_tries, ulong max_iters)source

Pollard's rho method [Pol1975] with Brent's cycle detection [Bre1980], for composite nn. Return 1 and set *factor to a nontrivial (not necessarily prime) factor on success, otherwise 0. The first function uses the polynomial x2+aix^2 + a_i and starting value xix_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-11-02).