Pollard Rho Factorization Method

A Prime Factorization Algorithm also known as Pollard Monte Carlo Factorization Method. Let $x_0=2$, then compute

$$x_{i+1}={x_i}^2-x_i+1 {\rm\ (mod\ } n).$$

If GCD $(x_{2i}-x_i,n)>1$, then $n$ is Composite and its factors are found. In modified form, it becomes Brent's Factorization Method. In practice, almost any unfactorable Polynomial can be used for the iteration ($x^2-2$, however, cannot). Under worst conditions, the Algorithm can be very slow.

See also Brent's Factorization Method, Prime Factorization Algorithms

References

Brent, R. P. ``Some Integer Factorization Algorithms Using Elliptic Curves.'' Austral. Comp. Sci. Comm. 8, 149-163, 1986.

Bressoud, D. M. Factorization and Prime 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.'' ftp://nimbus.anu.edu.au/pub/Brent/rpb156tr.ps.gz.

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.