hex

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.