Detecting if n is of the form a^b

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Nov 03, 2004 at 23:03

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?

5 Replies

Please log in or register to post a reply.

94a84041298055bd6ee5e78a44fe14c6
0
cristic 101 Nov 04, 2004 at 07:13

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.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Nov 04, 2004 at 07:36

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

280b3ca57720c1b1ad08dbc458325952
0
FarooqMela 101 Nov 04, 2004 at 07:45

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

94a84041298055bd6ee5e78a44fe14c6
0
cristic 101 Nov 04, 2004 at 07:50

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 ?

22b3033832c5c699c856814b0cf80cb1
0
bladder 101 Nov 04, 2004 at 13:20

@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 [snapback]13645[/snapback]

Scroll to the Other arithmetic operations section

Some really nice and seemingly interesting papers here :)