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
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
All goals completed! 🐙
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.