AKS primality testing solves whether a given integer is prime in $P$. AKS algorithm is following:

Input: integer n > 1.

  1. Check if $n$ is a perfect power: if $n = a^b$ for integers $a > 1$ and $b > 1$, output composite.

  2. Find the smallest $r$ such that $ord_r(n) > (\log_2 n)^2$ (if $r$ and $n$ are not coprime, then skip this $r$).

  3. For all $2 ≤ a ≤\min(r, n−1)$, check that $a$ does not divide $n$: If $a|n$ for some $2 ≤ a ≤ \min(r, n−1)$, output composite.

  4. If $n ≤ r$, output prime.

  5. For $a = 1$ to ${\displaystyle \left\lfloor \scriptstyle {{\sqrt {\varphi (r)}}\log_{2}(n)}\right\rfloor}$ do

    if $((X+a)^n - (X^n+a))≠0\bmod (X^r − 1,n)$, output composite;

  6. Output prime.

After Emil's comment note 5. is not in $NC$ hierarchy. It seems step 2. is not in $NC$ since $GCD$ is not known to be in $NC$.

Since we have $r\leq polylog(n)$ unconditional bound we may even look for smallest $r$ parallely (by testing $r|(n^k-1)$ in $NC$ at each of the parallel processor testing a different $r$) if coprimality is in $NC$ and we can use a boolean logic to combine steps 2 and 5 so they run in parallel. All other steps seem parallelizable wholly with some boolean logic.

So is it true that if coprimality testing (rather than $GCD$ finding) and polynomial identity testing for this particular polynomial in 5. proved in $NC$ then primality is in $NC$?

It seems it is possible coprimality is in $NC$. Note this is easier than $GCD$ finding.

  • 1
    $\begingroup$ FWIW, Wikipedia says that this is open: en.wikipedia.org/wiki/Primality_test#Complexity . $\endgroup$ – Noah Stephens-Davidowitz Aug 4 '18 at 17:22
  • 4
    $\begingroup$ Step 5 is not in NC, as it amounts to modular exponentiation, which requires $\log n$ sequential iterations. Also, this step is totally garbled. I see that you copied it from Wikipedia, where it was apparently vandalized. I’m going to revert it to the correct version. $\endgroup$ – Emil Jeřábek Aug 4 '18 at 18:47
  • $\begingroup$ @EmilJeřábek Oh then if coprimality and modular exponentiation are in $NC$ then primality is in $NC$? Is either believed to be in $NC$? $\endgroup$ – user124864 Aug 4 '18 at 18:49
  • 1
    $\begingroup$ Neither is believed to be in NC, as far as I am aware. (Note that in the correct version of the algorithm, it is modular exponential of polynomials, not integers, which only makes it more complicated.) $\endgroup$ – Emil Jeřábek Aug 4 '18 at 18:52
  • $\begingroup$ @EmilJeřábek Is irreducibility testing dense polynomials in $\mathbb F_q[x]$ in $NC$? $\endgroup$ – user124864 Aug 4 '18 at 19:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.