Pollard's rho algorithm

From Free net encyclopedia

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.

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

[edit]

Core ideas

The rho algorithm is based on Floyd's cycle-finding algorithm and on the observation that (as in 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>1 < \gcd \left( |x-y|,n \right) \le n</math> since p divides both <math>\left|x-y\right|</math> and n.

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.

[edit]

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.

x ← 2, y ← 2; d ← 1
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.

[edit]

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; m such that m > 0; and f(x), a pseudo-random function modulo n.

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

y ← x₀, r ← 1, q ← 1.
Do:
1. x ← y
2. For i = 1 To r:
  1. y ← f(y)
3. k ← 0
4. 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 + i
5. Until (k ≥ r or g > 1)
6. r ← 2r
Until g > 1
If g = n then
1. Do:
  1. ys ← f(ys), g ← GCD(|x − ys|, n)
2. Until g > 1
If g = n then return failure, else return g

[edit]

In practice

The algorithm is very fast for numbers with small factors. For example, on a 733 MHz 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:

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.

[edit]