# 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? – Tsuyoshi Ito 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. – arnab 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. – Tsuyoshi Ito Oct 10 '10 at 3:11
• Tsuyoshi/arnab, maybe you should repost as answers so this can be accepted ? – Suresh Venkat 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)$. – David Marquis Apr 28 '12 at 6:11
• A simple improvement that further removes a $\log \log n$ factor by only chose prime $b$. – Chao Xu Aug 31 '12 at 18:02

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. – Erick Wong 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<lg~n$.
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 & n) == n: return True  # 2 ^ k
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