Pollard's Rho Algorithm - Variants

Variants

In 1980, Richard Brent published a faster variant of the rho algorithm. He used the same core ideas as Pollard but a different method of cycle detection, replacing Floyd's cycle-finding algorithm with the related Brent's cycle finding method.

A further improvement was made by Pollard and Brent. They observed that if, then also for any positive integer b. In particular, instead of computing at every step, it suffices to define z as the product of 100 consecutive terms modulo n, and then compute a single . A major speed up results as 100 gcd steps are replaced with 99 multiplications modulo n and a single gcd. Occasionally it may cause the algorithm to fail by introducing a repeated factor, for instance when n is a square. But it then suffices to go back to the previous gcd term, where, and use the regular Rho algorithm from there.