\documentclass[10pt]{article}
\usepackage{amsfonts}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\bf Z}}
%\usepackage{psfig}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\begin{document}
\input{preamble.tex}
\newcommand{\NP}{\mathsf{NP}}
\newcommand{\coNP}{\mathsf{coNP}}
\newcommand{\RP}{\mathsf{RP}}
\newcommand{\coRP}{\mathsf{coRP}}
\newcommand{\polylog}{\mathsf{polylog}}
\renewcommand{\poly}{\mathsf{poly}}
\renewcommand{\bmod}[1]{\ (\mathrm{mod}\ #1)}
\newcommand{\ZZ}{\mathbb{Z}}
\lecture{12}{March 16th}{Madhu Sudan}{Chiheon Kim}
\section{Introduction}
Today we are going to talk about primality testing algorithm by Agarwal, Kayal, and Saxena.
The problem is following.
\begin{center}
Given an integer $N$, determine if $N$ is a prime.
\end{center}
There is a sequence of results dealing with this problem.
\begin{itemize}
\item By definition, Primality is in $\coNP$. Any nontrivial factorization of $N$ is a short proof that the $N$ is not a prime.
\item {[Pratt '75]}\footnote{Pratt, V. (1975), "Every Prime Has a Succinct Certificate." SIAM J. Comput. 4, 214-220.} Primality is in $\NP$. Note that $N$ is prime if and only if there is $a \in \left(\ZZ_N\right)^{\times}$ such that $\ord_N(a) = N-1$, i.e., $a^{N-1} = 1 \bmod{N}$ but $a^{(N-1)/q} \neq 1 \bmod{N}$ for all prime $q$ dividing $N-1$. We recursively give certificates that each of $q$ is prime, so the total length of proof is $\polylog(N)$.
\item {[Solovay-Strassen '77]}\footnote{Solovay, Robert M.; Strassen, Volker (1977). "A fast Monte-Carlo test for primality". SIAM J. Comput. 6 (1): 84–85.}{[Miller-Rubin '80]}\footnote{Rabin, Michael O. (1980), "Probabilistic algorithm for testing primality", J. Number Theory 12 (1): 128–138.} Primality is in $\coRP$. This result observes that if $N$ is not a prime, then there is $a$ and $k$ such that $a^{2k} = 1 \bmod{N}$ but $a^k \neq \pm 1 \bmod{N}$. Moreover, if we pick $a$ at random, then with probability at least half there is $k$ such that the test holds. Under Generalized Riemann Hypothesis, the test can be made deterministic by checking $\polylog(N)$ many $a$'s.
\item {[Goldwasser-Kilian '86]}\footnote{S. Goldwasser, J. Kilian (1986), Almost all primes can be quickly certified, STOC 1986, 316-329}{[Adleman-Huang '87]}\footnote{Leonard M. Adleman, Ming-Deh A. Huang (1987), Recognizing Primes in Random Polynomial Time. STOC 1987: 462-469} Primality is in $\RP$. They used elliptic curves to prove the result.
\item In 2003, Agarwal, Kayal, and Saxena proved that Primality is in $\mathsf{P}$.
\end{itemize}
\section{Another proof of Primality $\in \coRP$}
In 2000, Agrawal and Biswas proved that Primality is in $\coRP$ using different identity\footnote{M. Agrawal, S. Biswas (2003), Primality and Identity Testing via Chinese Remaindering. J. ACM, 50(4):429–443.}. Observe that if $N$ is a prime, that $(x+a)^N = x^N + a^N = x^N + a \bmod{N}$ for any $a$. We think it as a polynomial identity. We claim that converse is also true.
\begin{lemma} If $N$ is a composite* (here we mean that $N$ has two distinct prime factors) then $(x+a)^N \neq x^N+a \bmod{N}$ for any $a$ which is coprime to $N$.
\end{lemma}
\begin{proof}
Let $N = P^i Q$ where $P$ is a prime and $P^i$ doesn't divide $Q$. Then, the coefficient of $x^{N-P^i}$ in $(x+a)^N$ is $a^{P^i} \binom{N}{P^i}$. But $a^{P^i} = a \bmod{P}$ and $\binom{N}{P^i} \neq 0 \bmod{P}$, so the coefficient cannot be zero.
\end{proof}
Now we want to check the polynomial identity $(x+a)^N = x^N + a \bmod{N}$. It is inefficient to write down all the coefficients of $(x+a)^N$, so Agrawal and Biswas proposed a probabilistic way to reduce the degree of polynomial.
\begin{itemize}
\item Pick irreducible $Q(x) \in \ZZ_{N}[x]$ with $\polylog(N)$ degree at random.
\item Accept if $(x+a)^N = x^N + a \bmod{N, Q(x)}$.
\end{itemize}
We can compute $(x+a)^N \bmod{N, Q(x)}$ in $\polylog(N)$ time using repeated squaring.
If $N$ is a prime, the test will always accept. If $N$ is composite*, then we have $(x+a)^N \neq x^N+a \bmod{N}$. We claim that the number of (monic) irreducible polynomial $Q$ of degree at most $\polylog(N)$ such that $(x+a)^N = x^N + a \bmod{N, Q(x)}$ is at most $N$. This is because if we have $Q_1, \cdots, Q_{N+1}$ satisfying the identity, then the identity holds for $Q = Q_1 \cdots Q_{N+1}$ due to Chinese Remainder Theorem. We have $\deg(Q) > N$, so $(x+a)^N = x^N+a \bmod{N}$. There are roughly $\approx 2^{\polylog(N)}$ irreducible $Q$, so with high probability the test fails.
\section{Agrawal-Kayal-Saxena Primality Testing}
In 2003, Agrawal, Kayal, and Saxena proved that Primality is in $\mathsf{P}$\footnote{Agrawal, M., Kayal, N., Saxena, N. (2004), PRIMES is in P. Annals of Mathematics 160 (2): 781–793}. Instead of picking $Q$ at random, they used $Q(x) = x^r - 1$ for some nice prime $r$ along with $\polylog(N)$ many choices of $a$'s. The algorithm is as follows.
\begin{enumerate}
\item Choose a prime $r$ such that $\ord_{r}(N) \geq \polylog(N)$.
\item For $a=1,\cdots,A$, test if $(x+a)^N = x^N+a \bmod{N, x^r-1}$.
\item Accept if all tests accepts.
\end{enumerate}
Prime Number Theorem implies that for any integer $k \geq 1$, there is a prime $r = O(k^2 \log N)$ such that $\ord_r(N) \geq k$. So, for $k = \polylog(N)$ we can test all $r \leq \polylog(N)$ to find a good one. We defer the proof to next lecture.
It is always nice to work with a ring, so let $R = \ZZ[x] / (N, x^r-1)$. This ring has a lot of zero divisors, hence is not a field. Fix a prime divisor $p$ of $N$ and let $L = \ZZ[x]/(p, x^r-1)$. Moreover, fix an irreducible factor $h(x)$ of $x^r-1$ in $\ZZ_p[x]$. Define $K = \ZZ[x] / (p, h(x))$. Then $K$ is a field. It is immediate to see that if $f=0$ in $R$, then $f=0$ in $L$ and $K$.
From now on, we fix $N$ and $r$.
\begin{definition}
$f(x) \in \ZZ[x]$ is introverted with respect to $m \in \ZZ^+$ if $f(x^m) = f(x)^m \bmod{p, x^r-1}$.
\end{definition}
Note that $x+a$ is introverted with respect to $N$. From this fact, we can generate lots of introverted polynomials with respect to many numbers.
\begin{proposition}
If $f$ and $g$ are introverted with respect to $m$, then $fg$ is also introverted with respect to $m$. If $f$ is introverted with respect to $m_1$ and $m_2$, then $f$ is introverted with respect to $m_1 m_2$.
\end{proposition}
\begin{proof}
The first part is easy, as $f(x^m)g(x^m) = f(x)^m g(x)^m = (fg)(x)^m \bmod{p, x^r-1}$. For the second part, note that $f(x^{m_1}) = f(x)^{m_1} \bmod{p, x^r-1}$ implies that $f(x^{m_1m_2}) = f(x^{m_2})^{m_1} \bmod{p, x^{rm_2}-1}$. Since $x^r-1$ divides $x^{rm_2}-1$, we have $f(x^{m_1m_2}) = f(x^{m_2})^{m_1} \bmod{p, x^r-1}$. Hence, $f(x^{m_1m_2}) = f(x)^{m_1m_2} \bmod{p, x^r-1}$ as desired.
\end{proof}
Due to the proposition, we know that $\{\prod_{d_a \geq 0} (x+a)^{d_a} \mid d_a \geq 0\}$ are introverted with respect to $\{N^i p^j \mid i, j\geq 0\}$.
\begin{proposition}
If $f(x) \in \ZZ[x]$ is introverted for distinct $m_1$ and $m_2$ such that $m_1=m_2 \bmod{r}$. Then $f(x)$ as in $K$ is a zero of $z^{m_1}-z^{m_2} \in K[z]$.
\end{proposition}
\begin{proof}
In $L = \ZZ[x]/(p, x^r-1)$, we have $f(x)^{m_1} - f(x)^{m_2} = f(x^{m_1})-f(x^{m_2}) \bmod{p, x^r-1}$. Since $x^{m_1} = x^{m_1 \bmod{r}}$ and $x^{m_2} = x^{m_2 \bmod{r}}$ in $L$, we have $f(x)^{m_1}-f(x)^{m_2} = 0 \bmod{p, x^r-1}$. This identity holds in $K$, so $f(x) \in K$ is a root of $z^{m_1}-z^{m_2}$.
\end{proof}
Suppose that there are distinct $m_1, m_2 \leq B$ with $m_1=m_2 \bmod{r}$. If there were distinct $f_1(x), \cdots, f_{B+1}(x)$ in $K$ such that each $f_i$ is introverted with respect to $m_1$ and $m_2$, then $z^{m_1}-z^{m_2}$ has $B+1$ distinct roots. But this is impossible because $K$ is a field.
The main idea of AKS primality testing is as follows. We know that any polynomial in
$$
\mathcal{F} := \left\{\prod_{a \leq A} (x+a)^{d_a} \mid d_a\geq 0\right\}
$$
is introverted with respect to any number of the form $N^i p^j$. For $\{N^i p^j \mid 0\leq i, j \leq \sqrt{r}\}$, by Pigeonhole there are distinct $m_1$ and $m_2$ in this set, satisfying $m_1 = m_2 \bmod{r}$. Moreover, $m_1$ and $m_2$ are at most $N^{2\sqrt{r}}$. On the other hand, the number of polynomials in $\mathcal{F}$ is more than $2^A$. If they are distinct in $K$, by Proposition 4 there are $2^A$ roots for $z^{m_1}-z^{m_2}$, so $2^A \leq N^{2\sqrt{r}}$. But if we take large enough $A = \Theta(\polylog(n))$, this cannot happen, contradicting that $N$ is composite*.
Here we assumed that polynomials in $\mathcal{F}$ are distinct enough modulo $p$ and $h(x)$. This is indeed true if we restrict polynomials having degree at most the degree of $h(x)$. But this degree could be very small, so we need to ensure that (1) $p$ is large, and (2) every irreducible factor of $x^r-1$ in $\ZZ_p[x]$ has degree $\approx \polylog(N)$. We will give a detailed analysis in next lecture.
\end{document}