Integer Factoring - Check if $N=a^{b}$ for some integers $a$ and $b$

Question

I'm reading a lecture about Quantum Integer Factoring. At some point (page 16) it is stated:

Check if $N$ is a power $a^{b}$ for integers $a$ and $b$. An efficient algorithm for this exists.

Since my knowledge on number theory and integer factorization is still very limited, could you point me to some resources talking about this specific algorithm?

Edit: take $b \le \left\lceil \log_{2}{N} \right\rceil$

Answer 1

E.Bach and J.Sorensen, Sieve Algorithms for Perfect Power Testing, http://research.cs.wisc.edu/techreports/1989/TR852.pdf, describe an alogrithm with average complexity $O(\log^2N)$ based on tests whether $N$ is a perfect power modulo small primes.

Combined with optimal trial division the complexity can be reduced further.