Classical Primality and Factoring
The Pocklington-Lehmer N-1 Primality Test
Proving primality from a partial factorisation of one less than the candidate, and the certificate this produces.
Engineering / MathematicsClassical Primality and Factoring2 min readKV-MATH-0650
The Pocklington-Lehmer test proves primality using a partial factorisation of one less than the candidate. It is the classical proving method and it produces a compact, quickly verifiable certificate.
The criterion
If a sufficiently large factored part of one less than the candidate is available, and suitable witnesses exist for each of its prime factors, the candidate is prime.
Pocklington-Lehmer primality proving
- Partially factorFind prime factors of one less than the candidate until their product exceeds the square root.
- Find witnessesFor each such prime, find a base whose power conditions hold.
- Verify the conditionsA Fermat-style condition plus a GCD condition for each prime factor.
- ConcludeThe candidate is proven prime.
The certificate
The certificate is recursive: each prime factor used must itself be proven prime, giving a tree of certificates terminating at small primes verifiable directly.
The limitation
Where it works well
| Situation | Why it works |
|---|---|
| Numbers of special form | One less than the candidate factors by construction |
| Constructed primes | Build the prime from known factors upward |
| Small candidates | The factorisation is feasible |
| Random large candidates | Generally infeasible |
The N+1 variant
A dual method uses the factorisation of one more than the candidate, working with Lucas sequences instead of powers — see N+1 tests. Combining both often succeeds where neither alone does.
Relation to modern methods
The modern proving methods remove the factoring requirement. Goldwasser-Kilian replaces the multiplicative group with an elliptic curve group whose order can be chosen to be easily factored, which is exactly the flexibility the classical method lacks.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 8.3. 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.