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. In mathematics, the integer prime-factorization (also known as prime decomposition) problem is this: given a positive integer, write it as a product of prime numbers. ... Flowcharts are often used to represent algorithms. ... John Pollard is a mathematician who produced seminal work in the theory of factorisation of large numbers. ... 1975 was a common year starting on Wednesday (the link is to a full 1975 calendar). ...

Core ideas

The rho algorithm is based on Floyd's cycle-finding algorithm and the birthday paradox. It is based on the observation that, by the birthday paradox, two numbers x and y are congruent modulo p with probability 0.5 after Floyds cycle-finding algorithm is an algorithm invented by Robert W. Floyd in 1967 which can detect cycles in arbitrary sequences, whether in data structures or generated on the fly, notably including those in graphs and pseudo-random sequences in O(1) space. ... The birthday paradox states that if there are 23 people in a room then there is a slightly more than 50:50 chance that at least two of them will have the same birthday. ...

numbers have been randomly chosen. If p is a factor of n, the integer we are aiming to factor, then:

gcd( | x − y | ,n) = p

since

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. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (GCF) or highest common factor (hcf) of two integers which are not both zero is the largest integer that divides both numbers. ...

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.

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. 1980 is a leap year starting on Tuesday. ... Richard Peirce Brent is an Australian mathematician and computer scientist. ...

Brent's algorithm is as follows:

Input: n, the integer to be factored; x₀, such that 0 ≤ x₀ ≤ n; 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), k = 0
   3. Do:
      1. ys ← y
      2. For i = 1 To min(m, r − k):
         1. y ← f(y), q ← (q × |x − y|) mod n
      3. g ← GCD(q, n), k ← k + m
   4. Until (k ≥ r or g > 1)
   5. r ← 2r
3. Until g > 1
4. If g = n then
   1. Do:
      1. ys ← f(ys), g ← GCD(x − ys, n)
   2. Until g > 1
5. 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 733Mhz 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). In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form where n is a nonnegative integer. ... In mathematics, a semiprime (also called biprime or 2-almost prime) is a natural number that is the product of two (not necessarily distinct) prime numbers. ...

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. The American company UNIVAC began as the business computer division of Remington Rand formed by the purchase of the Eckert-Mauchly Computer Corporation (EMCC) in 1950. ... The UNIVAC 1110 was the fourth member of Sperry Rands UNIVAC 1100 series of computers, introduced in 1972. ...

Example factorization

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

97 is a non-trivial factor of 8051. Other values of c may give the cofactor (83) of 97 instead of 97.