Computational Complexity of Primality Checking

Question

"PRIMES in P" proved that primality checking is in $P$. However, the CS 101 prime checking algorithm is to divide a number $n$ through all integers up to ${\sqrt n}$ , and if no results are whole numbers, then $n$ is prime. Is this not an ${O}({\sqrt n})$ algorithm which is thus in $P$? If so, why did we need AKS to show that primality checking is in $P$?

Answer 1

Polynomial is meant in the input size in bits that is polynomial in $\log n$. The PRIMES is in P gives an $O((\log n)^C)$ algorithm.

Answer 2

quid succinctly answered this.

This graph of log-log size vs. time for some open source implementations shows how trial division (in orange) is exponential time, while AKS (dark green is v6, light green is with additional improvements) gives nice straight lines of slope ~6.4, which fits pretty well with the the expected $O(\log^6 n)$ complexity. The APR-CL and ECPP implementations also fit reasonably well with our expectations.