hex

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
🔗theorem
Hex.ECPP.natPrime_of_check {cert : Hex.ECPP.Cert} (h : Hex.ECPP.check cert = true) : Nat.Prime cert.subject
Hex.ECPP.natPrime_of_check {cert : Hex.ECPP.Cert} (h : Hex.ECPP.check cert = true) : Nat.Prime cert.subject

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.

🔗theorem
Hex.ECPP.natPrime_of_checkAt {n : ℕ} {cert : Hex.ECPP.Cert} (h : Hex.ECPP.checkAt n cert = true) : Nat.Prime n
Hex.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.