In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime.
Primality certificates lead directly to proofs that problems such as primality testing and the complement of integer factorization lie in NP, the class of problems verifiable in polynomial time given a solution.
This was the first strong evidence that these problems are not NP-complete, since if they were, it would imply that NP is subset of co-NP, a result widely believed to be false; in fact, this was the first demonstration of a problem in NP intersect co-NP not known, at the time, to be in P. Producing certificates for the complement problem, to establish that a number is composite, is straightforward: it suffices to give a nontrivial divisor.
The concept of primality certificates was historically introduced by the Pratt certificate, conceived in 1975 by Vaughan Pratt,[1] who described its structure and proved it to have polynomial size and to be verifiable in polynomial time.
It is based on the Lucas primality test, which is essentially the converse of Fermat's little theorem with an added condition to make it true: Given such an a (called a witness) and the prime factorization of n − 1, it's simple to verify the above conditions quickly: we only need to do a linear number of modular exponentiations, since every integer has fewer prime factors than bits, and each of these can be done by exponentiation by squaring in O(log n) multiplications (see big-O notation).
However, it is possible to trick a verifier into accepting a composite number by giving it a "prime factorization" of n − 1 that includes composite numbers.
We don't want to just force the verifier to factor the number, so a better way to avoid this issue is to give primality certificates for each of the prime factors of n − 1 as well, which are just smaller instances of the original problem.
We continue recursively in this manner until we reach a number known to be prime, such as 2.
We end up with a tree of prime numbers, each associated with a witness a.
For example, here is a complete Pratt certificate for the number 229: This proof tree can be shown to contain at most
values other than 2 by a simple inductive proof (based on theorem 2 of Pratt).
The result holds for 3; in general, take p > 3 and let its children in the tree be p1, ..., pk.
By the inductive hypothesis, the tree rooted at pi contains at most
However, while useful in theory and easy to verify, actually generating a Pratt certificate for n requires factoring n − 1 and other potentially large numbers.
This is simple for some special numbers such as Fermat primes, but currently much more difficult than simple primality testing for large primes of general form.
To address the problem of efficient certificate generation for larger numbers, in 1986 Shafi Goldwasser and Joe Kilian described a new type of certificate based on the theory of elliptic curves.
[2] This was in turn used by A. O. L. Atkin and François Morain as the basis for Atkin-Goldwasser-Kilian-Morain certificates, which are the type of certificates generated and verified by elliptic curve primality proving systems.
[3] Just as Pratt certificates are based on Lucas's theorem, Atkin–Goldwasser–Kilian–Morain certificates are based on the following theorem of Goldwasser and Kilian (lemma 2 of "Almost All Primes Can Be Quickly Certified"): Technically, an elliptic curve can only be constructed over a field, and
is only a field if n is prime, so we seem to be assuming the result we're trying to prove.
The difficulty arises in the elliptic-curve addition algorithm, which takes inverses in the field that may not exist in
However, it can be shown (lemma 1 of "Almost All Primes Can Be Quickly Certified") that if we merely perform computations as though the curve were well-defined and do not at any point attempt to invert an element with no inverse, the result is still valid; if we do encounter an element with no inverse, this establishes that n is composite.
To derive a certificate from this theorem, we first encode Mx, My, A, B, and q, then recursively encode the proof of primality for q < n, continuing until we reach a known prime.
Moreover, the algorithm that generates these certificates can be shown to be expected polynomial time for all but a small fraction of primes, and this fraction exponentially decreases with the size of the primes.
Consequently, it's well-suited to generating certified large random primes, an application that is important in cryptography applications such as generating provably valid RSA keys.
Provable prime generation based on variants of Pocklington's theorem (see Pocklington primality test)[4] can be efficient techniques for generating primes (cost is generally less than probabilistic generation) with the added benefit of built in primality certificates.
The bits needed for this certificate (and order of computational cost) should range from approximately
"PRIMES is in P"[7] was a breakthrough in theoretical computer science.
This article, published by Manindra Agrawal, Nitin Saxena, and Neeraj Kayal in August 2002, proves that the famous problem of checking primality of a number can be solved deterministically in polynomial time.
This test runs in Õ((log n)6) time.
In practice this method of verification is more expensive than the verification of Pratt certificates, but does not require any computation to determine the certificate itself.