\lecture{12: The AKS Primality Test}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}
\section{Overview}
We shall take a small detour before we go into factorising
polynomials. In this class we shall look at the AKS primality test, an
unconditional, deterministic polynomial time algorithm for primality
testing.
\section{Preliminaries}
Given a number
$n\in \N$, we wish to test whether the number
is prime or not. And since
$n$ is given in binary (hence input size is
$O(\log n)$), the running time is to be polynomial in
$\log n.$
The AKS algorithm uses the following proposition to distinguish
between primes and composites.
\begin{proposition}
If
$(a,n) = 1$, then
$(X+a)^n = X^n + a \pmod{n}$ if and only if
$n$
is prime.
\end{proposition}
\begin{proof}
If
$n$ is a prime, then we have already seen in the earlier class
that
$(X+a)^n = X^n + a^n = X^n + a \pmod{n}.$
Suppose
$n$ was composite and
$p$ was a prime divisor of
$n$. Let
the largest power of
$p$ that divides
$n$ be
$p^k$. The coefficient
of
$x^p$ in
$(X+a)^n$ is
$\binom{n}{p}a^{n-p}.$ $a$ anyway is
coprime to
$n$, and hence can be ignored. But it is easy to see that
$p^k$ does not evenly divide
$\binom{n}{p}$ (since a power of
$p$ is
knocked off from the
$n$) and hence that term would survive
$\bmod{n}.$
\end{proof}
There are however two problem with this, firstly being computing
$(X+a)^n$ efficiently, but that we saw last class (using repeated
squaring and the binary representation of
$n$). A more serious problem
is that
$n$ is exponential in the input size, and the polynomial would
be too large to compare and check if it is
$X^n + a.$
Getting around this difficulty was gave the AKS test.
\section{The Primality Test}
The idea to get around the difficulty of exponential degree is to
check it modulo polynomials of ``small'' degree, a ``small'' number of
times.
We shall give the algorithm first and then show that it is infact
correct and that it runs in time polynomial in
$\log n.$
\begin{algorithm}
\caption{AKS Primality Test:}
\begin{algorithmic}[1]
\REQUIRE $n$ in binary
\STATE Check if
$n$ is of the form
$a^b$ for
$b\geq 2$. If yes,
{\bf output} {\sc composite}
\STATE Find the least
$r$ such that the order of
$n$ modulo
$r$
(denoted by
$O_r(n)$)is at least
$4\log^2n$
\STATE If
$(a,r)\neq 1$ for
$1\leq a\leq r$,
{\bf output} {\sc composite}
\STATE If
$n<r$,
{\bf output} {\sc prime}
\FOR{$a=1$ to $\floor{2\sqrt{\phi(r)}\log n}$}
\IF{$(X+a)^n \neq X^n + a \pmod{n,X^r - 1}$}
\STATE {\bf output} {\sc composite}
\ENDIF
\ENDFOR
\STATE {\bf output} {\sc prime}
\end{algorithmic}
\end{algorithm}
Apart from step
$2$, it is clear that the algorithm will run in time
polyomial in the input length. As for step
$2$, the following lemma
would tell us that we can indeed find such an
$r$ quickly.
\begin{lemma}
If
$m$ is an odd number, then the lcm of
$1,2,\cdots,m$ is atleast
$2^{m-1}.$
\end{lemma}
\begin{proof}
Let
$m = 2n+1.$ Consider the following integral:
$$
\int_0^1 x^n(1-x)^n dx
$$
Since $x(1-x)<1/4
$, this integral is upper bounded by $2^
{2n}.
$ But
if we were to expand $(1-x)^n
$ using the binomial theorem, we have
\begin{eqnarray*}
2^{-2n}\leq\int_0^1 x^n(1-x)^n dx & = &\int_0^1 \sum_{k=0}^n
(-1)^k \binom{n}{k}x^{n+k}\\
&= &\sum_{k=0}^n (-1)^k\binom{n}{k}\frac{1}{n+k+1} = \frac{M}{N}
\end{eqnarray*}
Clearly, the denomiantor is atmost the lcm ($L
$) of the numbers
$1,2,
\cdots 2n+1
$ and $M
$ is atleast $1
$. Hence $L2^
{-2n} >
N2^
{-2n}\geq 1
$ and hence $L
\geq 2^
{2n}.
$
\end{proof}
\begin{lemma}
There exists an $r
\leq 16
\log^5n
$ such that $O_r(n)
\geq 4
\log^2n.
$
\end{lemma}
\begin{proof}
Suppose all $r
$'s till $T
$ were bad, that is, for all $1
\leq r
\leq
T
$ the order of $n
$ modulo $r
$ was less than $4
\log^2 n.
$ Then, for
every $r
$ there exists a $j < 4
\log^2n
$ such that $r
$ divided $n^j -
1.
$ Therefore, each $1
\leq r
\leq T
$ divides the product
$\prod_
{j=1}^
{4\log^2 n}(n^j - 1) < n^
{16\log^4n} = 2^
{16\log^5n}.
$ And
therefore, the lcm of the first $T
$ numbers divide the product. The
bound from the earlier lemma will now force $T < 16
\log^5n.
$
\end{proof}
It is now clear that the algorithm runs in time polynomail in $\log
n
$, each step is clearly a polylog operation. With some work, one can
see that this is roughly a $O(
\log^
{11}n)
$ algorithm.
\section{Proof Correctness}
One way is clear, if the number was a prime then the algorithm would
certainly output {\sc prime}. We need to show that if the algorithm
outputs {\sc prime}, then it is indeed prime.
Suppose not, let $p
$ be a prime divisor of $n.
$ And from our initial
tests, we know that $p>r.
$ And further for $a = 1,2,
\cdots l
$ where $l
=
\floor{2\sqrt{\phi(r)}\log n
},
$
$$
(X+a)^n = X^n + a \pmod{n,X^r - 1} = X^n + a \pmod{p,X^r - 1}
$$
Note that from Fermat's little theorem, we have
$$
(X+a)^p = X^p + a \pmod{p,X^r-1}
$$
We shall use a small notation here.
\begin{definition}
For any function $f
$, a number $m
$ is called introspective for $f
$
if $f(X)^m = f(X^m)
\pmod{p,X^r-1}.
$
\end{definition}
We then have the two simple lemmas.
\begin{lemma}
If $m
$ and $m'
$ are introspective for $f
$, so is $mm'.
$
\end{lemma}
\begin{proof}
\begin{eqnarray*}
f(X)^m & = &f(X^m) \pmod{p,X^r - 1}\\
\implies f(X^{m'})^m & =& f(X^{mm'})\pmod{p,X^{m'r -
1}}\quad(\text{substitute $X^{m'}$ for $X
$})\\
& = & f(X)^{mm'} \pmod{p,X^r - 1} \quad(\text{$X^r - 1$ divides
$X^{rm'}-1
$})\\
\implies f(X)^{mm'} & = & f(X^{mm'}) \pmod{p,X^r - 1}
\end{eqnarray*}
\end{proof}
\begin{lemma}
If $m
$ is introspective for $f
$ and $g
$, then $m
$ is introspective
for $fg.
$
\end{lemma}
\begin{proof}
Obvious!
\end{proof}
Let $I =
\setdef{n^ip^j}{i\geq 0, j\geq 0}$ and $P =
\setdef{\prod_{a=1}^
{l}(X+a)^
{e_a}}{e_a\geq 0}.
$ Then, from the two
lemmas, every element of $I
$ is introspective for every element in
$P
$.
Let $G
$ be the subgroup of $\Z_r^
\star$, of size $t
$, generated by $n
$
and $p
$. Since $O_r(n)
\geq 4
\log^2n
$, $|G|=t
\geq 4
\log^2 n.
$ To do a
similar thing for the polynomials, we first need to move from the ring
$(
\F_p/(X^r - 1))
$ to a field. Let $X^r - 1 = h_1(X)h_2(X)
\cdots
h_k(X)
$ be the factorization into irreducible factors. Since the
primitive $r
$-th root of unity generates all the roots of unity (since
we are going mod $X^r - 1
$), the primitive root of unity is a root of
some irreducible polynomial. Hence we shall look at $\F_r/(h(x))
$,
which is essentially $\F_r
[\eta]$ where $\eta$ is a primitive $r
$-th
root of unity.
Now in the field $\F_r/(h(x))
$, look at the multiplicative group. Let
$\mathcal{G}$ be the subgroup generated by $\inbrace{(X+a)}_
{1\leq
a\leq l}$, the set of polynomials in $P
$ that are non-zero in
$\F_p/(h(x)).
$
\begin{lemma}
$|
\mathcal{G}|
\geq \binom{t+l-2}{t-1}$
\end{lemma}
\begin{proof}
Since $l =
\floor{2\sqrt{\phi(r)}\log n
} < 2
\sqrt{r}\log n < r < p
$,
each of $\inbrace{(X+a)}_
{1\leq a\leq l}$ are distinct in
$\F_p/(h(x)).
$ At worst $h(x)
$ can be equal to one of them, hence
at least $l-1
$ of them are non-zero and distinct.
Let $f
$ and $g
$ be two polynomials from $P
$ of degree less than
$t
$. Suppose $f(x) = g(x)
$ in $\F_p/(h(x))
$, then we also have
$f^m(x) = g^m(x)
$ in the field. If we choose $m
\in G
$, then since
$m
$ is introspective for $f
$ and $g
$, we have $f(X^m) = g(X^m)
$ in
the field.
Since we can identify $X
$ with a primitive $r
$-th root of unity,
each of the $X^m
$ are distinct. And infact, each of them is a root
of the polynomial $H(Y) = f(Y) - g(Y).
$ The size of the group $G
$ is
$t
$ but the degree of $f
$ and $g
$ is less than $t
$, which gives an
absurd situation of the polynomial $f-g
$ having more roots than its
degree in the field.
Hence, if two polynomials of degree less than $t
$ are chosen from
$P
$, they are mapped to different elements in $\F_p/(h(x)).
$
$$
|\mathcal{G}| \geq \left|\setdef{\prod_{1\leq a\leq
l}(X+a)^{e_a}}{\sum e_a \leq t}\right|
$$
As we remarked earlier, there can be at most one $X+a_0
$ that
becomes zero in the field. So essentially, we just need to find the
different integer solutions to $\sum e_a
\leq t
$, summing over all
$a
\neq a_0
$, and this is equal to $\binom{t+l-2}{t-1}.
$ Hence
$|
\mathcal{G}|
\geq \binom{t+l-2}{t-1}.
$
\end{proof}
\begin{lemma}
If $n
$ is not a power of a prime, $|
\mathcal{G}| < n^
{2\sqrt{t}}$
\end{lemma}
\begin{proof}
Consider the subset $I' =
\setdef{n^ip^j}{0\leq i,j\leq \sqrt{t}}.
$
Hence each element in $I'
$ is bounded by $n^
{\sqrt{t}}p^
{\sqrt{t}} <
n^
{2\sqrt{t}}$. And further, if $n
$ is not a power of a prime, $|I'|
= (1+
\sqrt{t})^2 > t.
$ Since $|G| = t
$, there exists two distinct
$m,m'
$ of $I'
$ such that $m = m'
\pmod{r}$, and hence $X^m = X^
{m'}
\pmod{r,X^r-1}.
$ Also, for any $f
\in \mathcal{G}$, $f(X)^m =
f(X)^
{m'}$. Therefore, if you consider the polynomial $Y^m -
Y^
{m'}$, every element of $\mathcal{G}$ is a root. And since the
degree is bounded by $n^
{2\sqrt{t}}$, this forces $|
\mathcal{G}| <
n^
{2\sqrt{t}}.
$
\end{proof}
With the choice of $l
$, it is easy to see that the above two lemmas
give conflicting bounds (lower bound greater than upper bound), which
gives us the desired contradiction to the assumption that $n$ is
composite.
Hence, summarizing it in a theorem:
\begin{theorem}
The algorithm returns
{\sc prime} if and only if the input is a
prime.
\qed
\end{theorem}
\section{A short note on identity testing}
{\em I haven't taken notes here... would be nice if someone could fill
this part.}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "lecture12"
%%% End: