9

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<k<N , try to divide N by k until I get result 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 ak ≡ 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?

Jeff Schaller
  • 2,352
  • 5
  • 23
  • 38
hch
  • 717
  • 1
  • 6
  • 18
  • 5
    Note that the text of the problem uses `k` as the name of a power, N = a^k, but your explanation that follows uses `k` as a divider of N. In general, avoid giving the same name to different things! It adds to the confusion. We have plenty of letters in the alphabet. – Stef Mar 15 '22 at 09:19
  • 1
    The version of this question from the [theoretical CS StackExchange](https://cstheory.stackexchange.com/questions/2077/how-to-check-if-a-number-is-a-perfect-power-in-polynomial-time) may also be of use to you – kcsquared Mar 15 '22 at 14:29

3 Answers3

9

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.

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118
  • You were faster than me! Just a detail: we only need to test the prime `b`, but difference should not be too important. – Damien Mar 15 '22 at 09:34
  • @Damien non-prime `b` is also possible. eg. if input is `6^6` – vish4071 Mar 15 '22 at 09:38
  • 3
    @vish4071 a^(bc) = (a^b)^c, so if you can write a number as a composite power, you can also write it as a prime power. Eg: 6^6 is also 36^3. – Paul Hankin Mar 15 '22 at 09:40
  • @Damien nice observation about prime b! Given the question is of theoretical interest only, I prefer the simpler (but still polynomial) version. – Paul Hankin Mar 15 '22 at 09:42
  • Oh, yeah...that's true. I just assumed correct answer would want smallest `a`. Bad assumption on my part. – vish4071 Mar 15 '22 at 09:42
2

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.

Redu
  • 25,060
  • 6
  • 56
  • 76
1

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.