A primality certificate of an integer $n$ is a small set of numbers which enable one to quickly verify the primality of $n$ by using the numbers in a computation specified by a given theorem. Doing the computations to verify the certificate should be much faster than performing any sort of primality test on the number.