\documentclass[10pt]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\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}

\lecture{15}{November 2, 2005}{Madhu Sudan}{Jinwoo Shin}

Although there were some randomized polynomial-time algorithms for
testing primality, the first deterministic polynomial-time algorithm
for testing primality was published in 2002 by Manindra Agrawal,
Neeraj Kayal and Nitin Saxena. In the previous lecture, we
understood its basic idea and studied some notions and concepts to
understand its correctness. Today, we will finish the proof of its
correctness.

\section{Notations}
For fixed $n$, define a nice $r$.

\begin{definition} $r$ is nice for $n$ if

- $r \nmid n$ and $r$ is a prime number

- $ord_r(n) > 4{\log}^2 n$ $(ord_r(n)$ is the smallest number $k$
such that $n^k = 1 \ (\rm{mod} \ r))$
\end{definition}
Then a small nice $r$ always exists.

\begin{proposition}
There exist a prime number less than $32\log^6 n$ which is a divisor
of $n$ or nice for $n$.
\end{proposition}
\begin{proof}
Let $\tau$ be $[4{\log}^2 n]$, and $N$ be $\prod_{i=0}^{\tau}(n^i -
1) \ (\leq n^{\tau^2})$. Suppose $ord_r(n) \leq \tau$ and $r$ is not
a divisor of $n$. Then $r \ | \ n^i -1$ for some $i \in \{
1,...,{\tau} \}$, so $r \ | \ N. $
$$The\ number\ of\ prime\ divisors\ of\ N \leq \log N \leq {\tau^2} \log n$$
If we try the first $k(={\tau^2} \log n +1 \leq 16\log ^5 n +1)$
primes as a candidate for $r$, one of them is nice or a divisor of
$n$. From the well-known weak theorem about the number of primes(The
$k$\ th prime is less than $2k \log k$),
$$The\ k\ th\ prime < 2k \log k \leq 2(16
\log^5 n +1)\log (16 \log^5 n +1) \leq 32\log^6 n$$
\end{proof}
\\\\ Now define 'intorospectiveness', the most useful concept in our
algorithm and its proof of correctness.
\begin{definition}
For polynomial $f(x)$, the positive integer $m$, and ring $R$, we
say that $m$ is \textbf{intospective} for $f(X)$ if
$$[f(X)]^m = f(X^m )\ in\ R$$
\end{definition}
Then we can get the following facts as proved in the previous
lecture.
\begin{fact}
\end{fact}
\begin{enumerate}
\item{If $m$ is introspective for $f(X)$ and $g(X)$ in $R$, it is also
introspective for $f(X) \cdot g(X)$ in $R$.}
\item{If $m_1$ and $m_2$ is introspective for $f(X)$ in $R \
(=\mathbb{Z} [X] / (n,X^r - 1)),$ then so is $m_1 \cdot m_2$.}
\item{If $m$ is introspective for $f(X)$ in $R$, then $m$ is also
introspective for $f(X)$ in $R^\prime$,the subring of $R$.}
\end{enumerate}

\section{Preliminaries}
In this section, introduce and summarize some constants and sets
will be used in this note. (There are many variables in the proof of
correctness of our algorithm. So
I am supposed to summarize them before entering the main section.)\\

- $n$ : our fixed number to test.

- $r$ : $r$ is nice for $n$ and less than $32 \log^6 n$.

- $p$ : the prime divisor of $n$ (if exists) and greater than
$r$.

- $l$ : $l$ can be any number between $r$ and $t$.

- $T$, $t$ : $T = \{n^i p^j | i,j \geq 0\}$, $t = |\{m \ (\rm{mod}\
r)| m \in T\}|$.

- $S$, $S_t$ : $S = \{ \prod_{a=1}^{l} (X+a)^{d_a} | d_a \geq 0\}$,
$S_t = \{f \in S | deg\ f < t\}$.

- $h(X)$ : $h(X)$ is an irreducible polynomial that divides
$\frac{X^r -1}{X-1}$.

- $R$, $K$ : $R = \mathbb{Z} [X] / (n,X^r - 1)$, $K = \mathbb{Z} [X]
/ (p,h(X))$.
\\\\We can check some properties of them which will play crucial roles
in the proof of correctness of our algorithm.
\begin{observation}
\end{observation}
\begin{enumerate}
\item $t<\ l\ <\ r\ <\ p$
\item $|S_t| = {\binom {l+t-1} l} \geq 2^t$
($l>t$)
\item If $n$ is not a power of $p$, then $t > ord_r(n)$.
\item If $n$ is introspective for $X+a$ ($\forall a \in
\{1,...,l\}$) in $R$, every element of $T$ is introspective for
every element of $S$ in both $R$ and $K$. (From the Fact 4)
\end{enumerate}
The existences of $T$,$t$,$S$,$S_t$,$K$ are dependent on the
existence of $p$. So they will appear only in the proof of
correctness, not the algorithm itself.

\section{Algorithm}
Our algorithm for testing primality of $n$ like this.\\

TEST($n$) :
\begin{enumerate}
\item if $n = m^k$ for some integer $m$ and $k$, OUTPUT COMPOSITE.
\item if $\exists$ $r$ $\in \{1,...,[32\log ^6 n]\}$ such that $r\
|\ n$, OUTPUT COMPOSITE
\item Find a nice $r$ for $n$ in $\{1,...,[32\log ^6 n]\}$
\item (MAIN STEP) for $a=1$ to $l$,
$$if\ (X+a)^n \neq X^n +a\ (\rm{mod}\ n,X^r -1),\ OUTPUT\
COMPOSITE.$$
\item OUTPUT PRIME\\
\end{enumerate}
The step 1, step 2 and step 3 run obviously in $O(poly(n))$. The
step 4 also runs in $O(poly(n))$ because the size of $r$ and
$l(l<r)$ must be $O(poly(n))$ from step 3. So our algorithm runs in
$O(poly(n))$. The remaining work is to prove correctness of our
algorithm. The following theorem tells its correctness.\\

\begin{theorem}
Suppose $r$ is nice for $n$. If there is no factor of $n$ less than
$r$ and $n$ is introspective for $X+a$ ($\forall a \in \{1,...,l\}$)
in $R$($=\mathbb{Z} [X] / (n,X^r - 1)$), then $n$ is a power of a
prime $p$ greater than $r$.
\end{theorem}
Prove this theorem in the next section.

\section{Correctness}

To prove our theorem, suppose the following assumption for
contradiction.
\begin{assumption}
\end{assumption}
\begin{enumerate}
\item $r$ is nice for $n$
\item $n$ is introspective for $X+a$ ($\forall a \in \{1,...,l\}$) in
$R$
\item $n$ is not a power of $p$.
\end{enumerate}
Remember the facts proved in the previous lecture.

\begin{enumerate}
\item There exist two distinct numbers $m_1$ and $m_2$ in $T$ such that
$m_1 = m_2\ (\rm{mod}\ r)$ and $m_1 ,m_2\leq n^{2{\sqrt t}}$.
\item Let $P(Y) = Y^{m_1} - Y^{m_2}$ in $K[Y]$, then every element in
$S$ is a root of $P$ in $K$.
\end{enumerate}
From these facts, we can conclude the following.
\begin{fact}
There are at most $n^{2{\sqrt t}}$ elements of $S$ in $K$.
\end{fact}
With this fact and the following lemma, we can prove our main
theorem.

\begin{lemma}
Under the Assumption 7, two distinct elements $f$ and $g$ in $S_t$
are also distinct in $K$.

\end{lemma}
\begin{proof}
Suppose $f(X)=g(X)$ in $K$. Because $f$ and $g$ are distinct in
$\mathbb{Z}_p [X]$ ($p>l$), $f(X)=g(X)\ (\rm{mod}\ h(X))$. Let
$e(Y)$ be $f(Y)-g(Y)$ in $K$. Then the degree of $e$ is less than
$t$ and $X$ is a root of $e$. Because any $m$ in $T$ is
introspective for $f$ and $g$ in $K$(from the Observation 5-4),
$e(X^m )=f(X^m )-g(X^m )=f(X)^m-g(X)^m=0$ in $K$, so $X^m$ is a root
of $e$. Now show the following claim.\\\\
\textbf{Claim :} If $m_1 \neq m_2$ $(\rm{mod}\ r)$, then $X^{m_1}
\neq X^{m_2}\ (\rm{mod}\
h(X))$\\\\
If $h(X)$ divides $X^{m_1} - X^{m_2}$, $h(X)$ divides $X^{m_1 -
m_2}-1$(Suppose $m_1 > m_2$). Because $h(X)$ divides $X^r - 1$,
$h(X)$ divides $X^{gcd(m_1 - m_2 , r)} - 1$. If $m_1 \neq m_2\
(\rm{mod}\ r)$, $X^{gcd(m_1 - m_2 , r)} - 1 = X - 1$ and hence $h(X)
| X - 1$. This contradiction shows the claim.\\\\
Because there are $t$ distinct (in mod $r$) elements in $T$, the
number of roots of $e(Y)$ is at least $t$. This is contradiction
because the degree of $e$ is less than $t$.
\end{proof}\\
Prove our theorem which gives correctness of our algorithm.\\\\
\textbf{Proof of the main theorem }  Suppose the Assumption 7 is
true. Then the Lemma 9 and the Fact 8 tell $S_t \leq n^{2\sqrt t}$.
Because $2^t \leq S_t$(from the Observation 5-2), it is sufficient
to show $2^t
> n^{2\sqrt t}$ for contradiction.
$$t > ord_r(n)\ (n\ is\ not\ a\ power\ of\ p)$$
$$\rightarrow t > ord_r(n) > 4 \log^2 n\ (r\ is\ nice\ for\ n)$$
$$\rightarrow {\sqrt t} > 2 \log n$$
$$\rightarrow 2^t > n^{2\sqrt t}\ \qed\bigskip$$

\end{document}