polynomial (in n) time algorithm that decides whether N is a power

Question

I am a computer science student; I am studying the Algorithms course independently.

During the course, I saw this question:

Given an n-bit integer N, find a polynomial (in n) time algorithm that decides whether N is a power (that is, there are integers a and k > 1 so that a^k = N).

I thought of a first option that is exponential in n: For all k , 1

For example, if N = 27, I will start with k = 2 , because 2 doesn't divide 27, I will go to next k =3. I will divide 27 / 3 to get 9, and divide it again until I will get 1. This is not a good solution because it is exponential in n.

My second option is using Modular arithmetic, using a^k ≡ 1 mod (k+1) if gcd(a, k+1 ) = 1 (Euler's theorem). I don't know if a and k are relatively prime.

I am trying to write an algorithm, but I am struggling to do it:

function power(N)
Input: Positive integer N
Output: yes/no
Pick positive integers a_1, a_2, . . . , a_k < N at random
if (a_i)^N−1 ≡ 1 (mod N)
for all i = 1, 2, . . . , k:
    return yes
else:
    return no

I'm not sure if the algorithm is correct. How can I write this correctly?

user_1400793 · Answer

Ignoring the cases when N is 0 or 1, you want to know if N is representable as a^b for a>1, b>1.

If you knew b, you could find a in O(log(N)) arithmetic operations (using binary search). Each arithmetic operation including exponentiation runs in polynomial time in log(N), so that would be polynomial too.

It's possible to bound b: it can be at most log_2(N)+1, otherwise a will be less than 2.

So simply try each b from 2 to floor(log_2(N)+1). Each try is polynomial in n (n ~= log_2(N)), and there's O(n) trials, so the resulting time is polynomial in n.

user_4543207 · Answer

This looks like a simple math question. Suppose that we are given N = 96889010407 which is much less than Number.MAX_SAFE_INTEGER.

The question trys to figure out if N is a power where a**k === N for a > 1 and k > 1 . So we can also write it as

Math.log(a**k) === Math.log(N) yielding k*Math.log(a) === Math.log(N) yielding Math.log(a) === Math.log(N) / k where k is an Integer > 1.

Now remember the inverse logarithm. Math.log(y) = x yields y = Math.E**x.

This means we are looking for an Integer like a = Math.E**(Math.log(N) / k) for some k if exists. So start from k=2 and increment by 1.

 k  a = Math.E**(Math.log(N) / k)
___ _____________________________
 2  311269.99599543784    ->   NO
 3  4592.947769836504     ->   NO
 4  557.9157606623403     ->   NO
 5  157.49069663608586    ->   NO
 6  67.77129015915592     ->   NO
 7  37.1080205641031      ->   NO
 8  23.62024048697092     ->   NO
 9  16.622531664172815    ->   NO
 10 12.54952973764698     ->   NO
 11 9.971310247420734     ->   NO
 12 8.232332000056601     ->   NO
 13 6.999999999999999     ->   YES a is 7 and 96889010407 = 7^13

So for how long do we have to iterate? As long as Math.E**(Math.log(N) / k >= 2. In this case max 36 iterations since Math.E**(Math.log(96889010407) / 37 is 1.9811909632660634 and a must be an integer > 1.

This algorithm is probably the most efficient one for this job. It's time complexity is O(log2(N)) as we iterate k (the power). Had we chosen a to iterate then the time complexity would be O(sqrt(N)).

This is OK for Natural numbers but you can extend this to the Rationals as well.

Say, is 10.999671418529301 a perfect power?

All you have to do is to convert the decimal into a fraction the best way possible to get the rational form 4084101/371293 and apply both the numerator and the denominator to the mentioned algorithm above, to see if they both give the same power which in this case would be 5. 10.999671418529301 is 21^5/13^5.

Note: JS Math object is used in the example.

user_1196549 · Answer

The number N cannot exceed 2^n. Hence you can initialize i=2, j=n and compute i^j with decreasing j until you arrive at N, then increase i and so on. A power is found in polynomial time.

E.g. with 7776 < 8192 = 2^13, you try 2^12 = 4096, then 3^12, 3^11, 3^10, 3^9, 3^8, then 4^8, 4^7, 4^6, 5^6, 5^5, 6^5 and you are done.

polynomial (in n) time algorithm that decides whether N is a power

3 Answers