How to quickly determine whether a given natural number is a power of another natural number?

Question

We have a natural number $n>1$. We want to determine whether there exist natural numbers $a, k>1$ such that $n = a^k$.

Please suggest a polynomial-time algorithm.

Answer 1

This can be done in "essentially linear time." Check out Daniel Bernstein's website: http://cr.yp.to/arith.html

Especially note his papers labeled [powers] and [powers2].

Answer 2

In order to test whether or not a natural number $n$ is a perfect power, we can conduct a binary search of the integers {1,2,...,n} for a number $m$ such that $n = m^b$ for some $b>1$. Let $b>1$. If a solution $m$ to $m^b =n$ exists, then it must lie in some interval $[c_i,d_i]$. When $i = 0$ we may take $[c_0,d_0] = [1,n]$. To define $[c_{i+1},d_{i+1}]$, consider $\alpha:= \left\lfloor \frac{(ci+di)}{2}\right\rfloor$. If $\alpha^b = n$ then we’re done. If $\alpha^b > n$, let $[c_{i+1}, d_{i+1}] = [c_i, \alpha]$; otherwise $\alpha^b < n$ and we let $[c_{i+1}, d_{i+1}] = [\alpha, d_i]$. We continue in this manner until $|c_i − d_i| \leq 1$. We then increase the value stored in variable $b$ and start the loop again. Performing this loop for all $b \leq log(n)$ completes the algorithm.

A pseudocode implementation of this algorithm can be found on page 21 of Dietzelbinger's Primality Testing in Polynomial Time. Its complexity is approximately $O(log^3(n))$.

Answer 3

The computer algebra system GAP performs this test and determines a smallest root $a$ of a given integer $n$ quite efficiently. The following is copied directly from its source code (file gap4r6/lib/integer.gi), and should be self-explaining:

#############################################################################
##
#F  SmallestRootInt( <n> )  . . . . . . . . . . . smallest root of an integer
##
InstallGlobalFunction(SmallestRootInt,

  function ( n )

    local   k, r, s, p, l, q;

    # check the argument
    if   n > 0  then k := 2;  s :=  1;
    elif n < 0  then k := 3;  s := -1;  n := -n;
    else return 0;
    fi;

    # exclude small divisors, and thereby large exponents
    if n mod 2 = 0  then
        p := 2;
    else
        p := 3;  while p < 100  and n mod p <> 0  do p := p+2;  od;
    fi;
    l := LogInt( n, p );

    # loop over the possible prime divisors of exponents
    # use Euler's criterion to cast out impossible ones
    while k <= l  do
        q := 2*k+1;  while not IsPrimeInt(q)  do q := q+2*k;  od;
        if PowerModInt( n, (q-1)/k, q ) <= 1  then
            r := RootInt( n, k );
            if r ^ k = n  then
                n := r;
                l := QuoInt( l, k );
            else
                k := NextPrimeInt( k );
            fi;
        else
            k := NextPrimeInt( k );
        fi;
    od;

    return s * n;
end);

Answer 4

For each $k \le \log n/\log 2$, compute an approximation to the positive real $k$-th root of $n$ using Newton's method to enough precision to check if it is an integer. Alternatively, use $p$-adic roots for a suitable $p$, with Newton turning into Hensel.