Quote:
Originally Posted by bitblit
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).