5.5. Reusable certificates with primality?
The explicitly requested construction tactic primality? uses a larger,
finite search profile. It proves the Curve25519 field prime and offers a
clickable Try this: replacement containing the complete checked certificate.
This example checks the entire suggestion text, so changes to the generated
certificate or its formatting are detected:
/--
info: Try this:
[apply] exact
Hex.Nat.prime_of_checkPrimeAt (c :=
Hex.Nat.PrimeCert.pock 57896044618658097711785492504343953926634992332820282019728792003956564819949
[(2, 0,
Hex.Nat.PrimeCert.pock3 74058212732561358302231226437062788676166966415465897661863160754340907
2028478494862525422475607 22304740449229861598212 2028478494862525422475606
[(2, 0, Hex.Nat.PrimeCert.small 2), (2, 0, Hex.Nat.PrimeCert.small 353),
(2, 0, Hex.Nat.PrimeCert.small 57467),
(2, 0,
Hex.Nat.PrimeCert.pock3 31757755568855353 4028945 289 4028944
[(5, 2, Hex.Nat.PrimeCert.small 2), (2, 0, Hex.Nat.PrimeCert.small 223),
(2, 0, Hex.Nat.PrimeCert.small 4153)])])])
(by decide +kernel)
-/
#guard_msgs in
example : Hex.Nat.Prime (2 ^ 255 - 19) := ⊢ Hex.Nat.Prime (2 ^ 255 - 19)
All goals completed! 🐙
Apply the suggestion to keep certificate search out of subsequent builds. The
replacement uses Hex.Nat.prime_of_checkPrimeAt and decide +kernel;
the kernel still replays the certificate. A standalone file containing the
replacement needs only import HexPrimality.Cert. The goal retains the
expression 2 ^ 255 - 19. With HexPrimalityTheory imported, primality?
also handles Nat.Prime and suggests the corresponding bridge theorem.
Construction supports inputs through 521 bits, recursive depth 32, and a
shared limit of 1024 attempts. primality? (maxAttempts := 29) sets a smaller
limit; with only HexPrimality imported, Curve25519 succeeds at 29 and
exhausts at 28. It uses
stage-one Pollard p - 1 up to 524288, bounded rho work, and deterministic
small witnesses before random candidates. Every limit is finite; exhaustion
reports the seed, attempts, and resource profile. Success depends on finding
enough factors of predecessors for Pocklington, rather than on bit length
alone. Construction first tries the factors found by table division before
running the more expensive factor search. It can use a power of two alone and
can trade up to 63 small-divisor checks for a smaller factored part of the
predecessor. These checks are included in the reusable certificate and replayed
by the kernel. The ordinary primality policy keeps its existing smaller budget.
With import HexIntFactor, plain primality? uses a stronger search that
combines Pollard's p - 1 method with elliptic-curve factorization (ECM).
Both methods look for factors of the predecessors needed by Pocklington;
ECM here is a factoring algorithm, distinct from the elliptic-curve primality
certificates described in the ECPP chapter. The search
retains factors as it finds them and changes methods according to the size
of the remaining composite. It stops when it has enough factors for the
primality criterion, then recursively proves the primality of those factors.
This import selects the stronger provider before construction begins. One
search shares the same 1024 attempts across factoring, recursive proofs and
witnesses. It discovers certificates for secp256k1, P-384 and Curve448 without
supplied factors or curve parameters. See the
field-prime tutorial for complete examples.
The tutorial uses a finite maxHeartbeats allowance of 4000000. Exhaustion
means that this search failed within its allowance; it does not show that
the number is composite. Native search runs synchronously, so heartbeats
are not a wall-clock timeout.
Importing only HexPrimality retains the smaller portfolio described above,
including Curve25519's 29-attempt construction. With HexIntFactor, that
certificate is unchanged and takes 31 attempts. An explicit factor :=
provider or a supplied using certificate bypasses automatic selection.
Use primality? (factor := Hex.Nat.Construction.factorSearch) to select the
core route, or primality? (factor := Hex.Nat.interleavedConstructionFactor)
to select the stronger route explicitly. Ordinary primality keeps its
separate search policy.
A comparison tested the stronger native search on 300 independently generated
primes: 75 each at 128, 256, 384 and 512 bits, with a 180-second limit per search. It
constructed 186 certificates, compared with 138 for the previous automatic
Hex policy and 170 for PrimeCert with SymPy. Every successful certificate
was replayed by the Lean kernel. These are observations on a fixed corpus
and shared host, not completeness or latency guarantees. In particular,
at 512 bits, 12 searches succeeded, 12 exhausted their schedules and 51 hit
the 180-second process limit. The tactic has no such timeout and can take
more than three minutes on difficult inputs. A smaller maxAttempts or the
explicit core-only provider reduces the search allocation; neither is a
wall-clock limit.
On one unsuccessful 507-bit subject, two native trials of the stronger search
completed in about 147 seconds, while two reached the 180-second process limit.
The previous policy exhausted in 18–21 seconds in all four trials. These
paired failure measurements
illustrate the cost of the larger search; a timeout does not establish exhaustion.
The comparison report contains all samples, failures, exact certificates and reproduction instructions.
The Curve25519 result has three non-leaf certificate nodes and eight factor entries. Kernel replay reads the already verified sieve bitset for table leaves, and compiled prime enumeration reads 64 candidate bits at a time. Both changes are proved equal to their original implementations.
The fixed-corpus comparison measured Curve25519 native decision at
0.57 seconds and a fresh complete primality? build from its numeral at
1.63 seconds, including Lake overhead and kernel replay. Paired runs using
the original 2 ^ 255 - 19 expression took 2.17–2.29 seconds, compared with
7.01–10.41 seconds before these optimizations. FLINT and PARI native decisions
took 25.9 and 55.4 milliseconds respectively. The native timings use a
standalone executable; the complete tactic build also includes interpreted
core search, elaboration and kernel checking. Importing the precompiled
HexIntFactor producer selects native execution as well as a stronger policy. These measurements use the revisions pinned in the
report, rather than the current stronger search policy. All completed samples are
retained. These are host-specific observations, not latency guarantees. The
measurement report
records every sample, certificate sizes, and the comparison with the larger
reference certificate.
The fixed comparison corpus also includes standard cryptographic field
primes. The current construction profile finds P-256 and the structured
511/512-bit benchmark primes and P-521. The core-only profile exhausts on
secp256k1, P-384 and Curve448. Importing HexIntFactor enables all three:
see the field-prime tutorial for complete
examples and reusable proofs. The core-only P-521 construction uses 25 factor candidates and 170 attempts; the constructor
admits at most 32 factors and still examines at most 4096 subsets. For the
expression 2 ^ 521 - 1, set local maxRecDepth to 1024 and
exponentiation.threshold to 521; its numeral needs neither option.
The standard-field report
records the default profile's factoring barriers and separate construction, rendering,
and replay measurements. This is not a general-purpose prover for
arbitrary cryptographic-size primes.
The first cactus plot compares native exact primality decisions with the
complete primality? build. Native timings exclude Lean proof emission and
kernel replay, imports, and input conversion. Hex uses certificate
construction and a compiled self-check internally to decide primality;
FLINT and PARI return exact decisions through their native algorithms. The
dashed curve includes the full fresh Lake build: certificate construction,
proof emission, imports, and kernel checking.
Direct kernel measurements exclude imports, search, and proof elaboration. They check complete proof bodies, including expanded local auxiliary proofs. With PrimeCert’s fixed-window powering and the same selected Pocklington factors, supplied Curve25519 replay takes about 4.54 milliseconds for Hex and 3.54 milliseconds for PrimeCert on the recorded host. Curve448 takes 9.30 and 6.44 milliseconds. PrimeCert uses common witness bases; a separate matched-base experiment distinguishes that certificate choice from checker cost.
Complete automatic construction is a separate comparison. On the matched
Curve25519 Nat.Prime goal, the repeated fresh-module experiment measures
about 2.39 seconds for Hex primality? and 3.55 seconds for PrimeCert
prime_cert?, including imports, construction, elaboration, and checking.
These noisy shared-host observations are not portable performance promises.
The replay attribution
records exact revisions, every sample, component costs, negative controls,
and construction regression checks. Hex uses Lean 4.34.0 and PrimeCert uses
Lean 4.33.0; identical-code calibration is reported separately.
The kernel replay comparison uses a supplied Curve448 certificate in both systems.
The search in the field-prime tutorial
constructs its own certificate. Those replay measurements use a small,
structured corpus; the independent comparison above tests broader search coverage.