[andreasscherman]

To help anyone who was as confused as I about this being the first polynomial time algorithm. To me, even the naïve primality test is a polynomial time algorithm over the target number. However, here the AKS primality test is a polynomial time algorithm over the number of digits in the target number, which of course is different!

[allenz]

Yes, time complexity is based on the length of the input to a Turing machine. For example, integer factorization is a hard problem because all known algorithms are roughly exponential in the number of bits.