3
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – j_random_hacker Jun 27 '18 at 15:29
2
$\begingroup$

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.

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