Pollard's rho algorithm
[1] It uses only a small amount of space, and its expected running time is proportional to the square root of the smallest prime factor of the composite number being factorized.
A starting value, say 2, is chosen, and the sequence continues as
is not known beforehand, this sequence cannot be explicitly computed in the algorithm.
Yet in it lies the core idea of the algorithm.
sequence will eventually repeat, even though these values are unknown.
This structure of eventual cycling gives rise to the name "rho algorithm", owing to similarity to the shape of the Greek letter ρ when the values
This is detected by Floyd's cycle-finding algorithm: two nodes
In this (uncommon) case the algorithm fails, and can be repeated with a different parameter.
The algorithm takes as its inputs n, the integer to be factored; and
, a polynomial in x computed modulo n. In the original algorithm,
It performs the following steps:[2] Pseudocode for Pollard's rho algorithm Here x and y corresponds to
Note that this algorithm may fail to find a nontrivial factor even when n is composite.
In that case, the method can be tried again, using a starting value of x other than 2 (
Starting values other than x = y = 2 may give the cofactor (83) instead of 97.
One extra iteration is shown above to make it clear that y moves twice as fast as x.
Note that even after a repetition, the GCD can return to 1.
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.
[3] CLRS gives a heuristic analysis and failure conditions (the trivial divisor
A major speed up results as 100 gcd steps are replaced with 99 multiplications modulo
Occasionally it may cause the algorithm to fail by introducing a repeated factor, for instance when
But it then suffices to go back to the previous gcd term, where
[note 1] The algorithm is very fast for numbers with small factors, but slower in cases where all factors are large.
The ρ algorithm's most remarkable success was the 1980 factorization of the Fermat number F8 = 1238926361552897 × 93461639715357977769163558199606896584051237541638188580280321.
[4] The following table shows numbers produced by the algorithm, starting with
The third and fourth columns of the table contain additional information not known by the algorithm.
They are included to show how the algorithm works.
The first repetition modulo 101 is 97 which occurs in step 17.
occurring in the Pollard ρ algorithm were an actual random number, it would follow that success would be achieved half the time, by the birthday paradox in
It is believed that the same analysis applies as well to the actual rho algorithm, but this is a heuristic claim, and rigorous analysis of the algorithm remains open.
