Pollard’s ρ algorithm


Pollard’s ρ algorithm is an integer factorization algorithm devised by John Pollard in 1975 to take advantage of Floyd’s cycle-finding algorithm and pseudorandom number generation. Theoretically, trial divisionMathworldPlanetmath always returns a result (though of course in practice the computing engine’s resources could be exhausted or the user might not to be around to care for the result). Pollard’s ρ algorithm, on the other hand, was designed from the outset to cope with the possibility of failure to return a result.

It can be left up to the implementer to choose a function f(x) with a finite setMathworldPlanetmath of values that can be guaranteed to become cyclic quickly enough after few iterations. Crandall and Pomerance recommend f(x)=x2+amodn, where n is the number to be factored and a is a pseudorandom number chosen based on n.

Choose a function f(x) per the given requirements and call Pollard’s ρ algorithm with n a positive integer.

  1. 1.

    Choose random a and b from the ranges 1<a<(n-3) and 0<b<(n-1) and set c=a and d=b.

  2. 2.

    Set g=1.

  3. 3.

    While g==1 and allowed number of iterations not exceeded, iterate c=f(c) once and d=f(d) twice and compute g=GCD(c-d,n). The implementer may choose to take the absolute valueMathworldPlanetmathPlanetmathPlanetmathPlanetmath of c-d, though some implementations of GCD don’t mind being given negative argumentsPlanetmathPlanetmath.

  4. 4.

    If g>1, it is a factor of n. Otherwise, the algorithm has failed.

Take for example, n=42. Suppose our dice give us a=12 and b=37. I promise I didn’t choose these values consciously, but it happens that 37 does not change when input to f(x)=x2+12mod42! 12 will change however, giving a sequenceMathworldPlanetmath that continues 0, 20, 13. At 13, we find that 37-13=24, and computing GCD(24,42) gives up 6, which is not a prime, but is easily enough taken care of by trial division. The factorization is therefore 42=237.

To date, the most well-known success of this algorithm was when Pollard and Richard Brent factored 115792089237316195423570985008687907853269984665640564039457584007913129639937 (the eighth Fermat number) in less than two hours, which was an impressive feat in 1975 for a UNIVAC 1100/42. Today, Mathematica running on a Dell with Windows XP factors that number in about 12 seconds (Mathematica’s FactorInteger function has always used Pollard’s ρ algorithm as one of the algorithms it uses).

Title Pollard’s ρ algorithm
Canonical name PollardsrhoAlgorithm
Date of creation 2013-03-22 16:44:22
Last modified on 2013-03-22 16:44:22
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 5
Author PrimeFan (13766)
Entry type Algorithm
Classification msc 11A41
Synonym Pollard ρ algorithm
Synonym Pollard’s rho algorithm
Synonym Pollard rho algorithm