# While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test?

While a basic algorithm to check for primality of a number 'n' [checking if a divides n for all a less than n] would take O(n), AKS test was the breakthrough after which it was placed in P complexity class.

• Can you give a reference or proof for [primality test] considered to be not in P? Aug 23, 2020 at 7:22

The bit length of $$n$$ is $$\log(n)$$, if we forget about the most significant digits, which is always $$1$$ except for $$n=0$$. As a function of $$t=\log(n)$$ you have $$n^{1/2}=2^{t/2}$$. It is in terms of the bit length of $$n$$ that AKS runs in polynomial time, while the naive test doesn't.
• (While $O(n)$ looks as true as $\in\mathbb P$, can you quote (and argue) a tighter bound?) Aug 23, 2020 at 7:26
• What a lot of people seem to miss is that P and NP are defined in terms of Turing machines. A problem is in P if the TM takes at most a polynomial number of steps $p(n)$ where $n$ is the number of symbols on the input tape. Aug 24, 2020 at 0:16
• @Pseudonym They had a different problem, which is how $n$ is input. If $n$ is input in unary in the Turing machine, then the naive algorithm would be polynomial.