# Primality in $NC$ hierarchy?

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.

• FWIW, Wikipedia says that this is open: en.wikipedia.org/wiki/Primality_test#Complexity . – Noah Stephens-Davidowitz Aug 4 '18 at 17:22
• 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. – Emil Jeřábek Aug 4 '18 at 18:47
• @EmilJeřábek Oh then if coprimality and modular exponentiation are in $NC$ then primality is in $NC$? Is either believed to be in $NC$? – 1.. Aug 4 '18 at 18:49
• 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.) – Emil Jeřábek Aug 4 '18 at 18:52
• @EmilJeřábek Is irreducibility testing dense polynomials in $\mathbb F_q[x]$ in $NC$? – 1.. Aug 4 '18 at 19:41