<p>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.</p>

CC BY-SA 3.0
2014-01-15T02:56:41.817Z
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
CC BY-SA 3.0
2012-04-30T21:44:46.667Z
2012-04-30T21:44:46.667Z
Jeffrey Shallit
<p>Somehow, I can show that the binary search algorithm is <span class="math-container">$O(lg~n \cdot (lg~lg~n)^2)$</span>. <br></p>

<p>Firstly, <span class="math-container">$a^b = n$</span>, there is <span class="math-container">$b&lt;lg~n$</span>. <br> 
<b>Binary Search Algorithm: </b> 
For each <span class="math-container">$b$</span>, we use binary search to find <span class="math-container">$a$</span>.</p>

<p>Each time the computation of <span class="math-container">$a^b$</span> cost <span class="math-container">$lg~b = lg~lg~n$</span> operations by using  <b>fast exponentiation</b>. Therefore,
the remaining issue is the range of <span class="math-container">$a$</span>.</p>

<p>If <span class="math-container">$A$</span> is the maximal possible value of <span class="math-container">$a$</span>, then binary search needs   <span class="math-container">$lg~A$</span> operations </p>

<p>Note that <span class="math-container">$b~lg~a = lg~n$</span>, that is 
<span class="math-container">$$lg~A = \frac{lg~n}{b}$$</span>
When summing up,
<span class="math-container">$$\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$$</span></p>

<p>In other words, all the operations for binary search is <span class="math-container">$O(lg~n \cdot lg~lg~n)$</span></p>

<p>Consider the operation of <span class="math-container">$a^b$</span>, it is <span class="math-container">$O(lg~n \cdot (lg~lg~n)^2)$</span> finally.</p>

<p>ps: All the lg are base 2.</p>

<p><strong>Python code:</strong></p>



<pre><code>#--- a^n ---------------------------------------
def fast_exponentation(a, n):
    ans = 1
    while n:
        if n &amp; 1 : ans = ans * a
        a = a * a
        n &gt;&gt;= 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 &lt;&lt; (lgn / b + 1)
        while lowa &lt; higha - 1:
            mida = (lowa + higha) &gt;&gt; 1
            ab = fast_exponentation(mida,b) 
            if ab &gt; n:   higha = mida
            elif ab &lt; n: lowa  = mida
            else:   return True # mida ^ b
    return False
</code></pre>

CC BY-SA 4.0
2016-07-02T15:01:51.953Z
2020-05-18T15:02:03.893Z
2020-05-18T15:02:03.893Z
Kevin
<p>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.</p>

CC BY-SA 3.0
2013-07-31T15:42:59.270Z
2013-07-31T15:42:59.270Z
Plomb
<p>Given a number n, if at all it can be written as $a^b$ (b > 1), then $b &lt; \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. </p>

CC BY-SA 3.0
2012-04-28T06:11:11.567Z
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)$.
duckstar
CC BY-SA 3.0
2012-08-31T18:02:42.010Z
A simple improvement that further removes a $\log \log n$ factor by only chose prime $b$.
Chao Xu
CC BY-SA 4.0
2020-06-30T13:17:17.850Z
@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: https://www.chegg.com/homework-help/positive-integer-n-power-form-qk-q-k-positive-integers-k-1-g-chapter-1-problem-32e-solution-9780073523408-exc)
user777
CC BY-SA 2.5
2010-10-10T04:48:42.630Z
2010-10-10T04:48:42.630Z
Ramprasad
<p>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.</p>

CC BY-SA 3.0
2015-10-09T19:35:45.937Z
might be useful: http://cs.stackexchange.com/questions/48033/how-does-one-find-out-whether-n-ab-for-some-b/48060#48060
Charlie Parker
CC BY-SA 2.5
2010-10-10T02:45:32.483Z
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
CC BY-SA 2.5
2010-10-10T02:46:25.987Z
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
CC BY-SA 2.5
2010-10-10T03:07:01.633Z
@Tsuyoshi Thanks for pointing out my mistake. I haven't consulted the book.
yzll
CC BY-SA 2.5
2010-10-10T03:11:03.753Z
If [you care about the question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/318#318), please try to solve the problem before you post it.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-10T03:11:48.737Z
Tsuyoshi/arnab, maybe you should repost as answers so this can be accepted ?
Suresh Venkat
<ds.algorithms><nt.number-theory>
How to check if a number is a perfect power in polynomial time
yzll
# How to check if a number is a perfect power in polynomial time

(Asked by: username_0 on 2010-10-10)

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.

**Tags:** ds.algorithms, nt.number-theory

> **Comments:**
> **username_2**: 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?  
> **username_3**: 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.  
> **username_0**: @Tsuyoshi Thanks for pointing out my mistake. I haven't consulted the book.  
> **username_2**: If [you care about the question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/318#318), please try to solve the problem before you post it.  
> **username_4**: Tsuyoshi/username_3, maybe you should repost as answers so this can be accepted ?  
> **username_1**: might be useful: http://cs.stackexchange.com/questions/48033/how-does-one-find-out-whether-n-ab-for-some-b/48060#48060  

---

## 4 answers

### Answer by username_9 on 2010-10-10. Score: 34 | Accepted answer

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.

> **Comments:**
> **username_10**: username_9'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)$.  
> **username_11**: A simple improvement that further removes a $\log \log n$ factor by only chose prime $b$.  
> **username_12**: @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: https://www.chegg.com/homework-help/positive-integer-n-power-form-qk-q-k-positive-integers-k-1-g-chapter-1-problem-32e-solution-9780073523408-exc)  

---

### Answer by username_5 on 2012-04-30. Score: 16

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.

> **Comments:**
> **username_6**: 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.  

---

### Answer by username_7 on 2016-07-02. Score: 5

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


---

### Answer by username_8 on 2013-07-31. Score: 3

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.


---

