Brent variant of Pollard rho (source code)

= Brent variant of Pollard rho
{c}

= Brent's variant
{c}
{synonym}

= Brent variant
{c}
{synonym}

The <Brent variant of Pollard rho> finds factors of a composite <integer> $N$ by iterating a map such as $x\mapsto x^2+c\pmod N$. A collision modulo an unknown <prime factor> can be detected through $\gcd(|x-y|,N)$. <Brent's variant> organizes comparisons in blocks whose lengths double, reducing the work of cycle detection compared with comparing two iterates at every step.<An improved Monte Carlo factorization algorithm by Richard P. Brent>[§§3–4, cycle finding and factorization]{ref}

It can also batch differences: compute their product modulo $N$ and take one <greatest common divisor> per block. If that gcd is $N$, retry the saved differences individually to recover a proper factor, or restart with a different orbit. The commonly used square-root-of-factor runtime estimate is heuristic and depends on treating the orbit modulo that factor like a random map.