Pollard's rho algorithm is an algorithm for integer factorization. It was invented by John Pollard in 1975. It uses only a small amount of space, and its expected running time is proportional to the square root of the smallest prime factor of the composite number being factorized.

Core ideas

The algorithm is used to factorize a number <math>n = pq</math>, where <math>p</math> is a non-trivial factor. A polynomial modulo <math>n</math>, called <math>g(x)</math> (e.g., <math>g(x) = (x^2 + 1) \bmod n</math>), is used to generate a pseudorandom sequence. <math>g(x)</math> must be a polynomial. A starting value, say 2, is chosen, and the sequence continues as <math>x_1 = g(2)</math>, <math>x_2 = g(g(2))</math>, <math>x_3 = g(g(g(2)))</math>, etc. The sequence is related to another sequence <math>\{x_k \bmod p\}</math>. Since <math>p</math> is not known beforehand, this sequence cannot be explicitly computed in the algorithm. Yet in it lies the core idea of the algorithm.

Because the number of possible values for these sequences is finite, both the <math>\{x_k\}</math> sequence, which is mod <math>n</math>, and <math>\{x_k \bmod p\}</math> sequence will eventually repeat, even though these values are unknown. If the sequences were to behave like random numbers, the birthday paradox implies that the number of <math>x_k</math> before a repetition occurs would be expected to be <math>O(\sqrt N)</math>, where <math>N</math> is the number of possible values. So the sequence <math>\{x_k \bmod p\}</math> will likely repeat much earlier than the sequence <math>\{x_k\}</math>. When one has found a <math>k_1,k_2</math> such that <math>x_{k_1}\neq x_{k_2}</math> but <math>x_{k_1}\equiv x_{k_2}\bmod p</math>, the number <math>|x_{k_1}-x_{k_2}|</math> is a multiple of <math>p</math>, so a non-trivial divisor has been found.

Pseudocode for Pollard's rho algorithm

x ← 2 // starting value

y ← x

d ← 1

while d = 1:

x ← g(x)

y ← g(g(y))

d ← gcd(|x - y|, n)

if d = n:

return failure

else:

return d

Here and corresponds to and in the previous section. Note that this algorithm may fail to find a nontrivial factor even when is composite. In that case, the method can be tried again, using a starting value of x other than 2 (<math>0 \leq x < n</math>) or a different , <math>g(x) = (x^2 + b) \bmod n</math>, with <math>1 \leq b < n-2</math>.

Example factorization

Let <math>n = 8051</math> and <math>g(x) = (x^2 + 1) \bmod 8051</math>.

thumb|348x348px|Pollard's rho algorithm example factorization for <math>n=253</math> and <math>g(x)=x^2 \bmod 253</math>, with starting value 2. The example is using [[Floyd's cycle-finding algorithm.]]

{| class="wikitable" style="text-align:right"

! width=30 | || width=60 | || width=60 | ||

|-

| 1 || 5 || 26 || 1

|-

| 2 || 26 || 7474 || 1

|-

| 3 || 677 || 871 || 97

|-

| 4 || 7474 || 1481 || 1

|}

Now 97 is a non-trivial factor of 8051. Starting values other than may give the cofactor (83) instead of 97. One extra iteration is shown above to make it clear that moves twice as fast as . Note that even after a repetition, the GCD can return to 1.

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. CLRS (Cormen et Al. Introduction to Algorithms book) gives a heuristic analysis and failure conditions (the trivial divisor <math>n</math> is found).

Application

The algorithm is very fast for numbers with small factors, but slower in cases where all factors are large. The ρ algorithm's most remarkable success was the 1980 factorization of the Fermat number = 1238926361552897&nbsp;×&nbsp;93461639715357977769163558199606896584051237541638188580280321. The ρ algorithm was a good choice for because the prime factor = 1238926361552897 is much smaller than the other factor. The factorization took 2 hours on a UNIVAC 1100/42.

See also

  • Pollard's rho algorithm for logarithms
  • Pollard's kangaroo algorithm

Notes

References

Further reading

  • Describes the improvements available from different iteration functions and cycle-finding algorithms.
  • Comprehensive article on Pollard's Rho algorithm aimed at an introductory-level audience

<!-- Dead link: * Java Implementation -->

  • Java Implementation
  • About Pollard rho