24

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.

yzll
  • 428
  • 1
  • 3
  • 9
  • 7
    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 02:45
  • 1
    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 02:46
  • @Tsuyoshi Thanks for pointing out my mistake. I haven't consulted the book. – yzll Oct 10 '10 at 03:07
  • 2
    If you care about the question, please try to solve the problem before you post it. – Tsuyoshi Ito Oct 10 '10 at 03:11
  • Tsuyoshi/arnab, maybe you should repost as answers so this can be accepted ? – Suresh Venkat Oct 10 '10 at 03:11
  • might be useful: http://cs.stackexchange.com/questions/48033/how-does-one-find-out-whether-n-ab-for-some-b/48060#48060 – Charlie Parker Oct 09 '15 at 19:35

4 Answers4

33

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
  • 2,482
  • 18
  • 18
  • 5
    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 Apr 28 '12 at 06:11
  • 2
    A simple improvement that further removes a $\log \log n$ factor by only chose prime $b$. – Chao Xu 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: 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 Jun 30 '20 at 13:17
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.

Jeffrey Shallit
  • 6,986
  • 33
  • 38
  • 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 02:56
4

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
Rishabh Deep Singh
  • 103
  • 4
Kevin
  • 141
  • 3
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.

Plomb
  • 31
  • 1