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.
- Syracuse Problem
- System of Differential Equations
- System of Equations
- Syzygies Problem
- Syzygy
- Szilassi Polyhedron
- Szpiro's Conjecture
- Sárközy's Theorem
- T2-Separation Axiom
- Tableau
- Tabu Search
- Tacnode
- Tacpoint
- Tactix
- Tail Probability
- Tait Coloring
- Tait Cycle
- Tait Flyping Conjecture
- Tait's Hamiltonian Graph Conjecture
- Tait's Knot Conjectures
- Takagi Fractal Curve
- Take-Away Game
- Takeuchi Function
- TAK Function
- Talbot's Curve