Modern Primality Tests
The Modern Primality Testing Landscape
The methods available for proving primality, their complexities, and which to use for a given size of candidate.
Engineering / MathematicsModern Primality Tests2 min readKV-MATH-0657
Proving primality without factoring one less or one more than the candidate requires modern methods. Three families exist, and the one that is theoretically most satisfying is the one least used.
The three families
| Method | Complexity | Certificate | Practical use |
|---|---|---|---|
| Jacobi sum (APR-CL) | Almost polynomial — a slowly growing exponent | None; the run must be trusted or repeated | Very fast up to a few thousand digits |
| Elliptic curve (ECPP) | Heuristically polynomial | Yes, quickly verifiable | The general workhorse |
| AKS | Provably polynomial | The run itself | Not competitive in practice |
Choosing
- How certain must the result be?
- Practical certainty sufficesBaillie-PSW — cheapest by far
- A proof is required
- Does one less or one more factor easily?Pocklington-Lehmer or the N+1 test
- Up to a few thousand digits, no certificate neededJacobi sum
- Certificate needed, or very largeECPP
Why certificates matter
Always test before proving
The standard sequence
- Trial divideRemoves most composites at negligible cost.
- Run Baillie-PSWSettles compositeness with near certainty.
- Only then proveProving methods are expensive and should never be run on a number not already known to be a probable prime.
Practical scale
Baillie-PSW is effectively instantaneous at any size encountered in practice. The Jacobi sum test handles a few thousand digits comfortably. ECPP has proved primality of numbers with tens of thousands of digits, though such runs take considerable time.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 9. 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.