Question

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)

Answer 1

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(log₂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.

Answer 2

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