For some $n$, how can we check whether there exists $a,b \in \mathbb{N}$ such that $a^b = n$ in polynomial time?

Question

For some given $n$, how can we check whether there exists $a,b \in \mathbb{N}$ ($b > 0$) such that $a^b = n$ in polynomial time with respect to the number of digits in $n$?

Answer 1

Note that $b$ is upper bounded by $\log n$, so you can go over all possible integers $x\in\left[1,\lceil\log n\rceil\right]$, and for each $x$ check whether the equation $a^x=n$ has an integer solution, i.e. whether or not $n^{\frac{1}{x}}$ is an integer. You might be interested in root finding algorithms.

Answer 2

Take Ariel's answer first.

If the exponents get so large that say $a ≤ 10^{12}$, checking that a is an integer is usually very fast - calculate log n once, and usually $2^{log n / b}$ is nowhere near an integer.

If the exponents get even larger and a gets smaller, instead of iterating over b and calculating a, we can iterate over values of a from some value down to 2, calculate b = $log n / log a$ and check if that is close to an integer. , For example if n has 1 million digits, then for b ≥ 80,000 we have a ≤ $10^{13}$ and ordinary floating point operations can usually find that a is not an integer. If b ≥ 200,000 then a ≤ 100,000 so instead of iterating for b from 200,000 upwards we iterate for a from 100,000 down to 2 and check if b is an integer.

Doing all the checking in polynomial time in log n is easy, keeping the degree low is harder. There are much less than log n large values b or a to check, usually each in constant time. For smaller b, you obviously only need to check primes b.

You can also check for small prime factors of n. Say n has a factor $2^{57}$, then we only need to check b = 3 and b = 19. If n has any small prime factors, this will be quite helpful.