Pollard's p − 1 algorithm

Pollard's p − 1 algorithm is a <a href="/facts/Number_theory/zhoa7zrc">number theoretic</a> <a href="/facts/Integer_factorization/EjMCTz2t">integer factorization</a> <a href="/facts/Algorithm/fnl5NmRt">algorithm</a>, invented by <a href="/facts/John_Pollard_(mathematician)/wI1GHPYh">John Pollard</a> in 1974. It is a special-purpose algorithm, meaning that it is only suitable for <a href="/facts/Integer/PUwwrawx">integers</a> with specific types of factors; it is the simplest example of an <a href="/facts/Algebraic-group_factorisation_algorithm/rtwGraLN">algebraic-group factorisation algorithm</a>.
The factors it finds are ones for which the number preceding the factor, p − 1, is <a href="/facts/Smooth_number/pC6DVLJW">powersmooth</a>; the essential observation is that, by working in the multiplicative group <a href="/facts/Modular_arithmetic/0wtRa5dU">modulo</a> a composite number N, we are also working in the multiplicative groups modulo all of N's factors.
The existence of this algorithm leads to the concept of <a href="/facts/Safe_prime/d4pApf8z">safe primes</a>, being primes for which p − 1 is two times a <a href="/facts/Sophie_Germain_prime/d4pApf8z">Sophie Germain prime</a> q and thus minimally smooth. These primes are sometimes construed as "safe for cryptographic purposes", but they might be unsafe — in current recommendations for cryptographic <a href="/facts/Strong_prime/9XeCXPX5">strong primes</a> (e.g. ANSI X9.31), it is <a href="/facts/Necessary_but_not_sufficient/G45aDCY9">necessary but not sufficient</a> that p − 1 has at least one large prime factor. Most sufficiently large primes are strong; if a prime used for cryptographic purposes turns out to be non-strong, it is much more likely to be through malice than through an accident of <a href="/facts/Random_number_generation/RtXEfbzd">random number generation</a>. This terminology is considered <a href="/facts/Obsolete/IrFKfFja">obsolete</a> by the cryptography industry: the <a href="/facts/Lenstra_elliptic-curve_factorization/PwdIdtQW">ECM</a> factorization method is more efficient than Pollard's algorithm and finds safe prime factors just as quickly as it finds non-safe prime factors of similar size, thus the size of p is the key security parameter, not the smoothness of p-1.

Pollard's p − 1 algorithm open-in-new

Pollard's p − 1 algorithm