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

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$?

• It's easy if $b=1$ is allowed. – j_random_hacker Feb 23 '18 at 18:13
• I think you meant to write "($b > 1$)" in your edit. – j_random_hacker Feb 25 '18 at 15:10

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.

• It suffices to test prime values of $x$ in this range, since if $x$ is composite (say, $x = yz$ with $z$ prime), then $a^x = a^{yz} = (a^y)^z$. – j_random_hacker Jun 27 '18 at 15:29

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