# 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*^{2}-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.]