Primality certificate

From Wikipedia, the free encyclopedia

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 b² 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 = coNP, a result widely believed to be false.

1 Pratt certificates
2 Impact of PRIMES in P
3 References
4 External links

[edit] Pratt certificates

Although not the first primality proof invented, the most famous, called the Pratt certificate, was conceived in 1975 by Vaughan Pratt.^[1] This was the first primality proof proven to have polynomial size and to be verifiable in polynomial time. It is based on Lehmer's theorem, which is essentially the converse of Fermat's little theorem with an added condition to make it true:

Suppose we have an integer x such that:

x is coprime to n;
x^{n −1} ≡ 1 (mod n)
For every prime factor p of n −1, it is not the case that x^{(n −1)/p} ≡ 1 (mod n).

Then, n is prime.

Given such an x (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 less 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)⁴) time.

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 85 is prime, supplying x=4 and 84=6×14 as the "prime factorization" of n −1. Then:

4 is coprime to 85
4⁸⁵⁻¹ ≡ 1 (mod 85)
4^(85−1)/6 ≡ 16 (mod 85), 4^(85−1)/14 ≡ 16 (mod 85)

We would falsely conclude that 85 is prime. We don't want to just force the verifier to factor the number, because there is no known general polynomial-time factoring algorithm.

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 x. For example, here is a complete Pratt certificate for the number 229:

229 (x=6, 229−1 = 2²×3×19)
- 2 (known prime)
- 3 (x=2, 3−1 = 2)
  - 2 (known prime)
- 19 (x=2, 19−1 = 2×3²)
  - 2 (known prime)
  - 3 (x=2, 3−1 = 2)
    - 2 (known prime)

Note that the product of the numbers at each level of the tree is at most the original number, so the total size of each level is linear. The number of levels is logarithmic, since n −1 is divisible by 2 for all odd primes. Together these observations can be used to show that the verification requires no more time than O(log n) top-level verifications: the total time is O((log n)⁵), which is quite feasible for numbers in the range that computational number theorists usually work with.

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. For larger numbers, an easier-to-generate primality certificate such as the Atkin-Goldwasser-Kilian-Morain certificate used by elliptic curve primality proving (ECPP) may be preferred.

[edit] Impact of PRIMES in P

Because primality testing can now be done deterministically in polynomial time using the AKS primality test, a prime number could itself be considered a certificate of its own primality. Given widely-believed assumptions, this test runs in O((log n)⁶) 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.

[edit] References

^ Vaughan Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, vol.4, pp.214–220. 1975. Citations, Full-text (requires paid login)