# How to check if a number is a perfect power in polynomial time

The first step of the AKS primality testing algorithm is to check if the input number is a perfect power. It seems that this is a well known fact in number theory since the paper did not explain it in details. Can someone tell me how to do this in polynomial time? Thanks.

• The first step of the AKS algorithm is to test whether the input number is a perfect power (a number of the form $c^n$ for some integers c,n>1), which is different from testing whether the number is a prime power. The test for a perfect power is Exercise 9.44 of the book cited in the paper (Modern Computer Algebra by von zur Gathen and Gerhard, 2003). I have not read the book and I do not know the answer, but you have consulted the book? Oct 10 '10 at 2:45
• I believe the first step of AKS checks if the number is a power of some positive integer, not necessarily a prime. If it were known how to check a prime power in polynomial time before AKS, that would already have given a polynomial time primality tester. Oct 10 '10 at 2:46
• @Tsuyoshi Thanks for pointing out my mistake. I haven't consulted the book.
– yzll
Oct 10 '10 at 3:07
• If you care about the question, please try to solve the problem before you post it. Oct 10 '10 at 3:11
• Tsuyoshi/arnab, maybe you should repost as answers so this can be accepted ? Oct 10 '10 at 3:11

Given a number n, if at all it can be written as $a^b$ (b > 1), then $b < \log(n) + 1$. And for every fixed $b$, checking if there exists an $a$ with $a^b = n$ can be done using binary search. The total running time is therefore $O(\log^2 n)$ I guess.

• Ramprasad's answer leaves out the time to do the exponentiation which is $O(log^3 n)$. Another way is to choose $b$ then compute the $b$th root of $n$ which would have a total time of $O(log^3 n)$. Apr 28 '12 at 6:11
• A simple improvement that further removes a $\log \log n$ factor by only chose prime $b$. Aug 31 '12 at 18:02
• @DavidMarquis I don't know why it need $O(\log^3 n)$. I believe $O(\log^2 n)$ is enough. Just use the naive algorithm to find square, i.e. $a^2=b$ and modify it by the following: do while loop with j =2 to $\log n$ and replace 2 by j. (see the algorithm here to find square number of n: chegg.com/homework-help/…) Jun 30 '20 at 13:17

See Bach and Sorenson, Sieve algorithms for perfect power testing, Algorithmica 9 (1993), 313-328, DOI: 10.1007/BF01228507, and D. J. Bernstein, Detecting perfect powers in essentially linear time, Math. Comp. 67 (1998), 1253-1283.

• There is also a follow-up paper with improved asymptotic running time and simpler treatment: D. J. Bernstein, H. W. Lenstra Jr. and J. Pila, Detecting perfect powers by factoring into coprimes, Math. Comp. 76 (2007), 385–388. Jan 15 '14 at 2:56

I found an interesting and elegant solution in the paper: On the implementation of AKS class primality test, by R.Crandall and J.Papadopoulos, 18 Mar 2003.

Somehow, I can show that the binary search algorithm is $$O(lg~n \cdot (lg~lg~n)^2)$$.

Firstly, $$a^b = n$$, there is $$b.
Binary Search Algorithm: For each $$b$$, we use binary search to find $$a$$.

Each time the computation of $$a^b$$ cost $$lg~b = lg~lg~n$$ operations by using fast exponentiation. Therefore, the remaining issue is the range of $$a$$.

If $$A$$ is the maximal possible value of $$a$$, then binary search needs $$lg~A$$ operations

Note that $$b~lg~a = lg~n$$, that is $$lg~A = \frac{lg~n}{b}$$ When summing up, $$\sum lg~A = lg~n \cdot (\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{B}) = lg~n \cdot lg~B = lg~n \cdot lg~lg~n$$

In other words, all the operations for binary search is $$O(lg~n \cdot lg~lg~n)$$

Consider the operation of $$a^b$$, it is $$O(lg~n \cdot (lg~lg~n)^2)$$ finally.

ps: All the lg are base 2.

Python code:

#--- a^n ---------------------------------------
def fast_exponentation(a, n):
ans = 1
while n:
if n & 1 : ans = ans * a
a = a * a
n >>= 1
return ans
#------------------------------------------
# Determines whether n is a power a ^ b, O(lg n (lg lg n) ^ 2)
def is_power(n):
if (n == 1): return True
lgn = 1 + ( len( bin ( abs ( n ) ) ) - 2)
for b in range(2,lgn):
# b lg a = lg n
lowa = 1L
higha = 1L << (lgn / b + 1)
while lowa < higha - 1:
mida = (lowa + higha) >> 1
ab = fast_exponentation(mida,b)
if ab > n:   higha = mida
elif ab < n: lowa  = mida
else:   return True # mida ^ b
return False