hex

6.6. Using PARI/GP🔗

PARI/GP is an external computer algebra system with its own elliptic curve primality prover. Import HexECPPTheory.Pari and install its gp executable on your PATH to use it for certificate search. Then write primality? (method := pari) in a primality proof. Hex asks GP for a certificate, converts the result, and checks it before accepting the proof or offering a saved replacement.

This route requires a POSIX system for generation. Once the certificate is saved, it is ordinary Lean data: checking it does not require GP. The export command for this route is #ecpp_export MyCertificates.Prime cert for 17, with the same build-and-import workflow as above.

6.6.1. Using an existing PARI certificate🔗

If you already have PARI certificate text, you can use ecpp_cert% without installing GP. Each row has the form [n,t,s,a,P]:

  • n is the integer to be proved prime.

  • m = n + 1 - t is the proposed curve order, and s is its cofactor, so the next prime in the chain is q = m / s.

  • a is the coefficient of x in the curve equation. The other coefficient is recovered from the supplied point P.

  • P is an affine or homogeneous point; conversion computes Q = s • P and checks the required scalar multiplication by q.

The row in the example for 17 has m = 17 + 1 - 7 = 11 and cofactor 1, so P is already the point Q of order 11. The curve itself has 22 points; the saved row records the point's order 11, which is enough for the proof. A saved row is an encoding of the certificate calculation: the field t need not be the actual Frobenius trace of the curve. Hex verifies the required point-order calculation instead of trusting a claimed point count.

PARI certificates end with a prime below PARI's own cutoff. Hex still requires a proof certificate for that last integer; in the example, it is .small 11. It does not assume primality merely because PARI stopped its chain there.

Programmatic users can call Hex.ECPP.convertText with a string and the certificate for the last prime. It returns either an accepted Hex certificate or an error. Conversion accepts signed coordinates and reduces them modulo n. For homogeneous coordinates, the denominator must be invertible modulo n.

🔗def
Hex.ECPP.convertText (budget : Hex.ECPP.ImportBudget) (source : String) (leaf : Hex.Nat.PrimeCert) : Except Hex.ECPP.ImportError Hex.ECPP.Cert
Hex.ECPP.convertText (budget : Hex.ECPP.ImportBudget) (source : String) (leaf : Hex.Nat.PrimeCert) : Except Hex.ECPP.ImportError Hex.ECPP.Cert

Read PARI certificate text and convert it to a checked Hex primality certificate. Supply leaf as a HexPrimality certificate for the last prime in the chain. Return an error for invalid data or exceeded limits. Conversion does not call GP or search for leaf; a successful result is accepted by the ECPP checker for the integer recorded in the text.