Pollard's rho algorithm: Difference between revisions

Revision as of 11:38, 20 January 2025

Revision as of 20:59, 8 April 2025

Line 55:

== Variants ==

In 1980, [[Richard Brent (scientist)|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 [[Cycle detection#Brent.27s algorithm|Brent's cycle finding method]].<ref>{{cite journal |last=Brent |first=Richard P. |authorlink=Richard Brent (scientist) |year=1980 |title=An Improved Monte Carlo Factorization Algorithm |journal=BIT |volume=20 |issue=2 |pages=176–184 |url=httphttps://maths-people.anu.edu.au/~brent/pub/pub051.html |doi=10.1007/BF01933190|s2cid=17181286 }}</ref> CLRS gives a heuristic analysis and failure conditions (the trivial divisor <math>n</math> is found).<ref name=":0" />

A further improvement was made by Pollard and Brent. They observed that if <math>\gcd(a,n) > 1</math>, then also <math>\gcd(ab,n) > 1</math> for any positive integer {{tmath|b}}. In particular, instead of computing <math>\gcd (|x-y|,n)</math> at every step, it suffices to define {{tmath|z}} as the product of 100 consecutive <math>|x-y|</math> terms modulo {{tmath|n}}, and then compute a single <math>\gcd(z,n)</math>. A major speed up results as 100 {{math|gcd}} steps are replaced with 99 multiplications modulo {{tmath|n}} and a single {{math|gcd}}. Occasionally it may cause the algorithm to fail by introducing a repeated factor, for instance when {{tmath|n}} is a [[square (algebra)|square]]. But it then suffices to go back to the previous {{math|gcd}} term, where <math>\gcd(z,n)=1</math>, and use the regular ''ρ'' algorithm from there.<ref group="note">Exercise 31.9-4 in CLRS</ref>