Modern Primality Tests
Primality Certificates and Independent Verification
What a primality certificate is, why verification is cheaper than production, and what a certificate does and does not guarantee.
Engineering / MathematicsModern Primality Tests2 min readKV-MATH-0664
A certificate is data allowing a primality claim to be verified much more cheaply than it was produced, and by independent software. This converts trust in an implementation into a checkable mathematical claim.
The asymmetry
| Method | Production cost | Verification cost |
|---|---|---|
| Pocklington-Lehmer | Requires factoring one less than the candidate | A few modular exponentiations |
| ECPP | Substantial search | Point arithmetic at each level; logarithmically many levels |
| Jacobi sum | Moderate | The same as production — no certificate |
Structure of an ECPP certificate
Per recursion level
The chain terminates at a number small enough to verify by direct means, and each level is checked by elliptic curve arithmetic alone.
What a certificate guarantees
- Correctness of the claim
- If the certificate verifies, the number is prime. This is unconditional.
- Independence from the producer
- Verification uses different code and different logic.
- Nothing about the search
- The certificate says nothing about how it was found, and does not need to.
Verification discipline
Verifying a certificate
- Use independent softwareVerification by the producing program establishes much less.
- Check every levelIncluding the recursion structure and that each level's next candidate matches.
- Check the terminal caseThe smallest number must be verified by an independent method.
- Check the arithmeticPoint orders and curve membership at each level.
When certificates matter
For published mathematical results, for adversarially supplied input, and wherever the primality claim will be relied upon by others. For routine cryptographic key generation, Baillie-PSW is normally accepted without proof.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 9.2. 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.