AKS Primality Test not a polynomial time algorithm?

Question

The following algorithm is provided in the paper PRIMES is in P at the beginning of section 4.

However, I am struggling to see how this is supposed to be a polynomial time algorithm. For example, consider line 1. To check whether $n$ is expressible in the form $a^b$ (for $a \in \mathbb{n}$ and $b > 1$) we might use code such as the following

a, b = 2, 2
while n != pow(a,b) and pow(a,2) <= n:
     while pow(a,b) <= n:
          b = b+1
     b = 2
     a = a+1

where pow(a,b) denotes $a^b$. Clearly this has complexity $O(n^2)$ which is not polynomial with respect to the size (number of digits in) $n$. So this step cannot be done in polynomial time.

Does this not mean that this algorithm does not run in polynomial time, and thus the assertion that "PRIMES is in P" is invalid?

Answer 1

If you read further in the paper, they explain each step's complexity, albeit not in immense detail as this is well covered by other papers and books.

Section 5, first line of Theorem 5.1 proof, says step 1 (perfect power detection) is $\tilde{O}(\log^3 n)$. Their reference (Gathan and Gerhard 1999) in turn references the papers of Bach and Sorenson (1993) and Bernstein (1998) which we can look up, and I've provided a link to each.

For a practical implementation, see mpn/perfpow.c in GMP.

For your larger question, I've written multple AKS implementations in C+GMP, and they show very clear polynomial $O(\log^{6+\epsilon} n)$ behavior in practice. The later Bernstein variants are, as expected, orders of magnitude faster than the V6 paper, but just as Bernstein describes, it has the same asymptotic complexity. All of them are very slow compared to practical deterministic primality tests such as APR-CL and ECPP, which both matches the expected theoretical results as well as other researcher's practical results (e.g. Brent and Bernstein).

Answer 2

The highest possible exponent is when $a=2$, and $b=\log_2N$. This is linear in the number of digits of $N$. So, for $b=2$ to $\log_2N$, check whether $N^{1/b}$ is an integer.