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$?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ It's easy if $b=1$ is allowed. $\endgroup$– j_random_hackerFeb 23, 2018 at 18:13
-
$\begingroup$ I think you meant to write "($b > 1$)" in your edit. $\endgroup$– j_random_hackerFeb 25, 2018 at 15:10
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
-
$\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$ Jun 27, 2018 at 15:29
$\begingroup$
$\endgroup$
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.
