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.

  • 7
    $\begingroup$ 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? $\endgroup$ Oct 10, 2010 at 2:45
  • 1
    $\begingroup$ 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. $\endgroup$
    – arnab
    Oct 10, 2010 at 2:46
  • $\begingroup$ @Tsuyoshi Thanks for pointing out my mistake. I haven't consulted the book. $\endgroup$
    – yzll
    Oct 10, 2010 at 3:07
  • 2
    $\begingroup$ If you care about the question, please try to solve the problem before you post it. $\endgroup$ Oct 10, 2010 at 3:11
  • $\begingroup$ Tsuyoshi/arnab, maybe you should repost as answers so this can be accepted ? $\endgroup$ Oct 10, 2010 at 3:11

4 Answers 4


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.

  • 5
    $\begingroup$ 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)$. $\endgroup$
    – duckstar
    Apr 28, 2012 at 6:11
  • 2
    $\begingroup$ A simple improvement that further removes a $\log \log n$ factor by only chose prime $b$. $\endgroup$
    – Chao Xu
    Aug 31, 2012 at 18:02
  • $\begingroup$ @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/…) $\endgroup$
    – user777
    Jun 30, 2020 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.

  • $\begingroup$ 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. $\endgroup$
    – Erick Wong
    Jan 15, 2014 at 2:56

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 == 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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.