A primality certificate
of an integer is a small set of numbers which enable one to quickly verify the primality of 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.