Pollard's p-1 algorithm

For people who check facts

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:

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:

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

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:

Let a = 2.

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.