View Single Post
Old 2009-04-23, 18:51   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by bitblit View Post
Which is the fastest possible way to decide, whether a given natural number n is of the form n = a^b with integer a and b > 1?
(it is needed for the AKS primality test)
Let N be your number. Let a_i = N mod p_i for p_i = 2,3,5,7,11.....
up to some selected bound.

If N is a kth power, then it will be a kth power mod each of the primes.
If it fails any prime, then it is not a k'th power. Or one could check
if it is a kth power mod 2*3*5*7*11.... etc. (i.e. check all primes at
once)

If it is a kth power mod each prime, then we suspect that it actually
is a kth power. So compute the k'th root via (say) Newton's method
and see if it really is an integer.

So then try k = 2,3,5,7,... up to log_2(N).
R.D. Silverman is offline   Reply With Quote