Pollard's rho algorithm

From Wikipedia, the free encyclopedia

This article is about integer factorization algorithm. For discrete logarithm algorithm, see Pollard's rho algorithm for logarithms.

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

[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 1.177\sqrt{p} numbers have been randomly chosen. If p is a factor of n, the integer we are aiming to factor, then 1 < \gcd \left( |x-y|,n \right) \le n since p divides both \left|x-y\right| 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.

  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.

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

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

  1. y ← x0, r ← 1, q ← 1.
  2. 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)
        2. q ← (q × |x − y|) mod n
      3. g ← GCD(q, n)
      4. k ← k + m
    5. Until (k ≥ r or g > 1)
    6. r ← 2r
  3. Until g > 1
  4. If g = n then
    1. Do:
      1. ys ← f(ys)
      2. g ← GCD(|x − ys|, n)
    2. Until g > 1
  5. 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:

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

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 F8 took, in total, 2 hours on a UNIVAC 1100/42.

[edit] Example factorization

Let n = 8051 and f(x) = x2 + 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.

[edit] Complexity

In the worst-case scenario, the algorithm has a complexity of O(n1/4) for integer n.

[edit] References

Retrieved from "http://en.wikipedia.org../../../p/o/l/Pollard%27s_rho_algorithm.html"
In other languages