TOPICS
Search

Pollard rho Factorization Method


A prime factorization algorithm also known as Pollard Monte Carlo factorization method. There are two aspects to the Pollard rho factorization method. The first is the idea of iterating a formula until it falls into a cycle. Let n=pq, where n is the number to be factored and p and q are its unknown prime factors. Iterating the formula

 x_(n+1)=x_n^2+a (mod n),
(1)

or almost any polynomial formula (an exception being x_n^2-2) for any initial value x_0 will produce a sequence of number that eventually fall into a cycle. The expected time until the x_ns become cyclic and the expected length of the cycle are both proportional to sqrt(n).

However, since n=pq with p and q relatively prime, the Chinese remainder theorem guarantees that each value of x (mod n) corresponds uniquely to the pair of values (x (mod p)), x (mod q)). Furthermore, the sequence of x_ns follows exactly the same formula modulo p and q, i.e.,

x_(n+1)=[x_n (mod p)]^2+a (mod p)
(2)
x_(n+1)=[x_n (mod q)]^2+a (mod q).
(3)

Therefore, the sequence (mod p) will fall into a much shorter cycle of length on the order of sqrt(p). It can be directly verified that two values x_1 and x_2 have the same value (mod p), by computing

 GCD(|x_2-x_1|,n),
(4)

which is equal to p.

The second part of Pollard's method concerns detection of the fact that a sequence has become periodic. Pollard's suggestion was to use the idea attributed to Floyd of comparing x_i to x_(2i) for all i. A different method is used in Brent's factorization method.

Under worst conditions, the Pollard rho algorithm can be very slow.


See also

Brent's 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.Brent, R. P. "Some Integer Factorization Algorithms Using Elliptic Curves." Austral. Comp. Sci. Comm. 8, 149-163, 1986.Bressoud, D. M. Factorization and Primality Testing. New York: Springer-Verlag, pp. 61-67, 1989.Eldershaw, C. and Brent, R. P. "Factorization of Large Integers on Some Vector and Parallel Computers."Montgomery, P. L. "Speeding the Pollard and Elliptic Curve Methods of Factorization." Math. Comput. 48, 243-264, 1987.Pollard, J. M. "A Monte Carlo Method for Factorization." Nordisk Tidskrift for Informationsbehandlung (BIT) 15, 331-334, 1975.Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 83 and 102-103, 1991.

Referenced on Wolfram|Alpha

Pollard rho Factorization Method

Cite this as:

Weisstein, Eric W. "Pollard rho Factorization Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PollardRhoFactorizationMethod.html

Subject classifications