Pollard's rho algorithm

From Wikipedia, the free 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.

Contents 1 Core ideas 2 The algorithm 3 Richard Brent's variant 4 In practice 5 Example factorization 6 Complexity 7 External links 8 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 numbers have been randomly chosen. If p is a factor of n, the integer we are aiming to factor, then since p divides both 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)
3. If d = n, return failure.
4. Else, return d.

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.

1. y ← x₀, 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 3 GHz workstation, the original rho algorithm found the factor 274177 of the sixth Fermat number (18446744073709551617) in 26 milliseconds; the Richard Brent variant found the same factor in 5 millisecond. However, for a semiprime of the same size (10023859281455311421), the same workstation using the original rho algorithm took 109 milliseconeds to find a factor; the Richard Brent variant took 31 milliseconds.

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] 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) instead of 97.

[edit] Complexity

The algorithm offers a trade-off between its running time and the probability that it finds a factor. If n is a product of two distinct primes of equal length, running the algorithm for O(n^1/4 polylog(n)) steps yields a factor with probability roughly half. (Note that this is a heuristic claim, and rigorous analysis of the algorithm remains open.)

[edit] External links

• Java Implementation

[edit] References

• J.M. Pollard. "A Monte Carlo method for factorization", BIT Numerical Mathematics 15(3), 1975, pp. 331-334.
• Richard P. Brent. An Improved Monte Carlo Factorization Algorithm, BIT 20, 1980, pp.176-184, http://wwwmaths.anu.edu.au/~brent/pd/rpb051i.pdf
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.9: Integer factorization, pp.896–901 (this section discusses only Pollard's rho algorithm).

v • d • e Number-theoretic algorithms Primality tests AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division Sieving algorithms Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm Other algorithms Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.