Pollard’s p-1 algorithm
Pollard’s p-1 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 p-1 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 B and call Pollard’s p-1 algorithm with a positive integer.
-
1.
Use a simple method (such as the sieve of Eratosthenes) to find primes p<B, or even probable primes.
- 2.
-
3.
Find the exponent e such that pe≤B. Then for each p<B, compute b=apemod and see if . If that’s the case, return those results of the greatest common divisor function, exit.
-
4.
If the GCD function consistently returned 1s, one could try a higher test cap and try again from step 1.
-
5.
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 .
-
6.
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.
References
- 1 R. Crandall & C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001: 5.4.1
Title | Pollard’s algorithm |
---|---|
Canonical name | PollardsP1Algorithm |
Date of creation | 2013-03-22 16:43:47 |
Last modified on | 2013-03-22 16:43:47 |
Owner | PrimeFan (13766) |
Last modified by | PrimeFan (13766) |
Numerical id | 8 |
Author | PrimeFan (13766) |
Entry type | Algorithm |
Classification | msc 11A41 |
Synonym | Pollard algorithm |
Synonym | Pollard’s p minus 1 algorithm |
Synonym | Pollard p minus 1 algorithm |
Synonym | Pollard method |
Synonym | Pollard’s p minus 1 method |
Synonym | Pollard p minus 1 method |
Synonym | Pollard’s method |