mersenneforum.org > Math testing, if a number is a power
 Register FAQ Search Today's Posts Mark Forums Read

 2009-04-23, 18:07 #1 bitblit   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)
2009-04-23, 18:51   #2
R.D. Silverman

Nov 2003

22·5·373 Posts

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

2009-04-23, 19:33   #3
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

9,181 Posts

Realize that I am not the OP. And that I am not asking the Dr. to do this, unless he wishes to.
Quote:
 Originally Posted by Dr. Silverman 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.
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

 2009-04-23, 19:54 #4 Zeta-Flux     May 2003 30138 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/powers2-20060914-ams.pdf Note: The paper discusses how this is the bottleneck in AKS. Last fiddled with by Zeta-Flux on 2009-04-23 at 20:02 Reason: correcting a mistake
 2009-04-23, 19:58 #5 Zeta-Flux     May 2003 30138 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?
2009-04-23, 23:20   #6
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

7×911 Posts

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

2009-04-24, 00:01   #7
R.D. Silverman

Nov 2003

22×5×373 Posts

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

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.

 2009-04-24, 02:42 #8 wblipp     "William" May 2003 New Haven 23×5×59 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 an +/- 1 William
2009-04-24, 02:48   #9
Zeta-Flux

May 2003

7·13·17 Posts

Quote:
 Originally Posted by wblipp 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 an +/- 1 William
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^2-1).

 Similar Threads Thread Thread Starter Forum Replies Last Post ONeil Information & Answers 4 2017-12-23 05:30 kladner Soap Box 3 2016-10-14 18:43 primecrusader Information & Answers 2 2016-09-09 04:45 eepiccolo Math 6 2006-03-28 20:53 dotnet_dev Software 17 2003-06-16 14:30

All times are UTC. The time now is 13:14.

Sun Jan 17 13:14:42 UTC 2021 up 45 days, 9:26, 0 users, load averages: 2.15, 2.35, 2.37

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.