Modern Primality Tests
The Goldwasser-Kilian Primality Test
Primality proving by elliptic curves with known point counts, its recursive certificate, and the point-counting bottleneck.
Engineering / MathematicsModern Primality Tests2 min readKV-MATH-0662
Goldwasser-Kilian proves primality using an elliptic curve group in place of the multiplicative group. It removes the factoring obstruction of the classical methods and produces a certificate.
The idea
The Pocklington criterion has an elliptic curve analogue: a point of large known order on a curve modulo the candidate certifies primality, provided the order has a suitable large prime factor.
The algorithm
Goldwasser-Kilian primality proving
- Choose a random curveModulo the candidate.
- Count pointsUsing Schoof's algorithm.
- Test the orderAccept if it factors as a small part times a large probable prime.
- Find a pointOf the required order on the curve.
- RecurseThe large prime factor becomes the new candidate.
- TerminateAt a candidate small enough to test directly.
The certificate
The output is a chain: for each level, a curve, a point, and the factorisation of the order. Verification checks the point arithmetic at each level, which is far cheaper than the search that produced it.
The bottleneck
The Atkin-Morain fix
Complexity
| Aspect | Status |
|---|---|
| Expected running time | Polynomial, under heuristic assumptions |
| Worst case | Not proven polynomial |
| Certificate verification | Polynomial, unconditionally |
| Heuristic content | That curve orders behave like random integers of their size for smoothness purposes |
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 9.2.1. 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.