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

<p>Input: integer n > 1.</p>

<ol>
<li><p>Check if $n$ is a perfect power: if $n = a^b$ for integers $a &gt; 1$ and $b &gt; 1$, output composite.</p></li>
<li><p>Find the smallest $r$ such that $ord_r(n) &gt; (\log_2 n)^2$ (if $r$ and $n$ are not coprime, then skip this $r$).</p></li>
<li><p>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.</p></li>
<li><p>If $n ≤ r$, output prime.</p></li>
<li><p>For $a = 1$ to ${\displaystyle \left\lfloor \scriptstyle {{\sqrt {\varphi (r)}}\log_{2}(n)}\right\rfloor}$ do</p>

<p>if $((X+a)^n - (X^n+a))≠0\bmod (X^r − 1,n)$, output composite;</p></li>
<li><p>Output prime.</p></li>
</ol>

<p>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$. </p>

<p>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.</p>

<blockquote>
  <p>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$?</p>
</blockquote>

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

CC BY-SA 4.0
2018-08-04T17:22:57.200Z
FWIW, Wikipedia says that this is open: https://en.wikipedia.org/wiki/Primality_test#Complexity .
Noah Stephens-Davidowitz
CC BY-SA 4.0
2018-08-04T18:47:38.850Z
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
CC BY-SA 4.0
2018-08-04T18:49:11.840Z
@EmilJeřábek Oh then if coprimality and modular exponentiation are in $NC$ then primality is in $NC$? Is either believed to be in $NC$?
Turbo
CC BY-SA 4.0
2018-08-04T18:52:40.107Z
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
CC BY-SA 4.0
2018-08-04T19:41:19.000Z
@EmilJeřábek Is irreducibility testing dense polynomials in $\mathbb F_q[x]$ in $NC$?
Turbo
CC BY-SA 4.0
2018-08-06T13:08:43.017Z
Not to my knowledge.
Emil Jeřábek
CC BY-SA 4.0
2018-08-06T18:40:41.973Z
@EmilJeřábek From 2.4.8 here https://www.luke.maurits.id.au/files/misc/honours_thesis.pdf it seems if $gcd(p(x),(x^{q^n}-x))$ is in $NC$ then irreducibility testing of dense polynomials in $\mathbb F_q[x]$ is in $NC$. Degree $n$ I think might be factorable in $O(n)$ operations in $NC$. Just verifying possible bottlenecks.
Turbo
CC BY-SA 4.0
2018-08-07T10:42:28.803Z
Well, I would not call this a “bottleneck”, as it is essentially the complete algorithm. You don’t even need to factor $n$: $p(x)\in\mathbb F_q[x]$ of degree $d$ is irreducible if and only if it is coprime to $x^{q^n}-x$ for all $1\le n<d$.
Emil Jeřábek
CC BY-SA 4.0
2018-08-07T19:48:28.450Z
@EmilJeřábek True however $GCD$ is in $NC$ in $\mathbb F_q[x]$. Exponentiation is bottleneck process.
Turbo
CC BY-SA 4.0
2018-08-19T07:10:13.473Z
@EmilJeřábek Take binary representation of $q^n$ which is $q^n=\sum_{i=0}^{n\lceil \log q\rceil}a_i2^i$. It seems that since $2^i$ is fixed and only $a_i\in\{0,1\}$ changes it seems plausible that polynomial irreducibility is in non-uniform $NC$ and primality would be in non-uniform $NC$ if coprimality in non-uniform $NC$ as well?
Turbo
CC BY-SA 4.0
2018-12-02T09:06:15.673Z
@EmilJeřábek This claims coprimality of integers is in $NC$ https://pdfs.semanticscholar.org/e86e/8d7a267a29b9ad4ca112828109adfec55e8b.pdf. Is it true result?
Turbo
<cc.complexity-theory><complexity-classes><dc.parallel-comp><nt.number-theory><primes>
Primality in $NC$ hierarchy?
Turbo
# Primality in $NC$ hierarchy?

(Asked by: username_0 on 2018-06-16)

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.

**Tags:** cc.complexity-theory, complexity-classes, dc.parallel-comp, nt.number-theory, primes
> **Comments:**
> **username_1**: FWIW, Wikipedia says that this is open: https://en.wikipedia.org/wiki/Primality_test#Complexity .  
> **username_2**: 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.  
> **username_0**: @EmilJeřábek Oh then if coprimality and modular exponentiation are in $NC$ then primality is in $NC$? Is either believed to be in $NC$?  
> **username_2**: 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.)  
> **username_0**: @EmilJeřábek Is irreducibility testing dense polynomials in $\mathbb F_q[x]$ in $NC$?  
> **username_2**: Not to my knowledge.  
> **username_0**: @EmilJeřábek From 2.4.8 here https://www.luke.maurits.id.au/files/misc/honours_thesis.pdf it seems if $gcd(p(x),(x^{q^n}-x))$ is in $NC$ then irreducibility testing of dense polynomials in $\mathbb F_q[x]$ is in $NC$. Degree $n$ I think might be factorable in $O(n)$ operations in $NC$. Just verifying possible bottlenecks.  
> **username_2**: Well, I would not call this a “bottleneck”, as it is essentially the complete algorithm. You don’t even need to factor $n$: $p(x)\in\mathbb F_q[x]$ of degree $d$ is irreducible if and only if it is coprime to $x^{q^n}-x$ for all $1\le n<d$.  
> **username_0**: @EmilJeřábek True however $GCD$ is in $NC$ in $\mathbb F_q[x]$. Exponentiation is bottleneck process.  
> **username_0**: @EmilJeřábek Take binary representation of $q^n$ which is $q^n=\sum_{i=0}^{n\lceil \log q\rceil}a_i2^i$. It seems that since $2^i$ is fixed and only $a_i\in\{0,1\}$ changes it seems plausible that polynomial irreducibility is in non-uniform $NC$ and primality would be in non-uniform $NC$ if coprimality in non-uniform $NC$ as well?  
> **username_0**: @EmilJeřábek This claims coprimality of integers is in $NC$ https://pdfs.semanticscholar.org/e86e/8d7a267a29b9ad4ca112828109adfec55e8b.pdf. Is it true result?  

---

## 0 answers

