hex

6.1. Introduction🔗

How can we prove that a large integer is prime without trying every possible divisor? Elliptic curve primality proving, or ECPP, uses arithmetic on elliptic curves to build such a proof. Hex can search for these proofs and turn them into Lean theorems of the form Nat.Prime n. You can also save a proof's mathematical data and check it again in a later build, without repeating the search.

The idea is to find a curve and a point whose order is a sufficiently large prime q. If the integer n we want to prove prime were composite, it would have a prime divisor p ≤ √n. Reducing the curve and point modulo p would force the curve to have too many points over the finite field with p elements, contradicting Hasse's bound. The primality of q is proved in turn, giving a chain that ends with primes we can check by simpler methods.

Factorization enters when searching for a suitable q: we partially factor a proposed curve order and look for a large prime factor. This gives ECPP a choice of auxiliary integers to factor, from different curves. It complements the Pocklington method in HexPrimality, which uses factors of n - 1.

A primality certificate is the finite collection of curves, points, auxiliary prime certificates and modular arithmetic witnesses needed to verify the argument. Finding a certificate may be difficult; checking one does not require repeating that search. Hex provides a built-in search and an optional connection to PARI/GP. Both produce certificates that Lean checks before accepting a primality theorem.

For Mathlib users, the main entry points are:

Import

What it provides

HexECPPTheory

Proofs from previously supplied certificates.

HexECPPTheory.Native

Built-in search for a certificate, followed by a proof.

HexECPPTheory.Pari

Certificate search using the external PARI/GP program, followed by a proof.

The computational library HexECPP supplies the certificate checker and built-in search without importing Mathlib. Its companion HexECPPTheory connects the calculation to Mathlib's elliptic curves and supplies the theorem that accepted certificates prove primality.