Primality testing asks whether a number is prime. Primality proving asks for evidence that another person or program can verify independently.
Elliptic Curve Primality Proving (ECPP) converts the primality of a large integer N into the primality of a smaller integer q. The reduction is accompanied by an elliptic curve and a point whose order is forced to contain q. Hasse’s bound then rules out every possible small prime divisor of N.
The certificate is recursive. Prove q in the same way, then q’s child, until the chain reaches a small prime that can be checked directly. Verification is much easier than discovering the curves.
This is Guide 24 in the Bukit Timah Tutor Computational Number Theory series. It completes Batch 06 by pairing factorisation algorithms with a certificate-based route for proving terminal factors prime. It uses elliptic-curve arithmetic from Guide 8 and the primality-testing overview in Guide 3.
1. Probable prime is not proved prime
Miller–Rabin can make compositeness extremely unlikely after several independent bases, and deterministic base sets exist for bounded integer ranges. But a probable-prime result and a general recursive proof certificate are different objects.
A certificate should let a verifier check a finite set of exact identities without rerunning the expensive discovery search.
This asymmetry—harder to find, easier to verify—is central to ECPP.
2. The elliptic-curve primality criterion
Let N be an integer coprime to 6. Choose an elliptic curve E modulo N, a point P, and positive integers m and s with s|m.
Suppose:
[m]P = O, and for every prime q dividing s, [m/q]P has projective Z-coordinate coprime to N.
Then every prime divisor p of N has an elliptic-curve group E(F_p) whose order is divisible by s.
If additionally
s > (N^(1/4)+1)²,
Hasse’s bound forces N to be prime. This is the core Goldwasser–Kilian/Atkin–Morain certificate principle.
3. Why the fourth-root bound works
Assume N were composite. It would have a prime divisor p≤√N.
Hasse gives
#E(F_p) ≤ (√p+1)²
≤ (N^(1/4)+1)².
But the certificate conditions force s to divide #E(F_p), hence #E(F_p)≥s.
If s is larger than the Hasse upper bound, contradiction. Therefore no prime divisor p≤√N exists, and N must be prime.
4. The common prime-q special case
Most simplified descriptions take s=q prime. Write
m = kq, q > (N^(1/4)+1)².
Find P with
[m]P=O, [k]P ≠ O
and with all required projective denominators invertible modulo N.
Then the order of P modulo every prime divisor of N is divisible by q. Hasse gives the contradiction if N were composite.
5. A complete small certificate for 101
Consider N=101 and the curve
E: y²=x³+x+3 (mod101).
The discriminant factor is
4·1³+27·3² = 247 ≡45 (mod101),
which is coprime to 101.
Take
P=(1,45).
Check that P lies on E:
45² ≡5 mod101, 1³+1+3 =5.
6. The candidate order and its large prime factor
For this curve, direct point counting in the small demonstration gives
m=#E(F101)=87=3·29.
Set q=29 and k=3.
The required size threshold is
(101^(1/4)+1)² ≈17.4.
Thus q=29 is large enough, and 29 is itself prime.
7. The point-order checks
Exact elliptic-curve arithmetic gives
[2]P=(19,35) [3]P=(4,24) [29]P=(3,29) [87]P=O.
In particular, [3]P is a finite affine point, so its projective Z-coordinate is 1 and therefore coprime to 101.
We have [87]P=O but [87/29]P=[3]P≠O. The criterion certifies 101 prime once the primality of 29 is accepted.
This example was deliberately chosen small enough that every displayed point can be checked independently.
8. Verification does not need to recount the curve
The verifier does not need to enumerate all 101 x-values to confirm #E(F101)=87.
The certificate theorem only needs the listed scalar-multiplication conditions, the large prime q, the curve non-singularity checks and the size inequality.
That is the efficiency advantage of a certificate: expensive curve-order discovery can be omitted from verification.
9. Why projective Z-coordinates appear
Modulo a composite N, affine formulas may ask for inverses that do not exist. A failed inversion can expose a factor, as in ECM.
ECPP verification can use projective coordinates to avoid repeated inversion. If Q=[m/q]P=(X:Y:Z), checking
gcd(Z,N)=1
ensures that Q remains a well-defined nonidentity point modulo every prime divisor relevant to the theorem.
If the gcd is nontrivial, the attempted proof has instead found a factor of N.
10. Recursive proof chains
For a large N, q is still large. So ECPP recursively proves q prime using another curve and another large factor q2.
A certificate becomes a chain
N0 → N1 → N2 → … → Nt,
where each N_(i+1) is the large prime factor used to certify N_i.
The chain ends when Nt is small enough for direct deterministic primality verification.
11. Discovery versus verification
Verification is straightforward once a good certificate is known. Discovery is the difficult part: find a curve with a suitably factorable candidate order.
The original Goldwasser–Kilian approach can use point-counting algorithms. Atkin–Morain ECPP uses complex multiplication (CM) theory to construct curves whose orders are known candidates derived from quadratic forms and discriminants.
This makes practical ECPP a synthesis of algebraic number theory, quadratic forms, modular arithmetic and elliptic curves.
12. The CM order equation
For a suitable negative discriminant D, ECPP searches for integers u,v satisfying a norm-form relation of the shape
4N = u² + |D|v²
under the appropriate discriminant conventions.
Possible elliptic-curve traces are related to ±u, giving candidate curve orders
m = N+1−t.
One then factors m enough to expose a large probable-prime factor q satisfying the fourth-root bound.
The exact CM cases depend on D and the order being used; this equation is the conceptual entry point rather than a complete implementation specification.
13. Hilbert class polynomials and j-invariants
CM theory associates a Hilbert class polynomial H_D whose roots are j-invariants of elliptic curves with complex multiplication by the order of discriminant D.
Reduce H_D modulo N and find an appropriate root j. Construct a curve with that j-invariant modulo N, then choose the twist whose order corresponds to the desired candidate m.
For large discriminants, computing or evaluating class polynomials efficiently is itself a significant algorithmic task.
14. Why class groups reappear
Hilbert class polynomials have degree equal to the class number of the imaginary quadratic order.
The binary quadratic forms and class groups from Guide 17 therefore sit directly inside practical ECPP curve construction.
What looked like a separate algebraic-number-theory branch becomes part of a primality-proving engine.
15. Factoring the candidate order
ECPP does not necessarily require complete factorisation of m. It needs enough known factorisation to isolate a large prime or recursively provable factor q satisfying the theorem.
ECM is particularly useful here because candidate curve orders often need medium-factor extraction. Thus the factorisation algorithm from Guide 21 can support the primality algorithm in this guide.
Algorithmic components often return as dependencies in the opposite direction from where they were first introduced.
16. A verifier’s checklist
For each certificate step, verify:
N > 1 and gcd(N,6)=1 curve discriminant coprime to N P lies on E modulo N q is prime (recursively or directly) q divides m q > (N^(1/4)+1)² [m]P = O [m/q]P has projective Z coprime to N.
Then continue to the certificate for q.
This is far simpler than reproducing CM polynomial selection and curve search.
17. Certificate data should be explicit
A usable certificate needs enough information to reconstruct every check: N, curve coefficients, point coordinates, m, q and the recursive child certificate.
If curve models or transformations are used, the verifier must know the exact model and mapping conventions.
An undocumented integer tuple is not a certificate merely because a particular program can read it.
18. ECPP versus AKS
AKS gives a deterministic polynomial-time primality test with a landmark theoretical guarantee. Practical large-number proving often favours certificate methods such as ECPP because the proofs can be short and independently verifiable.
The comparison is not prime versus composite correctness—both are exact when implemented correctly. It is a comparison of practical algorithms, constants, certificate structure and proof-generation cost.
19. ECPP versus probable-prime testing
Probable-prime tests are excellent filters. They quickly reject most composites and make it sensible to invest in certificate generation only for strong candidates.
ECPP then turns that candidate into a proof.
A good pipeline may therefore be:
trial division / small-prime sieve → probable-prime tests → ECPP certificate generation → independent certificate verification.
20. Failure modes can reveal compositeness
During curve construction or point arithmetic, a modular inverse may fail. Taking gcd with N can reveal a factor.
A candidate order may refuse to yield a sufficiently large prime factor. That usually means try another discriminant or curve, not declare N composite.
A recursive q may turn out composite under further testing. Then discard that branch and search again.
21. Proof generation is not proof verification
The generator may use probabilistic searches, numerical approximations to class invariants and large database-style precomputation.
The final verifier should rely on exact modular identities, integer inequalities and recursively certified primes.
This separation lets independent software verify a certificate produced by a much more complicated program.
22. Common mistakes
1. Calling a probable prime an ECPP-proved prime. 2. Forgetting to recursively prove q. 3. Checking only [m]P=O and not the large-prime order condition. 4. Omitting the Hasse-derived size bound.
5. Ignoring a nontrivial gcd arising during projective arithmetic. 6. Assuming the verifier must recount #E. 7. Treating a failed curve search as evidence N is composite. 8. Publishing a certificate without its curve model and coordinate conventions.
23. Practice set
1. What is the difference between probable-prime testing and proving? 2. State the prime-q elliptic-curve criterion. 3. Explain the fourth-root bound using Hasse. 4. Verify that (1,45) lies on y²=x³+x+3 mod101.
5. Factor 87. 6. Check that q=29 exceeds the ECPP bound for 101. 7. Which point equals [3]P in the worked example? 8. What is [87]P?
9. Why does an affine nonidentity [3]P satisfy the projective gcd condition? 10. Must a verifier recount all curve points? 11. What is the role of CM? 12. What does a Hilbert class polynomial provide?
13. Why do class groups appear in ECPP? 14. Why is ECM useful inside ECPP discovery? 15. What terminates the recursive chain? 16. What must be independently checked for the final certificate?
24. Answers
1. A probable-prime test gives strong evidence; a proof provides exact independently verifiable conditions. 2. Find prime q|m with q>(N^(1/4)+1)², [m]P=O and [m/q]P nonidentity with the required projective gcd condition. 3. Any composite N has p≤√N, so Hasse gives #E(F_p)≤(N^(1/4)+1)², contradicting divisibility by larger q.
4. Both sides are 5 mod101. 5. 87=3·29. 6. The bound is about17.4, so 29 qualifies. 7. (4,24). 8. The identity O.
9. Its projective Z-coordinate can be taken as one, whose gcd with101 is one. 10. No. 11. It constructs curves with controlled candidate orders without generic point counting. 12. CM j-invariants for curves associated with a chosen discriminant.
13. Hilbert class polynomial degree and CM structure are controlled by imaginary quadratic ideal/form classes. 14. Candidate orders need partial factorisation to expose a large q. 15. A small terminal prime checked directly. 16. Every curve, point, scalar relation, gcd condition, size bound and child prime in the recursive chain.
Sources and further study
A. O. L. Atkin and François Morain, Elliptic curves and primality proving, Mathematics of Computation 61 (1993), 29–68, describes practical ECPP. For an algorithmic treatment of the certificate criterion, see modern computational-number-theory texts and PARI/GP’s primality-certificate documentation.
Computational Number Theory — Batch 06
Guide 21: Elliptic Curve Method (ECM) for Integer Factorisation
Guide 22: Quadratic Sieve, Factor Bases, Smooth Relations and Linear Algebra
Guide 23: Number Field Sieve, Polynomial Selection, Sieving and Square Roots
Guide 24: Elliptic Curve Primality Proving (ECPP) and Verifiable Prime Certificates