23
$\begingroup$

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.

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

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.

$\endgroup$
  • 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$ – David Marquis Apr 28 '12 at 6:11
  • 1
    $\begingroup$ A simple improvement that further removes a $\log \log n$ factor by only chose prime $b$. $\endgroup$ – Chao Xu Aug 31 '12 at 18:02
16
$\begingroup$

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.

$\endgroup$
  • $\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 '14 at 2:56
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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