The following algorithm is provided in the paper PRIMES is in P at the beginning of section 4.


However, I am struggling to see how this is supposed to be a polynomial time algorithm. For example, consider line 1. To check whether $n$ is expressible in the form $a^b$ (for $a \in \mathbb{n}$ and $b > 1$) we might use code such as the following

a, b = 2, 2
while n != pow(a,b) and pow(a,2) <= n:
     while pow(a,b) <= n:
          b = b+1
     b = 2
     a = a+1

where pow(a,b) denotes $a^b$. Clearly this has complexity $O(n^2)$ which is not polynomial with respect to the size (number of digits in) $n$. So this step cannot be done in polynomial time.

Does this not mean that this algorithm does not run in polynomial time, and thus the assertion that "PRIMES is in P" is invalid?

  • 2
    $\begingroup$ Which is more likely? That you have misunderstood the algorithm or its time complexity, or that everybody is wrong about it? $\endgroup$ Feb 23 '18 at 14:43
  • $\begingroup$ No, $n^2$ is not polynomial with regards to the size of $n$ (in terms of how many digits $n$ has). If $n$ increases by 1 digit then the size of $n$ has increased by a multiple of at least 10... Please think before leaving non-constructive comments, especially if you don't understand how complexity is measured. $\endgroup$
    – M Smith
    Feb 23 '18 at 14:51
  • $\begingroup$ You would do well to learn the difference between "I don't know how to do this step in polynomial time" (which is what you have shown) and "this step cannot be done [by anyone] in polynomial time" (which you assert, falsely). $\endgroup$
    – user856
    Feb 23 '18 at 15:09
  • $\begingroup$ That distinction should have been implied by the question mark, Rahul. $\endgroup$
    – M Smith
    Feb 23 '18 at 15:10

If you read further in the paper, they explain each step's complexity, albeit not in immense detail as this is well covered by other papers and books.

Section 5, first line of Theorem 5.1 proof, says step 1 (perfect power detection) is $\tilde{O}(\log^3 n)$. Their reference (Gathan and Gerhard 1999) in turn references the papers of Bach and Sorenson (1993) and Bernstein (1998) which we can look up, and I've provided a link to each.

For a practical implementation, see mpn/perfpow.c in GMP.

For your larger question, I've written multple AKS implementations in C+GMP, and they show very clear polynomial $O(\log^{6+\epsilon} n)$ behavior in practice. The later Bernstein variants are, as expected, orders of magnitude faster than the V6 paper, but just as Bernstein describes, it has the same asymptotic complexity. All of them are very slow compared to practical deterministic primality tests such as APR-CL and ECPP, which both matches the expected theoretical results as well as other researcher's practical results (e.g. Brent and Bernstein).


The highest possible exponent is when $a=2$, and $b=\log_2N$. This is linear in the number of digits of $N$. So, for $b=2$ to $\log_2N$, check whether $N^{1/b}$ is an integer.


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.