mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-04-23, 18:07   #1
bitblit
 
Apr 2009

2 Posts
Default 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)
bitblit is offline   Reply With Quote
Old 2009-04-23, 18:51   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 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
Old 2009-04-23, 19:33   #3
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

3·2,963 Posts
Default

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 View Post
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
Uncwilly is offline   Reply With Quote
Old 2009-04-23, 19:54   #4
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

152210 Posts
Default

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
Zeta-Flux is offline   Reply With Quote
Old 2009-04-23, 19:58   #5
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

2×761 Posts
Default

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?
Zeta-Flux is offline   Reply With Quote
Old 2009-04-23, 23:20   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

142638 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
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.
fivemack is offline   Reply With Quote
Old 2009-04-24, 00:01   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-04-24, 02:42   #8
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

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
wblipp is offline   Reply With Quote
Old 2009-04-24, 02:48   #9
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

2·761 Posts
Default

Quote:
Originally Posted by wblipp View Post
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).
Zeta-Flux is offline   Reply With Quote
Reply

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 2017-12-23 05:30
Anti-poverty drug testing vs "high" tax deduction testing kladner Soap Box 3 2016-10-14 18:43
How do I start testing after setting to run only on mains power primecrusader Information & Answers 2 2016-09-09 04:45
Speed of P-1 testing vs. Trial Factoring testing eepiccolo Math 6 2006-03-28 20:53
Testing same number on multiple machines dotnet_dev Software 17 2003-06-16 14:30

All times are UTC. The time now is 01:53.

Mon Nov 30 01:53:36 UTC 2020 up 80 days, 23:04, 3 users, load averages: 1.05, 1.12, 1.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

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.