TOPICS
Search

Brent's Factorization Method


The second part of Pollard rho factorization method concerns detection of the fact that a sequence has become periodic. Pollard's original suggestion was to use the idea attributed to Floyd of comparing x_i to x_(2i) for all i. Brent's improvement to Pollard's method concerns how to detect periodicity, and replaces Floyd's method with the following algorithm. Keep only one running copy of x_i. If i is a power of a base b, let y=x_i, and at each step, compare the current value x_i with the saved value y. In the factorization case, instead of comparing x_i with y, compute

 GCD(|x_i-y|,n).

More generally, Brent (1980) considered using any base b for saving values instead of b=2. However, he found b=2 to be very close to optimal.


See also

Brent's Method, Pollard rho Factorization Method, Prime Factorization Algorithms

Explore with Wolfram|Alpha

References

Brent, R. "An Improved Monte Carlo Factorization Algorithm." Nordisk Tidskrift for Informationsbehandlung (BIT) 20, 176-184, 1980.

Referenced on Wolfram|Alpha

Brent's Factorization Method

Cite this as:

Weisstein, Eric W. "Brent's Factorization Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BrentsFactorizationMethod.html

Subject classifications