## Pollard Rho Factorization Method

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

If GCD , then 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 (, however, cannot). Under worst conditions, the Algorithm can be very slow.

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.