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. By "succinct", we usually mean that we wish for the proof to 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.

Read more about Primality Certificate:  Pratt Certificates, Atkin–Goldwasser–Kilian–Morain Certificates, Impact of PRIMES in P

Famous quotes containing the word certificate:

    God gave the righteous man a certificate entitling him to food and raiment, but the unrighteous man found a facsimile of the same in God’s coffers, and appropriated it, and obtained food and raiment like the former. It is one of the most extensive systems of counterfeiting that the world has seen.
    Henry David Thoreau (1817–1862)