 Pollard's rho algorithm

An integer factorization algorithm that iterates a simple map such as $x\mapsto x^2+c\mathrm{mod}n$ and searches for a nontrivial greatest common divisor of $n$ and the difference of two iterates. A collision modulo an unknown prime factor can reveal that factor before a collision modulo $n$. A cycle detection schedule such as Floyd's cycle-finding algorithm limits the number of stored iterates. Unsuccessful choices of seed or map can be retried.