Complexity of primenumber test

Question

The german wiki claims that the approach to check if any number before p is a divisor of p is a polynomial time algoritm. I dont understand this claim. Because imho this is linear, which is polynomial of degree one. What am i missing?

Answer 1

Normally for complexity of primality testing of a number $n$ you work with $\log(n)\,$ and not with the actual number $n$, e.g. the original AKS complexity is $O(\log(n)^{12+\epsilon}).\;$ In this scale $\sqrt{n}= \exp\left(\frac{1}{2}\ln(n)\right)\,$ is exponential.