What is the complexity of checking whether an integer $n \geq 2$ is expressible in the form $a^b$ where $a, b \in \mathbb{N}$? I am currently studying the paper Primes is in P and have a question regarding 5 section of this paper. Line 1 of the algorithm (on page 3) requires the following operation to be performed

if (n = a^b for some natural numbers a and b), output 'composite'


I have attempted to deduce the complexity of this line and have deduced the following. Assuming $n \geq 2$, $b$ must be bounded above by $\lceil \log_2 (n) \rceil$. Thus, if there exists $a,b \in \mathbb{N}$ such that $a^b = n$ then $n^\frac{1}{b}$ must be an integer. Thus, to test whether such values of $a$ and $b$ exist, we must check whether
$$
n^\frac{1}{x}
$$
is an integer for each $2 \leq x \leq \lceil \log_2 (n) \rceil$. This requires a maximum of $\lfloor \log_2 (n) \rfloor$ operations to be performed, so the complexity of this step (according to my likely incorrect analysis) would be $O(\log_2 (n))$.

However, on page 6 of the paper it says that the complexity of this step is $O^\sim (\log^3(n))$. Why is this?

Note that this question regards the specific complexity of this operation, rather than simply verifying that it is doable in polynomial time (which was done here).
The complexity very much depends on whether you are looking at the worst case, or at the average case when you choose n at random. 

To find whether $n^{1/b}$ is an integer, you could pre-calculate the set of possible integers $(a^b) \mod k$ for various k, and check whether $n \mod k$ is among those values - if not then $n^{1/b}$ is not an integer. If n is chosen at random, then this will eliminate many cases very quickly. 

You can numerically calculate $n^{1/b}$ and check if it is an integer. If you calculate this value with (log n / b + 20) bits precision, and n was chosen at random, then your chance is 99.9999% that you can prove it is not an integer - this will fail if the result is an integer or close to one. There is a clever method doing the calculation using quadratically convergent Newton iteration involving only multiplications and additions / subtractions. Since only the last step requires the full precision, and the calculation involves raising numbers to powers b which is done in log b multiplications, this can be done in $O ({(\log n)^2 \over b^2} * \log b)$ steps using naive multiplication, and $O ((\log n / b) * \log (\log n / b) * \log b)$ using FFT. For random n, most of the time this is all that is needed. 

It is possible that we find $n^{1/b}$ rounded to the nearest integer and cannot prove that $n^{1/b}$ is not an integer. In these cases we may have to calculate $a^b$. Again, only the final product needs full precision, so this is done in $O(log^2 n)$ using naive multiplication, or $O (log n log log n) using FFT.