# Why was primality test thought to be NP? [duplicate]

To check if $$n$$ is prime, one only need to try dividing $$n$$ by numbers up to $$\sqrt{n}$$, meaning that the complexity would be $$O(\sqrt{n})$$. In my opinion, $$O(\sqrt{n}) < O(n)$$ so this simple algorithm is already P. But why did people think that primality test is NP, and were surprised by the AKS primality test?

## marked as duplicate by David Richerby, Evil, xskxzr, Discrete lizard♦Apr 27 at 17:52

• If something is in P then it is automatically in NP. You seem to be using "NP" as shorthand for either "NP - P" or "NP-complete". – John Coleman Apr 27 at 11:28
• And I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP. Then it was shown to be in NP and co-NP, which was odd. Many people believed it was "slightly" exponential. – gnasher729 Apr 27 at 13:48

To start, any decision problem with a witness verifiable for a "yes" answer in polynomial time is in NP.

$$\bullet$$ The problem 'Is $$p$$ composite?' has a witness $$k$$, and it can be tested in polynomial time whether $$k$$ divides $$p$$, therefore is in NP.

$$\bullet$$ The problem 'Is $$p$$ prime?' has a polynomial certificate (which can be found here), therefore is also in NP.

Now, your complexity analysis is not correct. If your input is a number $$p$$, then the input size is $$\log (p)$$, since you need $$log(p)$$ bits to represent it. Therefore, $$n=\log(p)$$ and $$\sqrt{p}=\frac{1}{2} \log(p)$$ bits. So the time required (in respect to $$n$$) checking all the numbers up to $$\sqrt{p}$$ will be $$2^{\frac{1}{2}n}$$, and is in fact exponential in terms of input size $$n$$.

The question "Where exactly does the Primality problem lie" has been answered in the link here

• "Is p composite" is obviously in NP, because you can bring a witness easily. "Is p prime" is in NP, but not obviously at all - there is a quite deep theorem that every prime p has a short prove of being prime, which I think involves complete factorisations of p+1 and/or p-1. – gnasher729 Apr 27 at 11:05
• @gnasher729 thank you for spotting it! I edited it in. – lox Apr 27 at 11:56

I don't think many people thought it was NP-complete; it doesn't seem that you can use it to solve other problems in NP (which is required for NP-complete). Then it was shown to be in NP and co-NP, which was odd.

And you could of course do probabilistic tests in polynomial time. It is quite likely that there is a not very large polynomial p(n) so that doing p(n) probabilistic tests proves indeed that a number of size n is a prime. In which case primality was always in P. (It's just hard to prove).