Pollard's rho algorithm
Pollard's rho algorithm is a general-purpose integer factorization algorithm. It was invented by John Pollard in 1975. It is particularly effective at splitting composite numbers with small factors.
Contents
Core ideas
The rho algorithm is based on Floyd's cycle-finding algorithm and on the observation that (as in the birthday problem) 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 
.
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.
Algorithm
Inputs: n, the integer to be factored; and f, a function with the property that x=y mod p implies f(x)=f(y) mod p.
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 may not find the factors and will return failure for composite n. In that case, use a different f(x) and try again. Note, as well, that this algorithm does not work when n is a prime number, since, in this case, d will be always 1. The algorithm is so-called because the values of f enter a period (mod d), resulting in a ρ shape when diagrammed.
Variants
In 1980, Richard Brent published a faster variant of the rho algorithm. He used the same core ideas as Pollard but a different method of cycle detection, replacing Floyd's cycle-finding algorithm with the related Brent's cycle finding method.
A further improvement was made by Pollard and Brent. They observed that if 
, then also 
for any positive integer b. In particular, instead of computing 
at every step, it suffices to define z as the product of 100 consecutive 
terms modulo n, and then compute a single 
. A major speed up results as 100 gcd steps are replaced with 99 multiplications modulo n and a single gcd. Occasionally it may cause the algorithm to fail by introducing a repeated factor, for instance when n is a square. But it then suffices to go back to the previous gcd term, where 
, and use the regular Rho algorithm from there.
Application
The algorithm is very fast for numbers with small factors, but slower in cases where all factors are large. 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.
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.
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.[citation needed] (Note that this is a heuristic claim, and rigorous analysis of the algorithm remains open.)
References
- Brent, Richard P. (1980), "An Improved Monte Carlo Factorization Algorithm", BIT 20: 176–184, doi:10.1007/BF01933190
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford (2001), "Section 31.9: Integer factorization", Introduction to Algorithms (Second ed.), Cambridge, MA: MIT Press, pp. 896–901, ISBN 0-262-03293-7 (this section discusses only Pollard's rho algorithm).
- Katz, Jonathan; Lindell, Yehuda (2007), "Chapter 8", Introduction to Modern Cryptography, CRC Press
- Pollard, J. M. (1975), "A Monte Carlo method for factorization", BIT Numerical Mathematics 15 (3): 331–334
External links
|
|||||||||||||||||||||||||||||
