Is the certificate for primality testing polynomial in the length of the input?
Before it was proven that primality is in P, it was known that a complete factorisation if n-1 could be used to prove primality of n.  Now this also requires a proof that all factors in the claimed factorisation are actually themselves primes; this leads to a O(n^2) size certificate. 

Google for “Pratt certificate”. 

(When you use a certificate to solve a problem in NP, you cannot just “trust” the certificate. So if I tell you “here is a complete factorisation if n-1”, you can’t just believe that. You’d have to check that the product of the factors is actually n-1, which is easy. But you’d also have to check that each of the numbers that I claim are prime factors are actually prime, so you need a certificate for primality of these smaller numbers as well)..