Pollard Rho Factorization Method
A Prime Factorization Algorithmalso known as Pollard Monte Carlo Factorization Method. Let 
, then compute
If GCD
, then 
is Composite and its factors are found. In modified form, it becomesBrent'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.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.
- Problem
- Procedure
- Proclus' Axiom
- Procrustian Stretch
- Product
- Product Formula
- Product-Moment Coefficient of Correlation
- Product Neighborhood
- Product Rule
- Product Space
- Program
- Projection
- Projection Operator
- Projective Collineation
- Projective General Linear Group
- Projective General Orthogonal Group
- Projective General Unitary Group
- Projective Geometry
- Projective Plane
- Projective Plane PK2
- Projective Space
- Projective Special Linear Group
- Projective Special Orthogonal Group
- Projective Special Unitary Group
- Projective Symplectic Group