testing, if a number is a power
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) 
[QUOTE=bitblit;170724]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)[/QUOTE] 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). 
Realize that I am not the OP. And that I am not asking the Dr. to do this, unless he wishes to. [QUOTE=Dr. Silverman;170727]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 [COLOR="SeaGreen"]will be a kth power mod each of the primes[/COLOR]. 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. [/QUOTE]Could someone show an example of this, with a real pair of numbers (say, 62748517 =13^7 and 62748571 [a random similar numbr]). I kinda get lost in the highlighted section. I think that I can grasp most of the rest and looked briefly at Newton's method (successive approx.) and get that. Thanks 
Here is a recent paper on a fast algorithm for testing for the largest k with N a kth power, and then finding N^(1/k). [url]http://cr.yp.to/lineartime/powers220060914ams.pdf[/url] Note: The paper discusses how this is the bottleneck in AKS.

Unwilly,
If N is actually a power, say 13^7, then clearly N will continue to be a power modulo any prime. In this case, N==13^7 mod p. His claim is not extraordinary. If N is not a power it might become a power modulo p. For example, 2 is not a power, but 2==3^2 mod 7. Does that answer your question about the highlighted text? 
[QUOTE=Uncwilly;170732]Realize that I am not the OP. And that I am not asking the Dr. to do this, unless he wishes to. Could someone show an example of this, with a real pair of numbers (say, 62748517 =13^7 and 62748571 [a random similar numbr]). I kinda get lost in the highlighted section. I think that I can grasp most of the rest and looked briefly at Newton's method (successive approx.) and get that.
Thanks[/QUOTE] 2^25 < 62748571 < 2^26, and it's obviously not a power of two, so if it is a kth power we have k<26. log(62748571)/log(3) = 16.34, so it's not a power of three; log(62748571)/log(5) = 11.15, so it's not a power of five; log(62748571)/log(7) = 9.23. So, if 62748571 is a kth power, k is 2, 3, 5 or 7. 62748571 is congruent to 6 mod 11, but the squares mod 11 are 0, 1, 3, 4, 5 and 9, so k is not 2. The fifth powers mod 11 are 0, 1 and 10, so k is not 5 either. 62748571 mod 7 = 4, but the cubes mod 7 are 0, 1 and 6, so k is not 3. 62748571 mod 29 = 24, but the 7th powers mod 29 are 0, 1, 12, 17 and 28, so k is not 7. So 62748571 is not an exact power. By the same set of logs, we know that if n=62748517 is a kth power, k is 2, 3, 5 or 7. n is 7 mod 11, so k is not 2 or 5; n mod 7 is 6 so it could be a cube, but the cubes mod 19 are 0, 1, 7, 8, 11, 12 and 18, and n%19=10. So k could only be 7, and indeed exp(log(62748517)/7) is 13.00000 and 13^7 = 62748517. 
[QUOTE=fivemack;170751]2^25 < 62748571 < 2^26, and it's obviously not a power of two, so if it is a kth power we have k<26.
log(62748571)/log(3) = 16.34, so it's not a power of three; log(62748571)/log(5) = 11.15, so it's not a power of five; log(62748571)/log(7) = 9.23. So, if 62748571 is a kth power, k is 2, 3, 5 or 7. 62748571 is congruent to 6 mod 11, but the squares mod 11 are 0, 1, 3, 4, 5 and 9, so k is not 2. The fifth powers mod 11 are 0, 1 and 10, so k is not 5 either. 62748571 mod 7 = 4, but the cubes mod 7 are 0, 1 and 6, so k is not 3. 62748571 mod 29 = 24, but the 7th powers mod 29 are 0, 1, 12, 17 and 28, so k is not 7. So 62748571 is not an exact power. By the same set of logs, we know that if n=62748517 is a kth power, k is 2, 3, 5 or 7. n is 7 mod 11, so k is not 2 or 5; n mod 7 is 6 so it could be a cube, but the cubes mod 19 are 0, 1, 7, 8, 11, 12 and 18, and n%19=10. So k could only be 7, and indeed exp(log(62748517)/7) is 13.00000 and 13^7 = 62748517.[/QUOTE] Sure. But for really big integers you would need a high precision logarithm function, and writing such is difficult (and slow). So when you suspect it might be a kth power, compute floor(N^1/k). This can be done using only integer arithmetic via Newton's method. The sample values of N given here. really do not show how powerful looking at N modulo small primes really is. Try it with N near 2^1024, for example. 
Depending on the source of the number, you may or may not know whether the number has small factors. If the number might have small factors, do some trial factoring before applying the test method described above. If you find any factors, the power must be a divisor of the gcd of the exponents of the trial factors.
I believe Dario Alpern's Java factoring applet uses this method when checking if a number is a[sup]n[/sup] +/ 1 William 
[QUOTE=wblipp;170761]Depending on the source of the number, you may or may not know whether the number has small factors. If the number might have small factors, do some trial factoring before applying the test method described above. If you find any factors, the power must be a divisor of the gcd of the exponents of the trial factors.
I believe Dario Alpern's Java factoring applet uses this method when checking if a number is a[sup]n[/sup] +/ 1 William[/QUOTE]Good point! For example, one knows that numbers of the form a^n+1 are never perfect powers (except in the cases 2^3+1 and 3^21). 
All times are UTC. The time now is 16:02. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2020, Jelsoft Enterprises Ltd.