Given that an integer is prime, can you convince me in a reasonable amount of time of that fact? Stated otherwise: Is there a “short” formal argument that proves the fact that a given prime is indeed prime? Here “short” means that the argument can be written in pages, for some polynomial independent of .
Notice that there is always a short proof of the fact that a given composite number is composite, namely a non-trivial factorization.
Formally this last statement means that the problem of the deciding if a given integer is composite is in NP.
The excercise is to prove that the problem of deciding if a given integer is prime is in NP.
Remarks: The formal argument mentioned in the explanation is usually called certificate. Notice that the size of the certificate must be polynomial in the logarithm of because is representable by bits and thus the size of the input is and not .