Pollard’s p-1 algorithm


Pollard’s p-1 method is an integer factorization algorithmMathworldPlanetmath devised by John Pollard in 1974 to take advantage of Fermat’s little theoremMathworldPlanetmath. Theoretically, trial divisionMathworldPlanetmath 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. 1.

    Use a simple method (such as the sieve of EratosthenesMathworldPlanetmathPlanetmath) to find primes p<B, or even probable primesMathworldPlanetmath.

  2. 2.

    Choose an integer a coprimeMathworldPlanetmathPlanetmath to n. If n is odd (which can be tested easily enough by looking at the least significant bit) then one possible choice is a=2. For even n, we could choose n+1.

  3. 3.

    Find the exponent e such that peB. Then for each p<B, compute b=apemodn and see if 1<gcd(b-1,n)<n. If that’s the case, return those results of the greatest common divisorMathworldPlanetmathPlanetmath function, exit.

  4. 4.

    If the GCD function consistently returned 1s, one could try a higher test cap and try again from step 1.

  5. 5.

    If the GCD function consistently returned n itself, this could indicate that a is in fact not coprime to n, in which case one could try going back to step 2 to pick a different a.

  6. 6.

    Throw a failure exception.

For example, n=221. Of course it’s overkill to use the Pollard p-1 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 B. So for this example let’s pick B=10, the primes are then 2, 3, 5, 7, and the exponents are 3, 2, 1, 1. Since 221 is odd, we try a=2. So we see that 28mod221=35, and gcd(34,221)=17. We also see 39mod221=14 and gcd(13,221)=13. MultiplicationPlanetmathPlanetmath immediately verifies that 13×17=221.

As of version 5.2, Pollard’s p-1 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 NumbersMathworldPlanetmath: A Computational Perspective, Springer, NY, 2001: 5.4.1
Title Pollard’s p-1 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 p-1 algorithm
Synonym Pollard’s p minus 1 algorithm
Synonym Pollard p minus 1 algorithm
Synonym Pollard p-1 method
Synonym Pollard’s p minus 1 method
Synonym Pollard p minus 1 method
Synonym Pollard’s p-1 method