What is the complexity of checking whether an integer $n \geq 2$ is expressible in the form $a^b$ where $a, b \in \mathbb{N}$?

Question

I am currently studying the paper Primes is in P and have a question regarding 5 section of this paper. Line 1 of the algorithm (on page 3) requires the following operation to be performed

if (n = a^b for some natural numbers a and b), output 'composite'

I have attempted to deduce the complexity of this line and have deduced the following. Assuming $n \geq 2$, $b$ must be bounded above by $\lceil \log_2 (n) \rceil$. Thus, if there exists $a,b \in \mathbb{N}$ such that $a^b = n$ then $n^\frac{1}{b}$ must be an integer. Thus, to test whether such values of $a$ and $b$ exist, we must check whether $$ n^\frac{1}{x} $$ is an integer for each $2 \leq x \leq \lceil \log_2 (n) \rceil$. This requires a maximum of $\lfloor \log_2 (n) \rfloor$ operations to be performed, so the complexity of this step (according to my likely incorrect analysis) would be $O(\log_2 (n))$.

However, on page 6 of the paper it says that the complexity of this step is $O^\sim (\log^3(n))$. Why is this?

Note that this question regards the specific complexity of this operation, rather than simply verifying that it is doable in polynomial time (which was done here).

Answer 1

The complexity very much depends on whether you are looking at the worst case, or at the average case when you choose n at random.

To find whether $n^{1/b}$ is an integer, you could pre-calculate the set of possible integers $(a^b) \mod k$ for various k, and check whether $n \mod k$ is among those values - if not then $n^{1/b}$ is not an integer. If n is chosen at random, then this will eliminate many cases very quickly.

You can numerically calculate $n^{1/b}$ and check if it is an integer. If you calculate this value with (log n / b + 20) bits precision, and n was chosen at random, then your chance is 99.9999% that you can prove it is not an integer - this will fail if the result is an integer or close to one. There is a clever method doing the calculation using quadratically convergent Newton iteration involving only multiplications and additions / subtractions. Since only the last step requires the full precision, and the calculation involves raising numbers to powers b which is done in log b multiplications, this can be done in $O ({(\log n)^2 \over b^2} * \log b)$ steps using naive multiplication, and $O ((\log n / b) * \log (\log n / b) * \log b)$ using FFT. For random n, most of the time this is all that is needed.

It is possible that we find $n^{1/b}$ rounded to the nearest integer and cannot prove that $n^{1/b}$ is not an integer. In these cases we may have to calculate $a^b$. Again, only the final product needs full precision, so this is done in $O(log^2 n)$ using naive multiplication, or $O (log n log log n) using FFT.

Answer 2

It is true that the search for $b$ leads to a loop with $O(\log n)$ iterations. But for a given $b$ you also have to find the corresponding $a$. So, how much time do we need for that?

I would try binary search. With $k:=\frac{\log n}b$, observe that the number of digits of $a$ is $O(k)$. So is the number of iterations of the binary search. Raising a candidate $a$ to the $b$-th power requires a loop of length $O(\log b)$. In the $i$-th iteration of said loop, we are muliplying $2^ik$-bit numbers. Which can be done in $O(2^ik\log(2^ik)\log\log(2^ik))$ time. Let's bound that as $O(2^ik(i+\log k)\log\log\log n)$. The full loop of length $O(\log b)$ then takes $O(bk(\log b+\log k)\log\log\log n)$ time. The binary search thus takes time $O(bk^2(\log b+\log k)\log\log\log n)$, which we bound by $O((\log n)^2\frac1b\log\log n\log\log\log n)$. The loop involving $b$ means summing $\frac1b$ up to $\log n$ resulting in $O(\log\log n)$.

So the overall running time is $O((\log n)^2(\log\log n)^2\log\log\log n)$. Which gives a better upper bound than $O((\log n)^3)$ but is also messier. Maybe the paper assumed a less sophisticated multiplication algorithm. Or maybe they deliberately traded bound tightness for simplicity. (Which, by the way, I may also have done above with regard to sums of lesser terms. For example, for summing I bounded $\log\log(2^ik)$ by $\log\log(2^{\log b}k)$.)