hex

6.4. What a primality certificate contains🔗

The type Hex.ECPP.Cert represents either a certificate from HexPrimality or an elliptic curve step with a certificate for its auxiliary prime. Here is a complete elliptic curve certificate for 17:

namespace HexECPPChapter def certificate : Hex.ECPP.Cert := .step 17 2 3 3 6 6 [10, 13, 3, 13] (.base (.small 11)) example : Nat.Prime 17 := ⊢ Nat.Prime 17 All goals completed! 🐙

The curve is y² = x³ + 2x + 3 modulo 17, and the point is Q = (3, 6). The smaller prime is 11, certified by .small 11. The final 6 before the list is an inverse of 4 · 2³ + 27 · 3² modulo 17. The list contains the inverses used in calculating 11 • Q. The checker verifies each inverse and that the calculation ends at infinity. No claimed curve order needs to be included.

An inverse is supplied as a witness so that checking a division needs only a modular multiplication: to justify dividing by d, we supply u and check d u = 1 modulo n. This matters while primality is still unknown, since division by an arbitrary nonzero residue modulo a composite integer is not valid.

The ecpp using tactic reads the certificate's constructor data, checks that it is for the integer in the goal, and produces a proof using the soundness theorem. A stored certificate must consist of data, with no uncomputed search calls or local hypotheses.

6.4.1. Checking a certificate as a computation🔗

The computational checker can also be called directly:

#guard Hex.ECPP.checkAt 17 certificate #guard !Hex.ECPP.checkAt 19 certificate

The first check accepts the certificate for 17. The second rejects it because this certificate says nothing about the primality of 19. The certificate itself records the integer whose primality it proves.

🔗def
Hex.ECPP.check : Hex.ECPP.Cert → Bool
Hex.ECPP.check : Hex.ECPP.Cert → Bool

Verify a primality certificate, including every smaller prime it uses.

For an elliptic curve step, verify the curve equation, nonsingularity, the strict size bound on the auxiliary prime, and scalar multiplication to infinity using the supplied modular inverses. For a HexPrimality certificate, use its existing primality checker.

In HexECPPTheory, natPrime_of_check proves that a true result implies Nat.Prime cert.subject.

🔗def
Hex.ECPP.checkAt (n : ℕ) (cert : Hex.ECPP.Cert) : Bool
Hex.ECPP.checkAt (n : ℕ) (cert : Hex.ECPP.Cert) : Bool

Verify that cert is a valid primality certificate for the integer n. Return false if it records a different integer, even when its own certificate is valid. In HexECPPTheory, natPrime_of_checkAt turns a true result into a theorem of Nat.Prime n.

Each elliptic step verifies the curve equation, nonsingularity, the size of the auxiliary prime, and every addition in the scalar calculation. It also checks the auxiliary prime's certificate. Coordinates and inverse witnesses must be residues between 0 and n - 1, and the calculation must use exactly the supplied inverses.

The real-valued size condition above is implemented with exact integer inequalities. With r = q - 1, the checker requires n < r² and 16 n q < (r² - n)². These are equivalent to the stated size condition for q ≥ 2; equality is not enough for this argument.

🔗def
Hex.ECPP.sizeBound (n q : ℕ) : Bool
Hex.ECPP.sizeBound (n q : ℕ) : Bool

Check the auxiliary prime size needed for the Hasse-bound argument. For q ≥ 2, this is the exact integer form of q > (n^(1/4) + 1)²: require n < (q - 1)² and 16*n*q < ((q - 1)² - n)². Strict inequalities are necessary to exclude a prime divisor of n at most √n.