\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{\PRIME}{\textsc{Prime}}
\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}

\lecture{12}{March 19, 2012}{Madhu Sudan}{Zeyuan Allen Zhu}

\section{Today's Problem: Primality Testing}
\begin{center}
Given an $n$-bit integer $N$, output YES if $n$ is prime and NO otherwise.
\end{center}
This is one of the most basic questions about numbers, with the following history.
\begin{itemize}
\item By definition $\PRIME\in\coNP$, because the prime decomposition is a short certificate for a number that is not prime.
\item $ $[Pratt'75] showed that $\PRIME \in \NP$. The Pratt certificate of a number $N$ being prime, is by looking at all prime factor $q$ of $N-1$ (which will be proved recursively), and giving some $a$ such that $a^{(N-1)/q}\not\equiv 1\pmod{N}$ for all such $q$'s. This proof is of length $\polylog N$.
\item The subsequent discoveries by [Solovay-Strassen'70s] [Miller-Rabin'70s] put $\PRIME$ in $\coRP$. This algorithm uses the fact that if there exists some $a,k$ such that $a^{2k}\equiv 1\ (\bmod{n})$ but $a^{k}\not\equiv \pm1\ (\bmod{n})$ then $N$ is composite. Moreover, the probabilistic algorithm picks $a$ at random, and with $>1/2$ probability there will be some $k$ satisfying such compositeness criterion if $N$ is composite.
\item $ $[Goldwassar-Killian'86] [Adleman-Huang'87] used algebraic (elliptic curve) techniques and proved that $\PRIME\in\RP$.
\item In 2002, Agarwal, Kayal, and Saxena finally put $\PRIME$ in $\mathsf{P}$, and this will be the main topic of today.
\end{itemize}

\section{Prelude: Agarwal-Biswas Probabilistic Testing}
\begin{lemma}
For all $a$ such that $(a,N)\neq 1$,
$$N\textrm{ is a prime }\Longrightarrow (x+a)^N \equiv x^N+a\pmod{N} \Longrightarrow N \textrm{ is a prime power.} $$
\end{lemma}
\begin{proof}
The first ``$\Longrightarrow$'' is easy. For the second one, if $N=B\cdot C$ and $(B,C)=1$, then after some careful calculation one can verify that $\binom{N}{B} \equiv C \not\equiv 0\ (\bmod{N})$. This means, the coefficient for the $x^B$ term does not equal to zero in the expansion of $(x+a)^N = \sum_{i=0}^N x^i a^{N-i} \binom{N}{i}$.
\end{proof}

The lemma reduces our number theoretical question to an algebraic question of checking whether $(x+a)^N \equiv x^N+a\ (\bmod{N})$. However, we cannot write down this big expansion explicitly, because we want an algorithm that runs in time $O(\poly(n)) = O(\polylog N)$. [Agarwal-Biswas'99] then proposed the following test:
\begin{itemize}\itemsep -1pt
\item pick a monic polynomial $Q\in\mathbb{Z}_N[x]$ of degree $\polylog N$ at random; then
\item verify if $(x+a)^N \equiv x^N+a\pmod{Q}$.
\end{itemize}

This is an efficient algorithm because the degree of $Q$ is small and we can use power method to compute $(x+a)^N\ \bmod{Q}$ in $\polylog N$ time. The correctness can be verified using the following two properties:
\begin{itemize}
\item With probability at least $\frac{1}{\deg Q}$, $Q$ is irreducible over mod $N$. This is because letting $d=\deg Q$,
$$x^{q^d}-x = \prod (\textrm{all irred. polys. of degree dividing }d )\enspace,$$
and thus counting the degree on both sides we have at least $\frac{q^{d}}{d}$ irreducible polynomials of degree dividing $d$, and since there are a total of $q^d$ choices for monic polynomials of $Q$ over $\mathbb{F}_p$, at least with probability $\frac{1}{d}$ we will get a polynomial $Q$ that is irreducible over $\mathbb{F}_p$, and then of course $Q$ is also irreducible module $N$.
\item Conditioning on $Q$ being irreducible, the probability that $(x+a)^N \equiv x^N+a\ (\bmod{Q})$ if $N$ is composite is very very small due to the Chinese Reminder Theorem. This is because, if $(x+a)^N \equiv x^N+a\ (\bmod{Q})$ holds for many polynomials $Q_1,Q_2,\dots,Q_t$'s, then the congruence also holds module $\mathrm{lcm}(Q_1,Q_2,\dots,Q_t)$ due to Chinese Reminder Theorem, but when $\deg(\mathrm{lcm}(Q_1,Q_2,\dots,Q_t))$ exceeds $N$ we will have $(x+a)^N \equiv x^N+a\ (\bmod{N})$ as well because the degree on both sides are only $N$, contradicting the fact that $N$ is composite.
\end{itemize}

\section{Derandomization: Agarwal-Kayal-Saxena Primality Testing}
[Agarwal-Kayal-Saxena'02] considered the nice form $Q(x)=x^r-1$ for some nice prime $r=\Theta(\polylog N)$, and their primality testing is as follows:
\begin{itemize} \itemsep -0.5pt
\item Pick some prime $r=\Theta(\polylog N)$.
\item Pick $A=\{1,2,\dots,\polylog N\}$.
\item Verify if $N=m^t$ for integer $t$, and output NO if this happens.

\emph{(By enumerating all possible choices of $t$ and computing $m$ using binary search for each $t$.)}
\item Verify if $\exists a\in A$ divides $N$, and output NO if this happens.
\item Verify if for all $a\in A$, we have $(x+a)^N \equiv x^N+a \pmod{N,x^r-1}$. Output YES if this is true, and NO if there exists some $a\in A$ that fails the test.
\end{itemize}

%Madhu - changed below
\noindent \emph{(The proof of AKS (to be shown below) is quite a novel one. Prof. Madhu Sudan claims no such proof was seen before in either the CS or number theory literature.)}

Notice that $R:=\mathbb{Z}[x]/(N,x^r-1)$ is not a field, because it is module $N$ which is not a prime, and module $x^r-1$ which might not be irreducible. In fact, if we define $p$ to be any prime divisor of $N$, we can let $L:=\mathbb{Z}[x] / (p,x^r-1)$, while identities in $R$ imply these in $L$. We can go another step further, by letting $h(x)$ to be any irreducible factor of $\frac{x^r-1}{x-1}$ in $\mathbb{F}_p[x]$, and define $K:=\mathbb{Z}[x] / (p,h(x))$. Now, $K$ is finally a field, and although $R$ is the ring we are performing the primality testing, $K$ is where we are going to work on the proof. Notice that identities in $R$ also hold in $K$.

%Madhu - added below

\paragraph{Proof overview:} The main idea of the proof is to find a large collection
of polynomials ${\cal F} \subseteq \Z[x]$ that, when viewed as elements of $L$
satisfy several ``semi''-nice ``near''-algebraic conditions (called introversion below),
assuming $N$ passes the AKS test.
The key idea in AKS is to convert this ``semi''-nice ``near''-algebraic conditions
into a ``pure'' algebraic one, i.e., in the form of a non-zero polynomial ${\cal P} \in K[z]$
such that every element of ${\cal F}$, when viewed as an element of $K$, is a zero
of ${\cal P}$. This conversion is neat in that ${\cal P}$ has low-degree if (and potentially
only if) $N$ is not a prime power. This leads to a contradiction because ${\cal P}$ now
has many distinct zeroes (namely appropriately chosen elements of ${\cal F}$) while
its degree is small! (Note that if $N$ had been a prime, the degree of ${\cal P}$ would
have been much larger and so the presence of so many zeroes would be perfectly OK.)

\begin{definition}[Introversion]
We say that $f(x)\in L$ is \emph{introverted} for $m$ if $f(x^m)\equiv f(x)^m$ in $L$.
\end{definition}

\begin{proposition} $ $
\label{prop}
\begin{enumerate}\itemsep -1pt
\item For any $a\in A$, $f(x)=x+a$ is introverted for $m=N$ (if $N$ passes the test);
\item for all $f(x)\in L$, $f$ is introverted for $m=p$;
\item if $f(x),g(x)\in L$ are both introverted for $m$, then $f(x)\cdot g(x)$ is introverted for $m$; and
\item if $f(x)\in L$ is introverted for both $a$ and $b$, then $f(x)$ is also introverted for $a\cdot b$.
\end{enumerate}
\end{proposition}
\begin{proof}
The first three propositions are trivial, so we only prove the last one. Starting from:
$$f(x)^a \equiv f(x^a) \pmod {x^r-1}\enspace, $$
we have:
$$f(z^b)^a \equiv f(z^{ba}) \pmod {z^{br}-1}\enspace.$$
Now, since $z^r-1 \vert z^{br}-1$, we also have:
$$f(z^b)^a \equiv f(z^{ba}) \pmod {z^{r}-1} \enspace,$$
and this is one place (and we will see another place shortly) that we have specific reason to use polynomials of the form $x^r-1$; in general, it may not be the case that $h(z)\vert h(z^b)$. We have not used any property of $r$ yet. At last, we have:
$$ f(z)^{ba}=f(z^b)^a \equiv f(z^{ba}) \pmod{z^{r}-1} \enspace.$$
\end{proof}


\begin{proposition}
If $f(x)\in L$ is introverted for $m_1$ and $m_2$ while $m_1 = m_2\ (\bmod{r})$, then $f(x)^{m_1}=f(x)^{m_2}$.
\end{proposition}
\begin{proof}
$f(x)^{m_1} = f(x^{m_1}) = f(x^{m_2})=f(x)^{m_2}$ and the second equality is because $m_1 \equiv m_2\ (\bmod{r})$ and we are in the ring module $x^r-1$.
\end{proof}


\subsection{High Level Ideas for the Analysis}
Now using above propositions, we want to find
\begin{itemize}\itemsep -1pt
\item a large set $\mathcal{F}$ of polynomials, even when viewed module $h(x)$, and
\item two small integers $m_1$ and $m_2$ satisfying $m_1=m_2\ (\bmod{r})$, such that for any $f(x)\in \mathcal{F}$, $f$ is introverted for both $m_1$ and $m_2$.
\end{itemize}

If we found such $m_1,m_2$, then all $f\in \mathcal{F}$ are roots to polynomial $\mathcal{P}(z):=z^{m_1}-z^{m_2}$, and although $f\in L$ and $L$ is not a field, but it is contained in $K$ which is a field, so $\mathcal{P}(z)\in K[z]$. Now notice that $\mathcal{F}$ is a large set of zeros of $\mathcal{P}(z)$, so if we had $|\mathcal{F}|>\max\{m_1,m_2\}$ we would have a contradiction.

\subsection{Details}
A very natural set $\mathcal{F}$ to consider is, for some fixed $t$, let
$$\mathcal{F}_t := \Big\{ \prod_{a\in A} (x+a)^{d_a} \Big| \sum_{a\in A} d_a \leq t\Big\} \enspace.$$
Then, $|\mathcal{F}_t| = \binom{t+|A|}{|A|}$. If we choose $t=|A|$ we always have $|\mathcal{F}_t| \geq 2^t$ being a large set. Notice that we still need to make sure that all polynomials in $\mathcal{F}_t$ are distinct module $h(x)$, but we will worry about this later.

Now, how to make $m_1$ and $m_2$ small? Recall from Proposition~\ref{prop} that all polynomials in $\mathcal{F}_t$ are introverted for all numbers in $\{ N^iP^j | 0\leq i\leq \sqrt{r}, 0\leq j\leq \sqrt{r}\}$. In fact, since this set has more than $r$ elements we can find two distinct $m_1,m_2 \leq N^{2\sqrt{r}}$ such that all polynomials in $\mathcal{F}_t$ are introverted for $m_1$ and $m_2$ and $m_1\equiv m_2\ (\bmod{r})$.\footnote{Notice that if we just look at all $N^i$ we can get $N^r$ naively, but using $p$ we can benefit.}

At last, we use the following powerful lemma

\begin{lemma}[Fourry'80s]
$\exists $ prime $r=O(\polylog N)$ s.t. for sufficiently large $p$, $\deg h(x) > r^{2/3}$.
\end{lemma}
Using the above lemma, if we pick $t=\deg h-1$ for $\mathcal{F}_t$, then $|\mathcal{F}_t| \geq 2^{r^{2/3}}$ and it contains only distinct polynomials module $h(x)$. Recall that $m_1,m_2\leq 2^{\sqrt{r}\log N}$, so this is sufficient to give the contradiction and is indeed the original proof. We emphasize here that one needs to check all small $r$'s because the Fourry lemma does not give an explicit construction for such prime $r$.

\subsection{Improved Analysis}
We will now potentially choose $t>\deg h$, but still try to argue that elements in $\mathcal{F}_t$ are distinct module $h(x)$. Let us define
$$T=\big\{ N^i p^j\ (\bmod{r})\ \big|\ i,j\in \mathbb{Z}^{\geq 0} \big\}\enspace,$$
and define $l=|T|\leq r$. We know that all polynomials in $\mathcal{F}_{\infty}$ are introverted for any $m\in T$. Now, let us consider a specific one $\mathcal{F}_{l-1}$, and will show that
\begin{itemize}\itemsep -1pt
\item elements of $\mathcal{F}_{l-1}$ are all distinct module $h(x)$ (which will be proved in Lemma~\ref{lemma2}).
\item $m_1,m_2\leq N^{2\sqrt{l}}$ (using similar proof as before), such that $m_1\equiv m_2\ (\bmod{r})$ and all polynomials in $\mathcal{F}_{l-1}$ are introverted for $m_1$ and $m_2$.
\end{itemize}

Now if we let $|A|=l-1$, we can lower bound $|\mathcal{F}_{l-1}|=\binom{l-1+|A|}{|A|}\geq 2^{l-1}$, and we will have a similar contradiction as before if $2^{l-1} > N^{2\sqrt{l}}$. This latter inequality will always be true when $l=|T|=\Omega(\log^2 N)$, to be shown in Lemma~\ref{lemma1}.

\subsection{Two Technical Lemmas}

\begin{lemma}
\label{lemma2}
Suppose $f\neq g$ and $f,g\in\mathcal{F}_{l-1}$ are introverted with respect to $m_1,\dots,m_l$ (all distinct $\bmod{r}$). Then
$f\not\equiv g\ (\bmod {h(x)})$.
\end{lemma}
\begin{proof}
We can view $f(z),g(z)\in \mathbb{F}_p[z]$ as $f(z),g(z) \in K[z]$ because $\mathbb{F}_p \subseteq K$. If $f(x)\equiv g(x) \pmod {h(x)}$, then $x\in K$ is a root of $f(z)-g(z)$ which is a non-zero polynomial with degree no more than $l-1$.

Now using introversion, we also have $f(x^m) = f(x)^m = g(x)^m = g(x^m)$ for each $m\in T$ so there are at least $l$ roots to $f(z)-g(z)$, so there must be true that $x^{m_i}\equiv x^{m_j}\ (\bmod{h(x)})$ for some distinct $m_i,m_j\in T$.
In such a case, we have both
\begin{eqnarray*}
x^{m_i - m_j}-1 &\equiv& 0\pmod {h(x)} \\
x^r - 1 &\equiv& 0 \pmod{h(x)}
\end{eqnarray*}
\emph{(This is another reason for our choice of polynomials like $x^r-1$).} We therefore have that $x^{\gcd(m_i-m_j,r)}-1\equiv 0\ (\bmod{h(x)})$, giving $x-1 \equiv 0\ (\bmod{h(x)})$ but this is against our choice of $h(x)$.
\end{proof}


\begin{lemma}
\label{lemma1}
There exists prime $r\leq O(k^2 \log N)$ such that
$$\big| \{N^i\ (\bmod{r})\ \big|\ i\}\big| \geq k \enspace.$$
Notice that by choosing choosing $k=\log^2 N$ we have $l=|T|\geq \big| \{N^i\ (\bmod{r})\ \big|\ i\}\big|\geq \log^2 N$.
\end{lemma}
\begin{proof}[not provided in class but can be found in prenotes]

Suppose this is not true for some prime $r$, that is $\big| \{N^i\ (\bmod{r})\ \big|\ i\}\big| < k$, then $r$ must divide the difference between $N^i$ and $N^j$ for some $0\leq i,j\leq k-2$, and therefore:
$$ r\ \Big\vert\ M := \prod_{i=1}^{k-2} (N^i-1)\enspace, \quad \textrm{ and } M\leq N^{k^2} \enspace.$$
However, if this is true for all prime $r$ that is below $m$, then we have
$$\prod_{p_i\leq m,\ p_i\textrm{\scriptsize{ is prime}}} p_i \leq M \leq N^{k^2}\enspace. $$
But this contradicts with Corollary~\ref{cor} below, when $m=\Omega(k^2 \log N)$.
\end{proof}

\begin{theorem}[Weak Prime Number Theorem]
$$ \Big| \big\{\textrm{prime number}\leq 2m+1 \big \} \Big| \geq \frac{m}{\log_4(2m+1)} \enspace.$$
\end{theorem}
\begin{proof}
Ommited, but it uses the fact that $\mathrm{lcm}(1,2,\dots,2m+1)\geq 4^m$. See the prenotes.
\end{proof}
\begin{corollary}\label{cor}
There exists some constant $c>1$ such that
$$\prod_{p_i\leq m,\ p_i\textrm{\scriptsize{ is prime}}} p_i > c^m \enspace. $$
\end{corollary}

\end{document}

