hex

6.7. Search limits and unsuccessful attempts🔗

Certificate search tries finitely many curves, points and auxiliary factorizations. It can stop without finding a proof, even when the integer is prime. An exhausted search therefore proves nothing about compositeness. Its error reports the unresolved integer and the stage or limit at which the search stopped.

The built-in search accepts integers through 256 bits by default. Select the larger policy with primality? (method := ecpp) (bits := 512) (seed := 0) for integers through 512 bits. In an export command, put (bits := 512) before the optional seed in the same way. The 512-bit policy tries an additional collection of curves from fixed linear and quadratic class polynomials. Neither policy guarantees success for every prime within its size limit; production above 512 bits is unsupported.

The seed controls the search's point and witness choices. Reusing the same seed makes the search reproducible. Changing it may find a certificate when an earlier attempt failed. It does not change which certificates the checker accepts.

Checking supplied certificates has separate limits. The public proof commands accept integers through 512 bits, at most 20 compact elliptic rows, and at most 32 certificate nodes in total. That total includes the elliptic steps, the wrapper around the last HexPrimality certificate, and every node of that certificate. There are also limits on the amount of source text and the number of modular inverses. These keep parsing and proof construction finite; the 512-bit search accounts for the row and node limits while trying alternative certificates.

6.7.1. Calling the search from a program🔗

The function Hex.ECPP.produce returns the certificate and search statistics, or a failure with its diagnostic. Its Hex.ECPP.SearchBudget argument controls the work allowed for the whole search, including the recursive proofs of smaller primes. Work already spent on an unsuccessful curve remains counted when the search moves to another curve.

open Hex.ECPP in #guard (produce 17 0).result.toOption.any (checkAt 17)
🔗def
Hex.ECPP.produce (n seed : ℕ) (budget : Hex.ECPP.SearchBudget := { }) : Hex.ECPP.SearchResult
Hex.ECPP.produce (n seed : ℕ) (budget : Hex.ECPP.SearchBudget := { }) : Hex.ECPP.SearchResult

Search for a primality certificate for n, using seed to choose the deterministic random sequence and budget to limit the work. Return a certificate and search statistics, or an error explaining why search stopped. Every .ok c result satisfies checkAt n c = true; failure to find a certificate does not imply that n is composite.

The default policy admits inputs through 256 bits. native512Budget and public512Budget explicitly select 512-bit search. For a theorem of Mathlib's Nat.Prime n, use HexECPPTheory.Native or apply the companion's soundness theorem to a kernel-checked checker equation.

The function's .ok result is a checked certificate. A Lean theorem of primality is obtained by applying the companion's soundness theorem to the checker equation, as described below.

6.7.2. Limits when importing certificate text🔗

Hex.ECPP.ImportBudget controls how much input a conversion may process: the length of the text, the number and size of the integers and rows, and the work spent calculating inverses or proving the last prime. The standard Hex.ECPP.defaultImportBudget is used by ecpp_cert%. The input is checked against these limits before expensive conversion or prime search begins.

🔗structure

Limits on the input and work allowed when importing a primality certificate from PARI text. These bound parsing, point calculations and optional search for a proof of the last prime. Exceeding a limit returns an error; it does not imply that the intended integer is composite.

maxInputBytes : ℕ

Maximum certificate text length in UTF-8 bytes, checked before parsing.

maxDigits : ℕ

Maximum digits in a supplied decimal integer, checked before allocating it.

maxRows : ℕ

Maximum number of elliptic curve steps in the supplied certificate.

maxIntegerBits : ℕ

Maximum bit length of the magnitude of any supplied integer, including coordinates.

maxScalarBits : ℕ

Maximum bit length of the cofactor or auxiliary prime used to multiply a point.

maxInverseOps : ℕ

Maximum divisions requiring a modular inverse in one scalar multiplication.

maxEndpointFuel : ℕ

Maximum search fuel a caller may request for proving the last prime in the chain.

For a program that needs to read the format separately, Hex.ECPP.parsePari parses the certificate and Hex.ECPP.preflight checks its size limits. Hex.ECPP.convertCounted can search for the proof of the last prime when that proof has not been supplied. The saved compact notation always supplies it explicitly, so checking a saved proof does not need that search.