2
$\begingroup$

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.

$\endgroup$
  • 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 supports Monica 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$ – T.... 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 supports Monica Aug 4 '18 at 18:52
  • $\begingroup$ @EmilJeřábek Is irreducibility testing dense polynomials in $\mathbb F_q[x]$ in $NC$? $\endgroup$ – T.... Aug 4 '18 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.