Pollard’s $\rho$ algorithm

Pollard’s $\rho$ 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 division 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 $\rho$ 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 set of values that can be guaranteed to become cyclic quickly enough after few iterations. Crandall and Pomerance recommend $f(x)=x^2+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 $\rho$ algorithm with $n$ a positive integer.

1. Choose random $a$ and $b$ from the ranges and and set $c=a$ and $d=b$.

2. Set $g=1$.

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 value of $c-d$, though some implementations of GCD don’t mind being given negative arguments.

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)=x^2+12mod42$! 12 will change however, giving a sequence 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=2\cdot 3\cdot 7$.

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 $\rho$ algorithm as one of the algorithms it uses).

Title	Pollard’s $\rho$ 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 $\rho$ algorithm
Synonym	Pollard’s rho algorithm
Synonym	Pollard rho algorithm