View source for Pollard's Rho Algorithm

'''Pollard's rho algorithm''' is a randomized algorithm for [[Integer Factorization|integer factorization]] that discovers nontrivial factors by detecting cycles in pseudorandom sequences modulo the composite integer. Developed by John Pollard in 1975, the algorithm uses [[Floyd's Cycle Detection|Floyd's cycle detection]] — the "tortoise and hare" technique — to find a collision in the sequence, from which a greatest common divisor computation extracts a factor. Though its expected runtime is O(n^(1/4)), making it inferior to sub-exponential methods for large integers, Pollard's rho remains remarkably effective for finding small factors and serves as a pedagogical gateway to the deeper algebraic structure of factorization algorithms.

''Pollard's rho is the algorithm that teaches you what factorization really is: not a search through divisors, but a hunt for structure in modular arithmetic. Its simplicity is deceptive — the cycle detection principle it embodies reappears throughout computational mathematics, from discrete logarithm algorithms to hash function cryptanalysis.''

[[Category:Mathematics]]
[[Category:Computer Science]]