hex

6.2. Proving primality in Lean🔗

Import HexECPPTheory.Native to ask Hex to find a certificate. The following example proves a 128-bit integer prime, using only the integer and a seed for the search:

example : Nat.Prime 177080666831933235355717939809840315427 := ⊢ Nat.Prime 177080666831933235355717939809840315427 Try this: [apply] ecpp using (ecpp_cert% "[[177080666831933235355717939809840315427,22472724743198264575,1,0,[86164193070500362417515215910064042752,63397728334770895955153524595593363575]],[177080666831933235333245215066642050853,177080666831933131533758370604197850807,1,0,[164825611451126091799850548711750959219,98072604898189975086589005997013690405]],[103799486844462444200047,103799486478864084196705,1,0,[91012759805143373526374,27884036705291358950654]]]" using Hex.Nat.PrimeCert.pock3 365598360003343 40853 36077 40849 [(3, 0, Hex.Nat.PrimeCert.small 2), (2, 0, Hex.Nat.PrimeCert.small 35591)])All goals completed! 🐙

The tactic closes the goal and offers a Try this: replacement containing the certificate it found. Apply that suggestion to save the certificate in your proof. Subsequent builds then check the saved data instead of searching for it again.

Here is the same workflow for 17, small enough that we can display the whole suggestion:

example : Nat.Prime 17 := ⊢ Nat.Prime 17 Try this: [apply] ecpp using (ecpp_cert% "17" using Hex.Nat.PrimeCert.small 17)All goals completed! 🐙
Try this:
  [apply] ecpp using (ecpp_cert% "17" using Hex.Nat.PrimeCert.small 17)

The replacement is a complete proof:

example : Nat.Prime 17 := ⊢ Nat.Prime 17 All goals completed! 🐙

This small example uses a direct small-prime certificate. Larger examples can contain elliptic curve steps, as we will see below. A file using the saved replacement only needs import HexECPPTheory; neither the optional search import nor an external program is needed to check it.

Search is requested explicitly with (method := ecpp). Importing the library does not change what ordinary primality or norm_num does. The integer in the goal must be a closed expression that Lean can reduce to a numeral, such as a literal or 2 ^ 127 - 1.