Pollard's rho algorithm

Pollard's rho algorithm is a special-purpose integer factorization algorithm that is only effective for factoring integers with small factors. It was invented by John M. Pollard in 1975.

Let

$f:S\mapsto S$

be a random function, and S be a finite set of cardinality n, where n is the integer to be factored. Take the sequence:

$x_{0},x_{1},\ldots$

to be defined as:

$x_{i+1}=f(x_{i}){\hbox{ mod }}n,\,x_{0}=2.$

Since S is a finite set, the sequence must eventually repeat. This is where the algorithm gets its name: the cycling sequence looks like the Greek letter ρ. Now, the aim is to find x_a and x_b such that

$x_{a}\equiv x_{b}{\pmod {p}}$

where p is a non-trivial factor of n. This would mean that gcd(x_a − x_b, p) = p. Since we do not know p, we perform these comparisons and calculations modulo n.

The search for x_a and x_b is a modification of Floyd's cycle-finding algorithm. We run two sequences defined by our random function f, but we run one twice as fast as the other. At each step, we compute gcd(|x_a-x_b|, n) to check if we have a factor. If the gcd is greater than 1 and less than n, we have a factor.

The algorithm is very fast for numbers with small factors. For example, on a 733Mhz workstation, an implementation of the rho algorithm, without any optimizations, found the factor 274177 of the sixth Fermat number in about half a second. The sixth Fermat number is 18446744073709551617 (20 decimal digits). However, for a semiprime of the same size, the same workstation took around 9 seconds to find a factor of 10023859281455311421 (the product of 2 10-digit primes).

For f, we choose a polynomial with integer coefficients. The most common ones are of the form:

$f(x)=x^{2}+c{\hbox{ mod }}n,\,c\neq 0,-2.$

For some f, the algorithm will not find a factor. If gcd(|x_a − x_b|, n) = n, the algorithm has failed, because x_a = x_b, meaning that the sequence has cycled and that continuing any further is merely repeating previous work. Changing c or f can increase the chance of success. This failure situation will arise for all prime n, but it arises for some composites too.

Here is an example. Let n = 8051 and f(x) = x² + 1 mod 8051.

i	xi	x2i	GCD(|xi − x2i|, 8051)
1	5	26	1
2	26	7474	1
3	677	871	97

97 is a non-trivial factor of 8051. Other values of c may give the cofactor (83) of 97 instead of 97.

The rho algorithm's most remarkable success has been the factorization of the eighth Fermat number by Pollard and Richard Brent. They used a modified version of the algorithm, which found a previously unknown prime factor. The complete factorization of F₈ took, in total, 2 hours on a Univac 1100/42.