An accepted elliptic curve primality certificate proves its recorded integer prime in Mathlib. The sole premise is the checker equation: the smaller primes, curve nonsingularity, point order and Hasse-bound size condition are all verified by the certificate and soundness proof.
6.8. The Mathlib correspondence
The soundness theorem connects the executable checker to Mathlib's
Nat.Prime. Its only premise is that the checker accepts the
certificate; it does not require a separate assumption that any
proposed curve order, auxiliary prime or search result is correct.
example (c : Hex.ECPP.Cert)
(h : Hex.ECPP.check c = true) : Nat.Prime c.subject :=
Hex.ECPP.natPrime_of_check h
example (n : Nat) (c : Hex.ECPP.Cert)
(h : Hex.ECPP.checkAt n c = true) : Nat.Prime n :=
Hex.ECPP.natPrime_of_checkAt h
Hex.ECPP.natPrime_of_check {cert : Hex.ECPP.Cert} (h : Hex.ECPP.check cert = true) : Nat.Prime cert.subjectHex.ECPP.natPrime_of_check {cert : Hex.ECPP.Cert} (h : Hex.ECPP.check cert = true) : Nat.Prime cert.subject
Hex.ECPP.natPrime_of_checkAt {n : ℕ} {cert : Hex.ECPP.Cert} (h : Hex.ECPP.checkAt n cert = true) : Nat.Prime nHex.ECPP.natPrime_of_checkAt {n : ℕ} {cert : Hex.ECPP.Cert} (h : Hex.ECPP.checkAt n cert = true) : Nat.Prime n
If checkAt n cert = true, then n is prime. The checker verifies both
the certificate and that its recorded integer is n; no additional
assumption about search, curve orders or auxiliary primes is required.
The proof follows the mathematical argument given above. For every
prime divisor p of the candidate integer, it interprets the
coordinates as Mathlib points on an elliptic curve over ZMod p.
Hex.ECPP.startingPoint_rep shows that the starting point
is not the identity; Hex.ECPP.add_rep shows that each
accepted addition agrees with Mathlib's group law.
Hex.ECPP.replay_zero then identifies the computed scalar
multiple with q • Q = 0 in that group.
The order of the point divides the number of points on the curve.
The bound supplied by Hex.ECPP.hasse_sq_zmod contradicts
the existence of a prime divisor at most √n. The Hasse theorem
is imported from the TauCeti project. Its
dependencies, and those of the primality theorems, are audited to
allow only Lean's standard propext, Classical.choice and
Quot.sound axioms.
The companion also relates the curve's points over the prime field
to points fixed by Frobenius over any extension field, in particular
an algebraic closure. The
equivalences Hex.ECPP.rationalPointsEquivFixed and
Hex.ECPP.rationalPointsEquivKer express that correspondence
as fixed points and as the kernel of 1 - Frobenius, respectively.
Certificate search runs during elaboration, but its computations
are not trusted as proofs. The generated data is turned into
explicit certificate constructors. Lean's kernel checks the
equation asserting that the checker returns true, and the proved
soundness theorem supplies Nat.Prime n. The native and PARI
routes check the exact saved certificate before suggesting it or
writing an export file.
For users of the computational API, Hex.ECPP.produce_ok
and Hex.ECPP.convert_ok establish that successful search
and conversion results pass the checker. The unconditional
primality implication remains in the theory companion, where
the elliptic curve and Hasse arguments are available.
For more on the mathematics, see
Sutherland's notes on elliptic curve primality proving.
For the external certificate format, see
PARI's primecert documentation.