The Brent variant of Pollard rho finds factors of a composite integer by iterating a map such as . A collision modulo an unknown prime factor can be detected through . Brent's variant organizes comparisons in blocks whose lengths double, reducing the work of cycle detection compared with comparing two iterates at every step.[ref]
An improved Monte Carlo factorization algorithm by Richard P. Brent. §§3–4, cycle finding and factorization
It can also batch differences: compute their product modulo and take one greatest common divisor per block. If that gcd is , 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.
Articles by others on the same topic
There are currently no matching articles.