Pollard's p − 1 algorithm

In number theory, Pollard's p-1 algorithm is an integer factorization algorithm. It is a special-purpose algorithm, meaning that it is only suitable for integers with relatively small factors.

Let n be the integer to be factored, and p be one of its factors. If p−1 is smooth with respect to some relatively small bound B, then Pollard's p-1 algorithm can extract a factor. (If some number x is smooth with respect to B (equivalently, if x is B-smooth) then all of its prime factors are less than or equal to B.)

Let M be the product of maximal powers of primes such that the result is less than or equal to n, as follows:

$q^{l}\leq n\Longrightarrow l\ln q\leq \ln n\Longrightarrow l\leq \log _{q}n$

$M=\prod _{s\leq B}s^{\lfloor \log _{s}n\rfloor }{\pmod {n}}$

where s is each distinct prime less than or equal to B. This calculation is usually performed using the square-and-multiply algorithm. Now, by Fermat's Little Theorem:

$a^{p-1}\equiv 1{\pmod {p}}$

$a^{k(p-1)}\equiv 1^{k}=1{\pmod {p}}$

for all a with gcd(a, p) = 1. Now, if p−1 is B-smooth, then p−1 divides M, since all powers of primes less than B that are less than or equal to n are multiplied together to produce M. Thus M = k(p−1), and thus

$a^{M}-1\equiv 0{\pmod {p}}$

p divides a^M−1, so gcd(n, a^M−1 mod n) yields a factor of n. The calculation a^M−1 is also performed using the square-and-multiply algorithm. Performing this calculation modulo n does not change the result, since the common factor is still present.

Notice that this algorithm will not work unless p−1 is B-smooth. This makes it unsuitable for factoring RSA moduli, which are products of two large primes. To have p−1 be B-smooth, B would have to be unreasonably large.

For the value of the smoothness bound B, usually a relatively small value is chosen. For example, in The Handbook of Applied Cryptography, an example is supplied where n = 19048567 and B = 19. The larger B is, the more chance that p−1 will be B-smooth, but the longer it takes to compute M.

Here is an example. Let n = 35. Let B = 3. So we now compute M:

$\lfloor \log _{2}n\rfloor =5;\lfloor \log _{3}n\rfloor =3.$

$M=2^{5}\cdot 3^{3}=891\equiv 16{\pmod {35}}$

Let a = 2.

$\gcd(2^{16}-1{\hbox{ mod }}35,35)=\gcd(15,35)=5.$

5 is a non-trivial factor of 35. Note that 5−1 = 4 is 3-smooth.