Pollard's rho algorithm

Pollard's rho algorithm is a special-purpose integer factorization algorithm. It was invented by John Pollard in 1975. It is particularly effective at splitting composite numbers with small factors.

Contents

1 Core ideas 2 The algorithm 3 Richard Brent's variant 4 In practice 5 Example factorization

Core ideas

The rho algorithm is based on Floyd's cycle-finding algorithm and the birthday paradox. It is based on the observation that, by the birthday paradox, two numbers x and y are congruent modulo p with probability 0.5 after

<math>1.177\sqrt{p}<math>

numbers have been randomly chosen. If p is a factor of n, the integer we are aiming to factor, then:

<math>\gcd(|x-y|,n)=p<math>

since

<math>x-y\equiv0\pmod{p}.<math>

The rho algorithm therefore uses a function modulo n as a generator of a pseudo-random sequence. It runs one sequence twice as "fast" as the other; i.e. for every iteration made by one copy of the sequence, the other copy makes two iterations. Let x be the current state of one sequence and y be the current state of the other. The GCD of |x − y| and n is taken at each step. If this GCD ever comes to n, then the algorithm terminates with failure, since this means x = y and therefore, by Floyd's cycle-finding algorithm, the sequence has cycled and continuing any further would only be repeating previous work.

The algorithm

Inputs: n, the integer to be factored; and f(x), a pseudo-random function modulo n

Output: a non-trivial factor of n, or failure.

1. x ← 2, y ← 2; d ← 1
2. While d = 1:
   1. x ← f(x)
   2. y ← f(f(y))
   3. d ← GCD(|x − y|, n)
   4. If 1 < d < n, then return d.
   5. If d = n, return failure.

Note that this algorithm will return failure for all prime n, but it can also fail for composite n. In that case, use a different f(x) and try again.

Richard Brent's variant

In 1980, Richard Brent published a faster variant of the rho algorithm. He used the same core ideas as Pollard, but he used a different method of cycle detection that was faster than Floyd's original algorithm.

Brent's algorithm is as follows:

Input: n, the integer to be factored; x₀, such that 0 ≤ x₀ ≤ n; and f(x), a pseudo-random function modulo n.

Output: a non-trivial factor of n, or failure.

1. y ← x₀, r ← 1, q ← 1.
2. Do:
   1. x ← y
   2. For i = 1 To r:
      1. y ← f(y), k = 0
   3. Do:
      1. ys ← y
      2. For i = 1 To min(m, r − k):
         1. y ← f(y), q ← (q × |x − y|) mod n
      3. g ← GCD(q, n), k ← k + m
   4. Until (k ≥ r or g > 1)
   5. r ← 2r
3. Until g > 1
4. If g = n then
   1. Do:
      1. ys ← f(ys), g ← GCD(x − ys, n)
   2. Until g > 1
5. If g = n then return failure, else return g

In practice

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:

<math>f(x)=x^2+c\hbox{ mod }n,\,c\neq0,-2.<math>

The rho algorithm's most remarkable success has been the factorization of the eighth Fermat number by Pollard and Brent. They used Brent's variant 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.

Example factorization

Let n = 8051 and f(x) = x² + 1 mod 8051.

i	xi	yi	GCD(|xi − yi|, 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.de:Pollard-Rho-Methode pl:Rho Pollarda