= Pollard's rho algorithm
{c}
= Pollard rho factorization algorithm
{c}
{synonym}
= Pollard rho
{c}
{synonym}
An <integer factorization> algorithm that iterates a simple map such as $x\mapsto x^2+c\bmod 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.
Back to article page
