6.1. Introduction
How can we prove that a large integer is prime without trying every
possible divisor? Elliptic curve primality proving, or ECPP, uses
arithmetic on elliptic curves to build such a proof. Hex can search for
these proofs and turn them into Lean theorems of the form Nat.Prime n.
You can also save a proof's mathematical data and check it again in a
later build, without repeating the search.
The idea is to find a curve and a point whose order is a sufficiently
large prime q. If the integer n we want to prove prime were composite,
it would have a prime divisor p ≤ √n. Reducing the curve and point
modulo p would force the curve to have too many points over the finite
field with p elements, contradicting Hasse's bound. The primality of
q is proved in turn, giving a chain that ends with primes we can check
by simpler methods.
Factorization enters when searching for a suitable q: we partially
factor a proposed curve order and look for a large prime factor. This
gives ECPP a choice of auxiliary integers to factor, from different
curves. It complements the Pocklington method in
HexPrimality, which uses factors of n - 1.
A primality certificate is the finite collection of curves, points, auxiliary prime certificates and modular arithmetic witnesses needed to verify the argument. Finding a certificate may be difficult; checking one does not require repeating that search. Hex provides a built-in search and an optional connection to PARI/GP. Both produce certificates that Lean checks before accepting a primality theorem.
For Mathlib users, the main entry points are:
Import | What it provides |
|---|---|
| Proofs from previously supplied certificates. |
| Built-in search for a certificate, followed by a proof. |
| Certificate search using the external PARI/GP program, followed by a proof. |
The computational library HexECPP supplies the certificate checker
and built-in search without importing Mathlib. Its companion
HexECPPTheory connects the calculation to Mathlib's elliptic curves
and supplies the theorem that accepted certificates prove primality.