\documentclass[10pt]{article}
\usepackage{amsfonts}
\let\E\relax
\usepackage{complexity}
\usepackage{mathtools}
\usepackage[mathscr]{euscript}
\newcommand{\sF}{\mathscr{F}}
\newcommand{\lcm}{\mathrm{lcm}}
%\usepackage{epsfig}
\begin{document}
\input{preamble.tex}
\lecture{13}{Mar 18, 2015}{Madhu Sudan}{Daniel Grier}
\section{Overview - Deterministic Primality Testing}
Last time we saw the major components of the AKS deterministic test for primality. Today we will finish the analysis. We first present the approach given in the original paper which relies on a rather strong number theoretic statement. We then give a more sophisticated analysis which will allow us to use a weaker number theoretic statement, which follows straightforwardly from the prime number theorem. In fact, we will even show an elementary proof of the prime number theorem, allowing us to prove that primality testing is achievable in polynomial time without any number-theoretic assumptions.
\section{Review of AKS Algorithm}
Let $N$ be the number that we are testing for primality. Let $A = \{1, 2, \ldots, \polylog(N)\}$. Choose prime $r = O(\polylog N)$. The method by which we choose our prime $r$ will depend on our number-theoretic assumption. Assume for now that it is given. The test for primality is as follows:
\begin{itemize}
\item Verify that $N$ has no divisors in $A$.
\item Verify that $N$ is not a prime power. This can be accomplished in $\polylog$ time by checking that for each $t \in \{2,3,\ldots, \log N\}$ that $N \neq m^t$ by binary searching on the value of $m$.
\item For all $a \in A$ verify $$x^N + a \equiv (x + a)^N \pmod{N, x^r -1}$$
\item If all tests pass, then output that $N$ is prime.
\end{itemize}
\section{Analysis}
It is clear that the test passes if $N$ is a prime. Assume, by contradiction, that $N$ passes the test but is composite. In particular, let $p$ be some prime divisor of $N$. Although the algorithm is really working in the ring $R := \Z[x]/(N, x^r -1)$, it will be convenient in the analysis to work with the rings $L := \Z[x]/(p, x^r -1)$ and $K := \Z[x]/(p, h(x))$ where $h(x)$ is an irreducible factor of the polynomial $\frac{x^r - 1}{x-1} \in \Z_p[x]$. Notice that identities in $R$, imply identities in $L$ and $K$, and that identities in $L$ imply identities in $K$. The magic of the proof is finding nice properties of certain polynomials in $L$, which will therefore hold in $K$; however, the fact that $K$ is actually a field, will allow us to draw a contradiction.
\begin{definition} A polynomial $f \in \Z[x]$ is \emph{introverted} with respect to $m$ if $$f(x^m) \equiv f(x)^m \pmod{p, x^r -1}$$ \end{definition}
Because we assumed $N$ passed the test, we have that the polynomial $x+a$ is introverted with respect to $N$ and $p$ for all $a \in A$. Furthermore, by the properties of introversion that we saw last time, we have that all polynomials in the family
$$\sF := \left\{\prod_{a \in A}(x+a)^{d_a} \mid d_a \ge 0\right\}$$
are introverted with respect to any element of $\{N^i p^j \mid i, j \ge 0\}$.
\begin{lemma}
\label{lem:pigeonhole}
If $f$ is introverted with respect to distinct $m_1, m_2$ but $m_1 \equiv m_2 \pmod{r}$, then $f(x)$ is a root of $z^{m_1} - z^{m_2} \in K[z]$.
\end{lemma}
\begin{proof}
$$f(x)^{m_1} \equiv f(x^{m_1}) \equiv f(x^{m_2}) \equiv f(m)^{m_2}$$
where the first and last equalities use introversion, and the second equality leverages the fact that we are working mod $x^r -1$ in $K$.
\end{proof}
The reason that we want to work in the field $K$ now becomes clear. Because $K$ is a field, the polynomial $z^{m_1} - z^{m_2}$ has at most $\max(m_1, m_2)$ roots. If we can find $m_1$ and $m_2$ that are relatively small compared to the number of polynomials that are roots of $z^{m_1} - z^{m_2}$, we will have arrived at a contradiction.
If we choose $m_1$ and $m_2$ from the set $\{N^i p^j \mid i, j \ge 0\}$, then $\sF$ is a natural large class of functions where we can look for a contradiction. This is exactly what we will do.
\begin{lemma}
$\exists$ distinct $m_1, m_2 \in \{N^i p^j \mid i, j \ge 0\}$ such that $m_1 \equiv m_2 \pmod{r}$ and $\max(m_1, m_2) \le N^{2\sqrt{r}}$.
\end{lemma}
\begin{proof}
First notice that all elements of $\{N^i p^j \mid i, j \ge 0\}$ are distinct because $N$ is composite and not a prime power. Therefore, there if we consider $i$ and $j$ in the range from $0$ to $\sqrt{r}$, we have $(\lfloor\sqrt{r}\rfloor + 1)^2 > r$ distinct numbers of the form $N^i p^j$ which are less than $N^{2\sqrt{r}}$. By the pigeonhole principle we must have two settings of $i$ and $j$ such that $N^i p^j$ are equivalent mod $r$.
\end{proof}
There are two things one might now worry about. First, for $a, b \in A$ perhaps $x + a$ is equivalent to $x + b$ in $K$ so that these two polynomials are actually identical (i.e. ruining our argument that the polynomial has too many roots). This would imply however that either $a \ge p$ or $b \ge p$, which shows that $p$ is an element of $A$. Recall now that we explicitly checked for this condition in the test, so this is impossible.
Secondly, one might worry that many different elements in $\sF$ would be equivalent mod $h(x)$. This is where we will invoke the strong number theoretic statement that we can in fact find an $h(x)$ such that $\deg h(x) \ge r^{1/2} \polylog(N)$. If we only consider polynomials in $\sF$ of degree less than the degree of $h(x)$, then they will all be distinct in $K$. This motivates the following definition.
Let $\sF_t := \{ f \in \sF \mid \deg(f) \le t\}$. A simple counting argument shows that $|\sF_t| = \binom{t + |A|}{t}$. If we let $|A| = t = \deg h - 1$, we get that $|\sF_t| \ge 2^{r^{1/2}\polylog N} \gg N^{2\sqrt{r}}$, which completes the argument that primality testing can be done in polynomial time.
\section{Analysis that Relies on Less Number Theory}
We now give up the assumption that we can find an $h(x)$ with large degree. We instead rely on a relatively weak number-weak theoretic fact that we can find a prime $r$ with large order. First define $\ord_r(N) := |\{N \mod r, N^2 \mod r, \ldots, N^r \mod r\}|$.
\begin{claim}
There exists prime $r$ such that $\ord_r(N) \ge \polylog N$.
\end{claim}
Let $l := |\{ N^i p^j \pmod r \mid i, j \ge 0 \}|$. It is clear that $\ord_r(N) \le l \le r$. Using the same pigeonhole argument of Lemma~\ref{lem:pigeonhole}, we can show that there exist distinct $m_1, m_2 \le N^{2\sqrt{l}}$ such that $m_1 \equiv m_2 \pmod r$. Notice then that if we let $|A| = l$ we get
$$|\sF_{l-1}| \ge 2^l \gg N^{2\sqrt l}$$
if $l > \log^2 N$, which we get from our number-theoretic assumption. If we can show that all polynomials in $\sF_{l-1}$ are distinct when viewed in the field $K$, then we would be done. This is what we will show.
\begin{lemma}
If $f, g \in \sF_{l-1}$, then $f \neq g \pmod {h(x)}$.
\end{lemma}
\begin{proof}
First view $f, g$ as polynomials in $\Z_p[z]$. Since $\Z_p$ is a subfield of $K$, we can consider $f(z) - g(z)$ as a polynomial in $K[z]$. Assume now that $f \equiv g \pmod{h(x)}$, which implies that $h(x) | f(x) - g(x)$, so $x$ is a root of the polynomial $f(z) - g(z)$.
We now give $l$ possible roots of $f(z) - g(z)$ of the form $x^m$. This follows from the fact that for every $m \in \{N^i p^j \pmod r\}$ we have
\begin{align*}
f(x^m) - g(x^m) &\equiv f(x)^m - g(x)^m \\
&= (f(x) - g(x))(f(x)^{m-1} + f(x)^{m-2}g(x) + \ldots + g(x)^{m-1}) \\
&\equiv 0 \pmod{h(x)}
\end{align*}
Since the degree of $f(z) - g(z)$ is less than $l$ we must have that $x^a \equiv x^b \pmod{p, h(x)}$ for $a < b$, so $h(x) | x^a(x^{b-a} - 1)$. Recall that $h(x) | x^r - 1$ and is irreducible, so there must be some $i < r$ such that $h(x) | x^i - 1$. This implies that $h(x) | x^{\gcd(i, r)} -1$. We know $r$ is prime, so $h(x) | x - 1$; however, we explicitly forbid $h(x)$ dividing $x -1$ in our choice of $h(x)$ leading to the contradiction.
\end{proof}
We now show that the number theoretic fact follows easily from a weak form of the prime number theorem. Let $\#(m)$ be defined as the number of distinct primes less than $m$.
\begin{theorem}[Prime Number Theorem]
$$\#m \ge c \frac{m}{\log m}$$
for some constant $c$.
\end{theorem}
\begin{proof}
Consider the integral $\int_0^1 x^m (1-x)^m \mathrm{d}x$. If we just expand out $x^m (1-x)^m$ and use the power rule, then we get that this integral is equal to some positive integer $z$ divided by the $\lcm(m+1,m+2, \ldots, 2m + 1) = \lcm(1,2, \ldots, 2m + 1)$. Also, in the interval [0,1], we have that $x(1-x) \le 1/4$. Stringing this together we have
$$\frac{z}{\lcm(1,2, \ldots, 2m+1)} = \int_0^1 x^m(1-x)^m \mathrm{d}x \le \frac{1}{4^m}$$
Noticing that $\lcm(1,2,\ldots m) \le m^{\#(m)}$ we get
$$z 4^m \le \lcm(1,2, \ldots, 2m+1) \le (2m+1)^{\#(2m + 1)}$$
Changing variables we get
$$\#m \ge \log_{m} z 2^{m - 1} = \frac{\log (z 2^{m-1})}{\log m} \ge \frac{m-1}{\log m} \ge c \frac{m}{\log m}$$
for some appropriately chosen $c$.
\end{proof}
Using the prime number theorem, we can now derive our weak number theoretic claim.
\begin{claim}
There exists prime $r$ such that $\ord_r(N) \ge \polylog N$.
\end{claim}
\begin{proof}
Suppose that for all prime $r \le \polylog N$, we have that $\ord_r(N) \le k$. For each $r$ there is some $i$ in the range 1 to $k$ such that $r | N^i -1$. For every prime $r\le \polylog N$ we have
$$r \bigg| \prod_{i=1}^k (N^i - 1)$$
but that $\prod_{i=1}^k (N^i - 1)$ is at most $N^{k^2}$. Assuming that $k \le \polylog N$ and using the prime number theorem, we know there exists an $m \le k^2 \log^2 N \le \polylog N$ such that $\#(m) > k^2 \log N$. If all primes of size at most $m$ divide $N^{k^2}$, then so must their products. However, the product of all the primes is at least $2^{\#(m)}$, which is greater than $N^{k^2}$ by construction.
\end{proof}
Relating this back to the original AKS algorithm, we can now find $r$ deterministically by simply brute forcing all possible primes less than some $\polylog N$.
\end{document}