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.