testing, if a number is a power

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

[R.D. Silverman]

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

[Uncwilly]

Realize that I am not the OP. And that I am not asking the Dr. to do this, unless he wishes to.

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

[Zeta-Flux]

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.

[Zeta-Flux]

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?

[fivemack]

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.

[R.D. Silverman]

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.

[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 aⁿ +/- 1

William

[Zeta-Flux]

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 aⁿ +/- 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).