Checking if a positive integer is a power other than a first power On page 43 of the pdf given as reference 2 at http://en.wikipedia.org/wiki/AKS_primality_test, the authors mention that this can be done in almost cubic time with Newton's method, although I can't figure out how this would work.
I do know about almost-linear time multiplication.
(this is theoretical enough that I'm guessing it goes here rather than on stackoverflow)
 A: A fast way of calculating $\sqrt{N}$ is the following iteration. Set $c_1=N$, then $c_{n+1}=\frac{c_n+N/c_n}{2}$. It is easy to see that $c_n>\sqrt{N}$ and the error is halved in each step, so we get $\lceil\sqrt{N}\rceil$ in linear time. If its square is $N$, then $N$ is a square, otherwise not. This is the Newton iteration for the function $f(x)=\sqrt{x}$. The corresponding thing must be done for the $k$-th root for each $k\leq\log(N)$.     
A: I don't know how to do it in cubic time, but I suppose that, to use Newton's Method, you could do the following:
Find floor(log2n), and this is the largest "power" that it can be.  Then, define:
$f_k(x) = x^k - n$ where n is your number and k is the floor value, and iterate Newton's Method until you get a number whose floor is m that fits any of the following:
1) mk < n && (m+1)k > n
2) mk > n && (m-1)k > n
3) mk == n
If the third is true, congrats, you've found yourself a root!  Otherwise, reduce k by 1 and try again.
The problem with this is that I don't know how long it'll take for such a value of m to be found.  Wikipedia says Newton's Method has a quadratic convergence, and you're making a fixed number of operations each iteration of the Method, so I guess its running-time would be pretty fast.
