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

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?

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.
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$$.