Pollard's rho algorithm

Pollard's rho algorithm

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.

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.177sqrt{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 ight) le n since "p" divides both left|x-y ight| 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.

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" &larr; 2, "y" &larr; 2; "d" &larr; 1
# While "d" = 1:
## "x" &larr; "f"("x")
## "y" &larr; "f"("f"("y"))
## "d" &larr; 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.

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

Output: a non-trivial factor of "n", or failure.
# "y" &larr; "x"0, "r" &larr; 1, "q" &larr; 1.
# Do:
## "x" &larr; "y"
## For "i" = 1 To "r":
### "y" &larr; "f"("y")
##"k" &larr; 0
## Do:
### "ys" &larr; "y"
### For "i" = 1 To min("m", "r" − "k"):
#### "y" &larr; "f"("y")
#### "q" &larr; ("q" &times; |"x" − "y"|) mod "n"
### "g" &larr; GCD("q", "n")
### "k" &larr; "k" + "m"
## Until ("k" &ge; "r" or "g" > 1)
## "r" &larr; 2"r"
# Until "g" > 1
# If "g" = "n" then
## Do:
### "ys" &larr; "f"("ys")
### "g" &larr; GCD(|"x" − "ys"|, "n")
## Until "g" > 1
# If "g" = "n" then return failure, else return "g"

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 milliseconds. However, for a semiprime of the same size (10023859281455311421), the same workstation using the original rho algorithm took 109 milliseconds 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:

:f(x)=x^2+chbox{ mod }n,,c eq0,-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 "F"8 took, in total, 2 hours on a UNIVAC 1100/42.

Example factorization

Let "n" = 8051 and "f"("x") = "x"2 + 1 mod 8051.

"i""x""i""y""i"GCD(|"x""i" − "y""i"|, 8051)
15261
22674741
367787197

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. (Note that this is a heuristic claim, and rigorous analysis of the algorithm remains open.)

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&ndash;901 (this section discusses only Pollard's rho algorithm).

External links

* [http://www.cs.princeton.edu/introcs/78crypto/PollardRho.java.html Java Implementation]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Pollard's rho algorithm for logarithms — is an algorithm for solving the discrete logarithm problem analogous to Pollard s rho algorithm for solving the Integer factorization problem.The goal is to compute gamma such that alpha ^ gamma = eta(mod N), where eta belongs to the group G… …   Wikipedia

  • Pollard's lambda algorithm — In mathematics, specifically computational number theory and computational algebra, Pollard s lambda algorithm (aka Pollard s kangaroo algorithm, see Naming below) is an algorithm for solving the discrete logarithm. The algorithm was introduced… …   Wikipedia

  • Pollard — may refer to:*Pollard (surname) *Pollard, Alabama, a town in the United States *Jonathan Pollard, a spy *Pollard, a tree or animal which has been polled (had its branches, horns or antlers removed): **Pollard, a tree affected by pollarding, a… …   Wikipedia

  • In-place algorithm — In place redirects here. For execute in place file systems, see execute in place. In computer science, an in place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of… …   Wikipedia

  • Pollard-Rho-Methode — Grafische Darstellung der Teilergebnisse Die Pollard Rho Methoden sind Algorithmen zur Bestimmung der Periodenlänge einer Zahlenfolge, die mit einer mathematischen Funktion berechnet wird. Verschiedene schwierige mathematische Probleme wie der… …   Deutsch Wikipedia

  • Williams' p + 1 algorithm — In computational number theory, Williams p + 1 algorithm is an integer factorization algorithm, one of the family of algebraic group factorisation algorithms. It was invented by Hugh C. Williams in 1982. It works well if the number N to be… …   Wikipedia

  • Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… …   Wikipedia

  • Cipolla's algorithm — In computational number theory, Cipolla s algorithm is a technique for solving a congruence of the form x2 = n, where , so n is the square of x, and where p is an odd prime. Here denotes the finite field with p elements; . Th …   Wikipedia

  • Cornacchia's algorithm — In computational number theory, Cornacchia s algorithm is an algorithm for solving the Diophantine equation x2 + dy2 = m, where and d and m are coprime. The algorithm was described in 1908 by Giuseppe Cornacchia[1]. Contents 1 The algorithm …   Wikipedia

  • Algoritmo rho de Pollard — Para otros usos de este término, véase algoritmo rho de Pollard para logaritmos discretos. El algoritmo rho de Pollard es un algoritmo especializado de factorización de números enteros. Fue inventado por John Pollard en 1975. Es especialmente… …   Wikipedia Español

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”