Decide whether an $n$-bit positive integer is composite

Question

Question:

Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP?

I know that for every composite number, a factor of the number is a certificate. Verification proceeds by dividing the number by the factor and checking if the reminder is zero. My question is whether the verification can be done in polynomial time of $n$? it seems that we need to use at most $2^n/2 = 2^{n-1}$ factors to test, does that mean we should use exponential time to verify?

Answer 1

NP doesn’t look at how hard it is to find a certificate (in this case a factor), just at how hard it is to test a certificate that claims to prove the answer is “yes”.

So it doesn’t matter how hard it is to find a factor, just that given a factor of an n-bit number, you can easily verify that it is a factor in $O(n^2)$. Or a bit faster with more effort. So “is x composite” is quite obviously in NP.

The opposite, “is x a prime”, has been shown to be in NP, but that is absolutely not easy to show. Basically you have to show that for any n-bit prime p, there is a certificate that allows us to verify in polynomial time time that p is prime.

Answer 2

It's almost always the case that problem sizes are expressed as a function of the length of the input, so a number n would be taken to be $\log n$ in length. For example, your verification would be in poly time if it ran in $O(\log^k n)$ time for some integer $k$.