Quick methods to check perfect $4^{th}, 5^{th}, 6^{th}$ powers

Question

Are there any quick modulus methods to check if a number could be a perfect power (4, 5, 6)? Preferably binary methods that could be extended to higher powers.

For example, a perfect fourth power has to be $0, 1 \pmod{16}$ from a square number being $0, 1 \pmod 4$. Also, a perfect sixth power has to be $0,1 \pmod{8}$.

Other than something very simple, a few iterations of Newton's method converges very quickly.

Answer 1

I am copying Jeremy Teitelbaum's answer here.

---

See the paper by Bernstein, Lenstra, and Pila: “Detecting Perfect Powers by Factoring into Coprimes”, Mathematics of Computation, Volume 76, #257, January 2007, pp. 385–388.

From the abstract:

This paper presents an algorithm that, given an integer $n>1$, finds the largest $k$ such that $n$ is a $k$th power.

The algorithm runs in time $\log(n)(\log\log(n))^{O(1)}$.