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]
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 (0)

There are currently no matching articles.