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)



Checking if a positive integer is a power other than a first power
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(log2*n*), 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) *m**k* < *n* && (*m*+1)*k* > *n*  

2) *m**k* > *n* && (*m*-1)*k* > *n*  

3) *m**k* == *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.






