Modern Primality Tests
Atkin-Morain Elliptic Curve Primality Proving
ECPP: using complex multiplication to construct curves of known order, avoiding point counting entirely.
Engineering / MathematicsModern Primality Tests2 min readKV-MATH-0663
Atkin-Morain primality proving replaces point counting with curve construction. Curves with complex multiplication have orders given by a formula, so a suitable order can be sought before any curve is built.
The reversal
| Goldwasser-Kilian | Atkin-Morain |
|---|---|
| Choose a curve | Choose a discriminant |
| Count its points — expensive | Compute the order from a formula — cheap |
| Hope the order is suitable | Test suitability before building anything |
| Repeat with a new curve | Repeat with a new discriminant |
The order formula
If the candidate is represented by the principal form of a discriminant, the curve orders with complex multiplication by that discriminant are given directly in terms of that representation.
The algorithm
Atkin-Morain ECPP
- Choose a discriminantSmall absolute value and small class number, tried in increasing order.
- Represent the candidateSolve the norm equation — this succeeds only for suitable discriminants.
- Compute candidate ordersFrom the representation.
- Test for a suitable factorisationA small part times a large probable prime.
- Build the curveVia the Hilbert class polynomial, finding a root modulo the candidate.
- Find a point and recurseAs in Goldwasser-Kilian.
Why the curve is built last
Class invariants
Discriminant ordering
Discriminants are tried in order of class number, since small class number means a small class polynomial. Most candidates are settled by one of the first few discriminants tried.
Practical performance
The certificate
The certificate is a chain of curve, point, discriminant and order factorisation at each level, verifiable independently and cheaply.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 9.2.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.