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

my solution:

I thought of a first option that is exponential in n, For all k , 1<k<N , try divide N by k, until i get result 1.

for example N = 27, i will start with k = 2 , because its not divided , i will go to next k =3. i will divide 27 / 3 , will get 9 , and divide it again until i will get 1. but this is not good sulotion. this 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). but i dont know if a and k are relatively prime.

I trying to write an algorithm, but I have struggle 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 dont sure if the algorithm is right

CodePudding user response：

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.