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.
- Brahmagupta Identity
- Brahmagupta Matrix
- Brahmagupta Polynomial
- Brahmagupta's Formula
- Brahmagupta's Problem
- Braid
- Braid Group
- Braid Index
- Braid Word
- Braikenridge-Maclaurin Construction
- Branch
- Branch Cut
- Branch Line
- Branch Point
- Brauer Chain
- Brauer Group
- Brauer Number
- Brauer-Severi Variety
- Brauer's Theorem
- Braun's Conjecture
- Breeder
- Brelaz's Heuristic Algorithm
- Brent-Salamin Formula
- Brent's Factorization Method
- Brent's Method