Pollard's p − 1 algorithm

Let n be a composite integer with prime factor p. By Fermat's little theorem, we know that for all integers a coprime to p and for all positive integers K:

${\displaystyle a^{K(p-1)}\equiv 1{\pmod {p}}}$

If a number x is congruent to 1 modulo a factor of n, then the gcd(x − 1, n) will be divisible by that factor.

The idea is to make the exponent a large multiple of p − 1 by making it a number with very many prime factors; generally, we take the product of all prime powers less than some limit B. Start with a random x, and repeatedly replace it by ${\displaystyle x^{w}{\bmod {n}}}$ as w runs through those prime powers. Check at each stage, or once at the end if you prefer, whether gcd(x − 1, n) is not equal to 1.

It is possible that for all the prime factors p of n, p − 1 is divisible by small primes, at which point the Pollard p − 1 algorithm simply returns n.

The basic algorithm can be written as follows:

Inputs: n: a composite number

Output: a nontrivial factor of n or failure

1. select a smoothness bound B
2. define ${\displaystyle M=\prod _{{\text{primes}}~q\leq B}q^{\lfloor \log _{q}{B}\rfloor }}$ (note: explicitly evaluating M may not be necessary)
3. randomly pick a coprime to n (note: we can actually fix a, e.g. if n is odd, then we can always select a = 2, random selection here is not imperative)
4. compute g = gcd(a^M − 1, n) (note: exponentiation can be done modulo n)
5. if 1 < g < n then return g
6. if g = 1 then select a larger B and go to step 2 or return failure
7. if g = n then select a smaller B and go to step 2 or return failure

If g = 1 in step 6, this indicates there are no prime factors p for which p-1 is B-powersmooth. If g = n in step 7, this usually indicates that all factors were B-powersmooth, but in rare cases it could indicate that a had a small order modulo n. Additionally, when the maximum prime factors of p-1 for each prime factors p of n are all the same in some rare cases, this algorithm will fail.

The running time of this algorithm is O(B × log B × log² n); larger values of B make it run slower, but are more likely to produce a factor.

Since the algorithm is incremental, it can just keep running with the bound constantly increasing.

Assume that p − 1, where p is the smallest prime factor of n, can be modelled as a random number of size less than √n. By Dixon's theorem, the probability that the largest factor of such a number is less than (p − 1)^1/ε is roughly ε^−ε; so there is a probability of about 3⁻³ = 1/27 that a B value of n^1/6 will yield a factorisation.

In practice, the elliptic curve method is faster than the Pollard p − 1 method once the factors are at all large; running the p − 1 method up to B = 2³² will find a quarter of all 64-bit factors and 1/27 of all 96-bit factors.

A variant of the basic algorithm is sometimes used; instead of requiring that p − 1 has all its factors less than B, we require it to have all but one of its factors less than some B₁, and the remaining factor less than some B₂ ≫ B₁. After completing the first stage, which is the same as the basic algorithm, instead of computing a new

${\displaystyle M'=\prod _{{\text{primes }}q\leq B_{2}}q^{\lfloor \log _{q}B_{2}\rfloor }}$

for B₂ and checking gcd(a^M' − 1, n), we compute

${\displaystyle Q=\prod _{{\text{primes }}q\in (B_{1},B_{2}]}(H^{q}-1)}$

where H = a^M and check if gcd(Q, n) produces a nontrivial factor of n. As before, exponentiations can be done modulo n.

Let {q₁, q₂, …} be successive prime numbers in the interval (B₁, B₂] and d_n = q_n − q_n−1 the difference between consecutive prime numbers. Since typically B₁ > 2, d_n are even numbers. The distribution of prime numbers is such that the d_n will all be relatively small. It is suggested that d_n ≤ ln² B₂. Hence, the values of H², H⁴, H⁶, … (mod n) can be stored in a table, and H^q_n be computed from H^q_n−1⋅H^d_n, saving the need for exponentiations.

• The GMP-ECM package includes an efficient implementation of the p − 1 method.
• Prime95 and MPrime, the official clients of the Great Internet Mersenne Prime Search, use a modified version of the p - 1 algorithm to eliminate potential candidates.

• Williams's p + 1 algorithm

• Pollard, J. M. (1974). "Theorems of factorization and primality testing". Proceedings of the Cambridge Philosophical Society. 76 (3): 521–528. Bibcode:1974PCPS...76..521P. doi:10.1017/S0305004100049252. S2CID 122817056.
• Montgomery, P. L.; Silverman, R. D. (1990). "An FFT extension to the P − 1 factoring algorithm". Mathematics of Computation. 54 (190): 839–854. Bibcode:1990MaCom..54..839M. doi:10.1090/S0025-5718-1990-1011444-3.
• Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. pp. 138–141. ISBN 978-1-4704-1048-3.