Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)

share|improve this question
7  
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
add comment

2 Answers

up vote 0 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.