certificate of primality

In everyday life, a certificate is a document attesting to the truth of a statement. For example, a wedding certificate provides proof that you were married and a diploma is a certificate showing that you have earned a specific degree. These contain information such as the name of the agency granting the certificate and signatures by which the certificate could be checked.

A certificate of primality for p is a summary of the proof that p is prime. The certificate must contain enough information to reproduce proof. The certificate should also be short (or at least substantially shorter than the original algorithm). For example, we can show a small number is prime by using trial division or the sieve of Eratosthenes. Neither of these methods provides a certificate of primality since to verify the proof we must reproduce the entire work. They do though provide certificates of compositeness (should the number be composite): the certificate would be the least prime divisor found. It is then easy to check this certificate by dividing by that one number.

The classical primality proving algorithms do admit certificates. To use these methods to prove n is prime we first (partially) factor n²-1 and then find a numbers which satisfy certain conditions for each of the prime factors. For example, Lucas proved that the number n is prime if for each prime divisor q of n-1 we can find an integer a for which a^n-1 ≡ 1 (mod n) but not a^(n-1)/q ≡ 1 (mod n). The certificate would be the list of prime divisors used along with those numbers. This summarizes the proof in a short and concise form.

A similar approach works for the elliptic curve primality proving algorithm, making the check of the certificate as much as 100 times as fast as the original proof. Currently cyclotomy does not admit practical primality certificates--the longest part of the work must be redone.

A final curious note: if p is prime, then there are integers a, b, . . . , z such that the value of the Matijasevic polynomial is p. A quick count shows that given these integers we need only do 87 additions, subtractions and multiplications to verify p is prime. This however is not considered a primality certificate because some of the 26 integers would be greater than p^p^p^p^p. Trial division by hand would be far faster than doing this on a computer.

References:

Ribenboim95 (sect. 2XIc)

P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, New York, NY, 1995.  pp. xxiv+541, ISBN 0-387-94457-5. MR 96k:11112 [An excellent resource for those with some college mathematics. Basically a Guinness Book of World Records for primes with much of the relevant mathematics. The extensive bibliography is seventy-five pages.]