5 replies to this topic

[Reedbeta]

I'm trying (just for fun) to implement the Agrawal-Kayal-Saxena primality testing algorithm. The majority of the algorithm seems fairly straightforward, but the first line is tripping me up.

It asks to determine, for a given natural number n, if n = a^b for some natural numbers a and b > 1. I've thought of taking the logarithm of n; this gives log n = b log a, but doesn't seem to help the determination if a and b are natural numbers (obviously, if one allows a and b to be real numbers, there are infinitely many solutions to n = a^.

This isn't an essential part of the algorithm as it's basically an early-out, but I'm curious anyways.

How do you tell whether n is of the form a^b?

[cristic]

hmmm, you could use the brute force method until you come up with a better idea...

And, honestly I don't know of a better idea, because you want to find the values of two constants, but you only have one equation. :sad:

Edited for length.

[Reedbeta]

Yes, if we were dealing with real numbers, the system would be underdetermined. But since n, a, and b are all constrained to be natural numbers, it should be easier. There will still be multiple solutions in some cases, but all that is required is to discover that one exists (I don't care what the a and b are, only that they exist) or to prove that none exist.

Brute force would work, though I was hoping for something better =D

[FarooqMela]

There is a paper by DJ Bernstein which addresses this very problem. Off the top of my head I think it's titled "Detecting perfect powers in essentially linear time." Google it

[cristic]

If you could think of one more dependency between a,b it could work. But to my knowledge, if you have only one equation and two unknown constants it can not be done, without expressing one constant as a function of the other. Whether we are dealing with real or natural number the nature of the problem is the same, only thing that changes is that with natural numbers the problem has a finite number of possible solutions and thus the correct one can be computed with brute force.

Although looking closer at the problem, I think it is safe to say that if n=a^b then this means that n can be divided by a exactly b times, so it would make sense to furhter investigate only those values of a that divide n. This doesn't give an exact solution but further narrows the interval for valid values of a and b. For instance if n is 9, there is no need to check for values of a like 2, 4, 5,...

What do you mean by multiple solutions in this context ?

[bladder]

FarooqMela said:

There is a paper by DJ Bernstein which addresses this very problem. Off the top of my head I think it's titled "Detecting perfect powers in essentially linear time." Google it

Scroll to the Other arithmetic operations section

Some really nice and seemingly interesting papers here