# 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)

-
MR1464141 (98j:11121) Bernstein, Daniel J, Detecting perfect powers in essentially linear time. Math. Comp. 67 (1998), no. 223, 1253--1283. – Victor Protsak Jun 30 '10 at 5:01
Intuitively, for each $k$, just calculate the $k$th root using floating-point arithmetic with enough accuracy to see if it's exactly an integer. – Timothy Chow Jun 30 '10 at 17:51

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.

-

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)$.

-
If you're in a hurry, just do the check for prime k up to log(N). Gerhard "Ask Me About System Design" Paseman, 2010.06.30 – Gerhard Paseman Jun 30 '10 at 6:21