2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$ – Raphael Feb 26 '18 at 12:43
  • 2
    $\begingroup$ @M Smith Most probably they will be doing the binary search on numbers between 2 and $\log n$. This will give the time $O(\log^2 n)$. $\endgroup$ – Complexity Feb 26 '18 at 12:58
  • 1
    $\begingroup$ I think Ariel has already posted the answer. You should take a look at the Wikipedia link he gave you. $\endgroup$ – Willard Zhan Feb 26 '18 at 16:48
  • 4
  • 1
    $\begingroup$ The operation to be performed is “is the b-th root of a an integer”. Is that s constant time operation for n bit integers? $\endgroup$ – gnasher729 Feb 26 '18 at 19:35
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There are also some fast pre-tests that can very quickly reject large percentages of arbitrary inputs. Bloom filters (fastest) or some modular methods as shown in Cohen and elsewhere (Cook has a blog about it also, though he doesn't discuss bloom filters). This is a big speedup for the many algorithms that do millions of tests on native size (e.g. 64-bit) inputs. I like your description of the partial precision method, which I think GMP uses. $\endgroup$ – DanaJ Apr 3 '18 at 18:44
1
$\begingroup$

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

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