I’ve written recently about a simple kind of primality certificates, Pratt certificates. These certificates are easy to understand, and easy to verify, but they’re expensive to produce. In order to produce a Pratt certificate that n is a prime you have to factor n-1, and that can take a long time if n is large [1]. So Pratt certificates are only used in practice for moderately large primes. “Moderate” could mean a 50-digit number, which is large for some purposes, but would not be considered large in the context of cryptography.
High-level description
Elliptic curve primality proofs are used to certify primes that are too large for Pratt certificates. The Goldwasser-Kilian theorem says that a number p is prime if there exists an elliptic curve with certain properties that depend on another prime q. As with Pratt certificates, this process is applied recursively: p is prime if q is prime, and q is prime if r is prime, … down some the base case of primes so small that they are recognized as prime.
The Goldwasser-Kilian theorem gives a lower bound on the size of q:
q > p1/2 + p1/4 + 1.
Ideally you find a q that’s not too much bigger than it needs to be. So to prove a 100-digit number is prime, maybe you reduce the problem to proving than an 80-digit number is prime, then reduce that to the problem of proving a 64-digit number is prime, etc.
Details
What is this elliptic curve in the theorem? You have to find a smooth curve mod p and a point M on the curve such that M is not the group identity, but qM is the group identity. How in the world would you go about finding such a curve? That’s a more complicated story, but the main idea of certificates is that they’re easy to verify, not easy to produce. Coming up with an elliptic curve primality proof is harder than verifying one [2].
Primality certificates need to be computationally easy to verify, not necessarily conceptually easy to verify. But they tend to be conceptually easier to verify than to produce as well. The rest of this post will outline how you could write your own code to verify an elliptic curve primality certificate.
How to verify from scratch
To verify an elliptic curve primality proof, you first [3] have to verify that someone has given you a smooth elliptic curve. They give you two numbers, a and b, and claim that
y² = x³ + ax + b
is a smooth elliptic curve over the integers mod p. To verify this you have to compute
4a³ + 27b²
and show that it is not divisible by n. Then you have to verify that the point M = (x, y) they gave you is on the curve, which requires sticking x and y into the cubic equation above and verifying that the equation holds mod p.
The last and most difficult step is to verify that qM gives the group identity for the elliptic curve. You have to add M to itself q times using the group law of the curve [4].
Implementing the group law for an elliptic curve modulo a prime is a little tedious, but the only difficult part is finding a multiplicative inverse mod p. Presumably your computing environment would have a library routine for modular inverses. For example, Mathematica has the function ModularInverse.
Related posts
[1] If n is a safe prime then q = (p-1)/2 is also a prime, and so proving that q is prime is just about as hard as proving p is prime. Such hard luck can’t keep going. As you recurse you eventually get to primes p such that p-1 factors into pieces much smaller than p, but the process can start of being difficult.
[2] Elliptic curve primality certificates are sometimes called Atkin-Goldwasser-Kilian-Morain certificates or Atkin-Morain certificates because Atkin and Morain did a lot of work to make the idea of Goldwasser and Kilian practical.
[3] The Goldwasser-Kilian theorem also requires that p is not divisible by 2 or 3, but that’s trivial to verify.
[4] In practice you don’t literally add M to itself q times, but you produce a result that is the same as if you did. You’d use repeated doubling, analogous to using repeated squaring in fast exponentiation.
and show that it is not divisible by n? p?