A prime factorization algorithm also known as Pollard Monte Carlo factorization method. There are two aspects to the Pollard factorization method. The first is the idea of iterating a formula until it falls into a cycle. Let , where is the number to be factored and and are its unknown prime factors. Iterating the formula
(1)
|
or almost any polynomial formula (an exception being ) for any initial value will produce a sequence of number that eventually fall into a cycle. The expected time until the s become cyclic and the expected length of the cycle are both proportional to .
However, since with and relatively prime, the Chinese remainder theorem guarantees that each value of (mod ) corresponds uniquely to the pair of values (), ). Furthermore, the sequence of s follows exactly the same formula modulo and , i.e.,
(2)
| |||
(3)
|
Therefore, the sequence (mod ) will fall into a much shorter cycle of length on the order of . It can be directly verified that two values and have the same value (mod ), by computing
(4)
|
which is equal to .
The second part of Pollard's method concerns detection of the fact that a sequence has become periodic. Pollard's suggestion was to use the idea attributed to Floyd of comparing to for all . A different method is used in Brent's factorization method.
Under worst conditions, the Pollard algorithm can be very slow.