## You are here

HomePollard's $p - 1$ algorithm

## Primary tabs

# 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.

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

2. Choose an integer $a$ coprime 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 $\lfloor\sqrt{n}\rfloor+1$.

3. Find the exponent $e$ such that $p^{e}\leq B$. Then for each $p<B$, compute $b=a^{{p^{e}}}\mod n$ and see if $1<\gcd(b-1,n)<n$. 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 $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. 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 $2^{8}\mod 221=35$, and $\gcd(34,221)=17$. We also see $3^{9}\mod 221=14$ and $\gcd(13,221)=13$. Multiplication immediately verifies that $13\times 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 Numbers: A Computational Perspective, Springer, NY, 2001: 5.4.1

## Mathematics Subject Classification

11A41*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections