Pollard’s method is an integer factorization algorithm devised by John Pollard in 1974 to take advantage of Fermat’s little theorem. 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.
Choose a test cap and call Pollard’s algorithm with a positive integer.
If the GCD function consistently returned 1s, one could try a higher test cap and try again from step 1.
If the GCD function consistently returned itself, this could indicate that is in fact not coprime to , in which case one could try going back to step 2 to pick a different .
Throw a failure exception.
For example, . Of course it’s overkill to use the Pollard algorithm on such a small number, but it helps to keep the example simple. Since the running time of the algorithm is exponential, Crandall and Pomerance suggest picking small . So for this example let’s pick , the primes are then 2, 3, 5, 7, and the exponents are 3, 2, 1, 1. Since 221 is odd, we try . So we see that , and . We also see and . Multiplication immediately verifies that .
As of version 5.2, Pollard’s algorithm is one of the methods used by Mathematica’s
FactorInteger function after ferreting out small factors by trial division.
- 1 R. Crandall & C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001: 5.4.1
|Date of creation||2013-03-22 16:43:47|
|Last modified on||2013-03-22 16:43:47|
|Last modified by||PrimeFan (13766)|
|Synonym||Pollard’s p minus 1 algorithm|
|Synonym||Pollard p minus 1 algorithm|
|Synonym||Pollard’s p minus 1 method|
|Synonym||Pollard p minus 1 method|