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 |
[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.
- x ← 2, y ← 2; d ← 1
- While d = 1:
- x ← f(x)
- y ← f(f(y))
- d ← GCD(|x − y|, n)
- If d = n, return failure.
- 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; 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.
- y ← x0, r ← 1, q ← 1.
- Do:
- x ← y
- For i = 1 To r:
- y ← f(y)
- k ← 0
- Do:
- ys ← y
- For i = 1 To min(m, r − k):
- y ← f(y)
- q ← (q × |x − y|) mod n
- g ← GCD(q, n)
- k ← k + m
- Until (k ≥ r or g > 1)
- r ← 2r
- Until g > 1
- If g = n then
- Do:
- ys ← f(ys)
- g ← GCD(|x − ys|, n)
- Until g > 1
- Do:
- 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 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) 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(n1/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
[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).
|