Pollard's Rho Algorithm

Pollard's rho algorithm is a randomized algorithm for 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 — 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.