38.5. Proving the secp256k1, P-384 and Curve448 field primes
The field primes for secp256k1, P-384 and Curve448 have short formulas but hundreds of bits. Hex can discover primality certificates for all three and prove them in Lean. You supply the number, and the tactic finds the factors and recursively proves the smaller primality statements it needs.
38.5.1. Start here
Use a checkout of the
hex-dev repository. The ECM provider is
part of HexIntFactor, which is not yet included in the published split
libraries. Start a Lean file with these imports:
import HexIntFactor
The examples use Hex.Nat.Prime, so they need no Mathlib import.
To state the same goals with Nat.Prime, also import HexPrimalityTheory.
The same tactic syntax then applies.
Put the examples in a section with local options:
section
set_option maxHeartbeats 4000000
The finite heartbeat allowance accommodates certificate construction. All three examples pass with this option alone; it is a tested allowance, not a measured minimum. It does not increase the factor search's shared 1024-attempt budget. Lean may warn that the powers with exponents 384 and 448 exceed its shortcut threshold of 256. The goals still normalize and the proofs succeed; these examples leave that warning visible.
38.5.2. Three proofs
The secp256k1 field prime is 2^256 - 2^32 - 977:
example : Hex.Nat.Prime (2 ^ 256 - 2 ^ 32 - 977) := by primality?
The P-384 field prime is 2^384 - 2^128 - 2^96 + 2^32 - 1:
example : Hex.Nat.Prime
(2 ^ 384 - 2 ^ 128 - 2 ^ 96 + 2 ^ 32 - 1) := by
primality?
The Curve448 field prime is 2^448 - 2^224 - 1:
example : Hex.Nat.Prime (2 ^ 448 - 2 ^ 224 - 1) := by primality?
Close the section after the examples:
end
Each proof produces a Try this: suggestion containing a complete
certificate. Apply the suggestion to replace the search with a proof that
replays that certificate. This is particularly useful when sharing a file:
other people can check the proof without repeating the factor search.
The standard import selects a search combining Pollard's p - 1 method
and elliptic-curve factorization (ECM). It factors the predecessors needed
by Pocklington and recursively proves the smaller primes. This is different
from using an elliptic curve directly to certify primality through ECPP.
The entire construction shares one 1024-attempt allowance and one advancing
random state. You do not need to supply factors, curve parameters, seeds or
certificates. Apply the suggested proof to avoid repeating this search.
The expert override
primality? (factor := Hex.Nat.interleavedConstructionFactor) selects the
same provider explicitly. Use
primality? (factor := Hex.Nat.Construction.factorSearch) for the core-only
route. The original fixed-curve provider remains available through
primality? (factor := Hex.Nat.ecmFactorSearch) for explicit comparisons.
If Lean reports a heartbeat limit, include the local option from the setup. A message saying that certificate construction exhausted its search instead means that its schedule or attempt allowance ran out. It identifies the unresolved subject; it does not show compositeness. The factor-search reference describes the default schedule and the optional arguments of the explicit providers.
Build note: the three construction examples and their exact Try this:
suggestions are checked in
the field construction tests.
Run lake build HexIntFactorFieldConformance to check them together.
The manual build checks the saved proof below without repeating the searches.
38.5.3. What the saved proof looks like
Here is a saved secp256k1 certificate in full, with abbreviated constructor
names. This standalone proof needs only import HexPrimality.Cert and uses the
numeral to avoid the options for normalizing powers:
example : Hex.Nat.Prime
115792089237316195423570985008687907853269984665640564039457584007908834671663 := ⊢ Hex.Nat.Prime 115792089237316195423570985008687907853269984665640564039457584007908834671663
exact Hex.Nat.prime_of_checkPrimeAt (c :=
.pock 115792089237316195423570985008687907853269984665640564039457584007908834671663
[(2, 0,
.pock 205115282021455665897114700593932402728804164701536103180137503955397371
[(2, 0,
.pock3 255515944373312847190720520512484175977
185873736969223 6447496504 185873736969222
[(3, 2, .small 2), (2, 0, .small 4423),
(2, 0, .small 41201), (2, 0, .small 96557)])])])
(⊢ ((Hex.Nat.PrimeCert.pock 115792089237316195423570985008687907853269984665640564039457584007908834671663
[(2, 0,
Hex.Nat.PrimeCert.pock 205115282021455665897114700593932402728804164701536103180137503955397371
[(2, 0,
Hex.Nat.PrimeCert.pock3 255515944373312847190720520512484175977 185873736969223 6447496504
185873736969222
[(3, 2, Hex.Nat.PrimeCert.small 2), (2, 0, Hex.Nat.PrimeCert.small 4423),
(2, 0, Hex.Nat.PrimeCert.small 41201), (2, 0, Hex.Nat.PrimeCert.small 96557)])])]).subject ==
115792089237316195423570985008687907853269984665640564039457584007908834671663 &&
Hex.Nat.checkPrime
(Hex.Nat.PrimeCert.pock 115792089237316195423570985008687907853269984665640564039457584007908834671663
[(2, 0,
Hex.Nat.PrimeCert.pock 205115282021455665897114700593932402728804164701536103180137503955397371
[(2, 0,
Hex.Nat.PrimeCert.pock3 255515944373312847190720520512484175977 185873736969223 6447496504
185873736969222
[(3, 2, Hex.Nat.PrimeCert.small 2), (2, 0, Hex.Nat.PrimeCert.small 4423),
(2, 0, Hex.Nat.PrimeCert.small 41201), (2, 0, Hex.Nat.PrimeCert.small 96557)])])])) =
true All goals completed! 🐙)
The kernel checks the certificate through
Hex.Nat.prime_of_checkPrimeAt. The search is untrusted: finding a
factor is not enough to establish primality, and every necessary recursive
certificate must pass the same checker. The
earlier saved certificates
also include P-384 and the original Curve448 certificate; the current
Curve448 suggestion uses a different, equally kernel-checkable certificate.
38.5.4. How long does it take?
Allow a few minutes to try all three searches in Lean. Construction and its factor provider run natively during elaboration; the complete module build also includes imports, certificate rendering and kernel checking.
In the paired field-prime comparison, native search medians were about 35.6 seconds for secp256k1, 2.4 seconds for P-384 and 5.0 seconds for Curve448. These measurements use the policy selected by the examples above, but exclude imports, Lean proof rendering, elaboration and kernel replay. They are observations on a shared host, not time limits or guarantees. The factor-policy report records every trial and the paired comparison with the previous policy.
Earlier complete-module and direct-kernel measurements used the previous core-first search and its saved certificates. The construction report and ECM report retain those measurements, with their exact revisions and separate costs.
The native search is synchronous. Lean can report a heartbeat overrun only
after that computation returns; the heartbeat allowance is not a wall-clock
timeout. The finite attempt limit bounds the search schedule. Difficult inputs can
take more than three minutes; the comparison runner's 180-second process
limit does not apply to the tactic. Use a smaller maxAttempts allocation
when you want less search work, then save successful suggestions for replay.
The search has a fixed, bounded schedule and can still exhaust on other primes. The primality construction reference explains reusable certificates and the available budget override.