Pollard's p-1 algorithm

In number theory, Pollard's p − 1 algorithm is an integer factorization algorithm, invented by John Pollard in 1974. 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:

<math>s^\ell\leq n\Longrightarrow \ell\ln s\leq \ln n\Longrightarrow \ell\leq\log_s n<math>

<math>M=\prod_{s\leq B}s^{\lfloor\log_s n\rfloor}<math>

where s is each distinct prime less than or equal to B. This calculation is usually not actually performed; this representation of M is used later. Now, by Fermat's little theorem:

<math>a^{p-1}\equiv 1\pmod{p}<math>

<math>a^{k(p-1)}\equiv 1^{k}=1\pmod{p}<math>

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

<math>a^M-1\equiv 0\pmod{p}<math>

p divides a^M−1, so gcd(n, a^M−1 mod n) yields a factor of n. The calculation a^M−1 is performed using the square-and-multiply algorithm; since we know the factors of M, this is easy: see the example below. This in fact leads to an optimization of the algorithm: see below. 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. RSA primes are specially chosen so that p−1 is not smooth with respect to a small number

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 = 8051. Let B = 3. So we now form M:

<math>\lfloor\log_2 8051\rfloor = 12;\lfloor\log_3 8051\rfloor=8.<math>

<math>M=2^{12}\cdot3^{8}<math>

Let a = 2.

<math>a^M=2^{2^{12}\cdot3^8}\hbox{ mod }8051<math>

<math>a^M=\left(2^{2^{12}}\hbox{ mod }8051\right)^{3^{8}}\hbox{ mod }8051<math>

<math>a^M=(3844)^{3^{8}}\hbox{ mod }8051<math>

<math>a^M\equiv6500\pmod{8051}<math>

<math>\gcd(6500-1,8051)=97.<math>

97 is a non-trivial factor of 8051, and we can easily find its cofactor: 83. Note that 97 − 1 = 2⁵•3 is 3-smooth, whereas 83 − 1 = 2•41 is not.

However, instead of waiting until a^M is calculated, we can take the gcd after each exponentiation - the gcd algorithm runs quickly. In this case, this will not find the factor any faster. It can, at times, save the algorithm from failure - if an intermediate result ever comes to 1, the rest of the intermediate results will come to 1 and the gcd will be n. This measure means that we can take a large value for B, or not use B at all - simply test each prime successively until p − 1 factors completely over them.