20090423, 18:07  #1 
Apr 2009
2 Posts 
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) 
20090423, 18:51  #2  
Nov 2003
2^{2}×5×373 Posts 
Quote:
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). 

20090423, 19:33  #3  
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
256F_{16} Posts 
Realize that I am not the OP. And that I am not asking the Dr. to do this, unless he wishes to.
Quote:
Thanks 

20090423, 19:54  #4 
May 2003
7×13×17 Posts 
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). http://cr.yp.to/lineartime/powers220060914ams.pdf Note: The paper discusses how this is the bottleneck in AKS.
Last fiddled with by ZetaFlux on 20090423 at 20:02 Reason: correcting a mistake 
20090423, 19:58  #5 
May 2003
7·13·17 Posts 
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? 
20090423, 23:20  #6  
(loop (#_fork))
Feb 2006
Cambridge, England
2^{4}·3·7·19 Posts 
Quote:
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. 

20090424, 00:01  #7  
Nov 2003
2^{2}×5×373 Posts 
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. 

20090424, 02:42  #8 
"William"
May 2003
New Haven
3×787 Posts 
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^{n} +/ 1 William 
20090424, 02:48  #9  
May 2003
7×13×17 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
I took a New assignment untested Prime Number manual testing &TF  ONeil  Information & Answers  4  20171223 05:30 
Antipoverty drug testing vs "high" tax deduction testing  kladner  Soap Box  3  20161014 18:43 
How do I start testing after setting to run only on mains power  primecrusader  Information & Answers  2  20160909 04:45 
Speed of P1 testing vs. Trial Factoring testing  eepiccolo  Math  6  20060328 20:53 
Testing same number on multiple machines  dotnet_dev  Software  17  20030616 14:30 