Primality certificate

In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. 'Succinct' usually means that the proof should be at most polynomially larger than the number of digits in the number itself (for example, if the number has b bits, the proof might contain roughly b2 bits). In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. 'Succinct' usually means that the proof should be at most polynomially larger than the number of digits in the number itself (for example, if the number has b bits, the proof might contain roughly b2 bits). 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. These problems already trivially lie in co-NP. This was the first strong evidence that these problems are not NP-complete, since if they were, it would imply NP = 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. Standard probabilistic primality tests such as the Baillie–PSW primality test, the Fermat primality test, and the Miller–Rabin primality test also produce compositeness certificates in the event where the input is composite, but do not produce certificates for prime inputs. The concept of primality certificates was historically introduced by the Pratt certificate, conceived in 1975 by Vaughan Pratt, 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). Even with grade-school integer multiplication, this is only O((log n)4) time; using the multiplication algorithm with best-known asymptotic running time, the Schönhage–Strassen algorithm, we can lower this to O((log n)3(log log n)(log log log n)) time, or using soft-O notation Õ((log n)3). 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. For example, suppose we claim that n = 85 is prime, supplying a = 4 and n − 1 = 6 × 14 as the 'prime factorization'. Then (using q = 6 and q = 14): We would falsely conclude that 85 is prime. 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 4 log 2 ⁡ n − 4 {displaystyle 4log _{2}n-4} 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 4 log 2 ⁡ p i − 4 {displaystyle 4log _{2}p_{i}-4} values, so the entire tree contains at most since k ≥ 2, and p1...pk = p − 1. Since each value has at most log n bits, this also demonstrates that the certificate has a size of O((log n)2) bits.