Pollard's p - 1 algorithm

Pollard's p-1 algorithm is a number theoretic integer factorization algorithm invented by John Pollard in 1974. It is a special-purpose algorithm, suitable only for integers with particular kinds of factors, and it is the simplest example of an algebraic-group factorisation algorithm. It finds a prime factor p of a composite number n when p-1 is powersmooth. Working in the multiplicative group modulo n also means working modulo every factor of n, and by Fermat's little theorem a raised to a large multiple of p-1 is congruent to 1 modulo p, so the greatest common divisor of that value minus one and n reveals the factor. The exponent is made a multiple of p-1 by taking the product of all prime powers below a smoothness bound B. The basic running time is O(B x log B x log squared n), so larger bounds are slower but more likely to succeed. The method gave rise to the idea of safe primes, although the elliptic curve method has since made that terminology obsolete in cryptography.