The group order is no longer fixed by n
The Pocklington test fails when n − 1 cannot be factored, and nothing can be done about it — the group is determined by n. On an elliptic curve modulo n the group order varies with the curve, so a curve can be sought whose order has a large easily-certified prime factor. That reduces primality of n to primality of a smaller number, and iterating produces a short certificate that verifies quickly.
Learning objectives
- State the elliptic curve analogue of the Pocklington criterion.
- Explain the downstep and why the certificate terminates.
- Describe how the CM method avoids general point counting.
- Interpret and verify an ECPP certificate.
- State the practical limits of the method.
Section 01The criterion
Let E be a curve modulo n and P a point on it. Suppose m is a candidate for the group order, q a prime divisor of m with q > (n1/4 + 1)2, and
Then n is prime, provided q is prime. The bound on q comes from Hasse: it forces any prime factor of n to exceed n1/2, which is impossible unless n is prime.
Primality of n is reduced to primality of q, which is roughly the same size as n but strictly smaller. Iterating gives a decreasing chain that terminates at a small prime. The chain is the certificate.
Section 02Goldwasser–Kilian and Atkin–Morain
Choose random curves and count points with Schoof's algorithm until an order with a large prime factor appears. Theoretically clean; the point counting is the bottleneck.
Choose a CM discriminant D, solve 4n = u² + |D|v² by Cornacchia, and the candidate orders are n + 1 ± u immediately. Build the curve only after a suitable order is found — no point counting at all.
- For each small CM discriminant D in order of increasing class number:
- Check that D is a quadratic residue modulo n; if not, skip.
- Solve 4n = u2 + |D|v2 by Cornacchia's algorithm. Fails quickly when no representation exists.
- Test the candidate orders m = n + 1 ± u for a large prime factor q after removing small factors.
- If a suitable q is found, compute the class polynomial for D, find a root modulo n, and build the curve.
- Find a point P and verify the two multiplication conditions; recurse on q.
Most discriminants yield no representation, or an order with no large prime factor. Each attempt is fast, and the search simply moves on. The randomised character of the method lies here, in how many attempts are needed — not in the correctness of the result.
Section 03Certificates
The certificate is the chain of steps: for each level, the curve parameters, the point, the candidate order and the next prime. Verification repeats only the scalar multiplications.
- Stage 01Read the levelTake n, the curve parameters, the point P, the order m and the prime q.
- Stage 02Check the curveConfirm the discriminant is invertible modulo n and P lies on E.
- Stage 03Check the conditionsVerify [m]P = O and [m/q]P ≠ O.
- Stage 04DescendMove to the next level with n replaced by q; stop at a small prime verified directly.
A certificate that takes minutes to verify for a proof that took weeks to find is what makes a primality claim publicly checkable. This is the decisive advantage over the Jacobi sum test, which offers no such artefact.
Section 04Practical considerations
| Aspect | Guidance |
|---|---|
| Preliminary screening | Always run strong probable prime tests first — ECPP on a composite wastes very large amounts of time before failing |
| Discriminant ordering | Try small class numbers first; the class polynomial cost grows with |D| |
| Backtracking | If a level yields no usable order, return to the previous level and choose a different q — the chain is a search tree, not a line |
| Parallelism | Independent discriminants can be tried in parallel; distributed ECPP is how record proofs are obtained |
| Certificate storage | Store and publish the certificate; it is the durable artefact, not the log of the search |
Occasionally no suitable curve is found at a level within a reasonable budget. The remedy is to back up and select a different prime at the previous level. Implementations must support backtracking, since a purely forward search can fail on inputs that are perfectly provable.
ReferenceFrequently asked questions
Why is the bound on q what it is?
It comes from Hasse's theorem: a group order within 2√n of n + 1 combined with a point of order q greater than (n^(1/4) + 1)² forces any prime factor of n to exceed √n, which is impossible for a composite.
What happens if n is actually composite?
The arithmetic modulo n is not field arithmetic, so an inversion will typically fail during a scalar multiplication — revealing a factor of n. Alternatively the multiplication conditions simply fail. Either way the method does not produce a false proof.
How large can ECPP go?
Proofs for numbers of tens of thousands of digits have been completed with distributed computation. The practical limit is set by the class polynomial computation and the search for usable orders, both of which grow steadily rather than abruptly.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.