hex

6.3. Why elliptic curves prove primality🔗

Suppose n > 3 is coprime to 6. Choose coefficients for a short Weierstrass equation

E : y² = x³ + a x + b,

and do arithmetic modulo n. Require 4a³ + 27b² to be invertible modulo n. This ensures that for every prime divisor p of n, reducing the equation modulo p gives a nonsingular elliptic curve over the field 𝔽_p.

Next find a finite point Q and a prime q < n such that scalar multiplication gives q • Q = O, where O is the point at infinity. Every division used in this calculation must have a verified inverse modulo n. The calculation therefore remains valid after reduction modulo every prime divisor p of n.

The reduced point is finite, so it is not the identity. Since q is prime, its order is exactly q. Consequently,

q ≤ #E(𝔽_p) ≤ (√p + 1)².

The second inequality is Hasse's bound. We use the formal proof from the TauCeti project, imported as WeierstrassCurve.hasse_bound. If we also require

q > (n^(1/4) + 1)²,

there can be no prime divisor p ≤ √n: such a divisor would give (√p + 1)² ≤ (n^(1/4) + 1)² < q, a contradiction. Every composite integer greater than 1 has a prime divisor at most its square root, so n must be prime.

We do not assume that n is prime in order to use an elliptic curve group over 𝔽_p. The argument takes place over fields associated with the prime divisors of n. This is what lets the method prove primality.

The certificate includes a proof certificate for the smaller prime q. That certificate may use another elliptic curve, or one of HexPrimality's small-prime or Pocklington certificates. Repeating this construction produces a finite proof of the original integer's primality.

6.3.1. Finding the curve and point🔗

Hex's search uses complex multiplication to propose curves with useful orders. Here this means using a fixed collection of special elliptic curves for which number-theoretic calculations suggest the number of points. We partially factor a proposed order m = s q, find a point P, and try Q = s • P as a point of order q. The search then tries to prove q prime recursively.

These proposed orders guide the search; they are not mathematical assumptions in the final proof. The checker directly verifies the curve, point and equation q • Q = O needed for the Hasse argument. Understanding complex multiplication is therefore unnecessary for using or checking a saved certificate.