Classical Primality and Factoring
The Pollard p-1 Method
Pollard's p-1 method, its dependence on the smoothness of the group order, and why that dependence is its fatal limitation.
Engineering / MathematicsClassical Primality and Factoring2 min readKV-MATH-0654
Pollard's p-1 method finds a prime factor when the order of the multiplicative group modulo that factor is smooth. It is fast when it works and useless when it does not, and understanding why motivates ECM.
The idea
If one less than a prime factor is smooth, then raising a base to a highly composite exponent gives one modulo that factor, and a GCD reveals it.
Pollard p-1, stage one
- Choose a boundThe smoothness bound for stage one.
- Build the exponentThe product of prime powers below the bound.
- ExponentiateCompute the base to that exponent modulo the number.
- Take a GCDOf the result minus one with the number.
- InterpretA non-trivial GCD is a factor.
Stage two
If one less than the factor is smooth except for a single larger prime, a second stage searching over that prime finds it much more cheaply than raising the bound.
The fatal limitation
This makes p-1 a special-purpose method. It is worth a brief attempt because it is cheap and occasionally spectacular, but it cannot be relied upon.
Why ECM is the answer
Cryptographic relevance
The p+1 variant
Williams' p+1 method uses Lucas sequences to exploit smoothness of one more than the factor instead, in the same relation to p-1 as N+1 tests bear to N-1 tests. It shares the same fundamental limitation.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 8.5. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.