Pollard’s algorithm is an integer factorization algorithm devised by John Pollard in 1975 to take advantage of Floyd’s cycle-finding algorithm and pseudorandom number generation. Theoretically, trial division always returns a result (though of course in practice the computing engine’s resources could be exhausted or the user might not to be around to care for the result). Pollard’s algorithm, on the other hand, was designed from the outset to cope with the possibility of failure to return a result.
It can be left up to the implementer to choose a function with a finite set of values that can be guaranteed to become cyclic quickly enough after few iterations. Crandall and Pomerance recommend , where is the number to be factored and is a pseudorandom number chosen based on .
Choose a function per the given requirements and call Pollard’s algorithm with a positive integer.
Choose random and from the ranges and and set and .
If , it is a factor of . Otherwise, the algorithm has failed.
Take for example, . Suppose our dice give us and . I promise I didn’t choose these values consciously, but it happens that 37 does not change when input to ! 12 will change however, giving a sequence that continues 0, 20, 13. At 13, we find that , and computing gives up 6, which is not a prime, but is easily enough taken care of by trial division. The factorization is therefore .
To date, the most well-known success of this algorithm was when Pollard and Richard Brent factored 115792089237316195423570985008687907853269984665640564039457584007913129639937 (the eighth Fermat number) in less than two hours, which was an impressive feat in 1975 for a UNIVAC 1100/42. Today, Mathematica running on a Dell with Windows XP factors that number in about 12 seconds (Mathematica’s
FactorInteger function has always used Pollard’s algorithm as one of the algorithms it uses).
|Date of creation||2013-03-22 16:44:22|
|Last modified on||2013-03-22 16:44:22|
|Last modified by||PrimeFan (13766)|
|Synonym||Pollard’s rho algorithm|
|Synonym||Pollard rho algorithm|