\input{preamble}
\begin{document}
\lecture{Finding Irreducible Polyomials}{Polynomial Factoring}{Srikanth Srinivasan}{Ramprasad Saptharishi}

\section{Introduction}

One of the most common tricks used in any application of finite fields
is going to higher extensions. It is often necessary to work with
extension fields, to perhaps obtain certain roots, or maybe to create
larger fields with small characteristic. One natural way is to find an
irreducible polynomial of that degree, and go modulo this polynomial
to create extensions. Besides it numerous applications all over the
place, it gives a closure and is certainly something worth studying. 

The ``prime number theorem'' for finite fields tell us that a random
degree $n$ polynomial over $\F_p$ is irreducible with high
probability. In this talk we shall look at it deterministically. \\

\noindent
{\bf Problem: }Given $F = \F_p$ for a prime $p$, a positive integer $n$,
compute $q[x]\in F$, an irreducible polynomial of degree $n$.\\

As for the running time, what we would ideally want is $\poly(n,\log
p)$ but currently we do not have algorithms that do so well. However,
Shoup's algorithm works well for fields with small characteristic. In
this talk, we shall look at his $\poly(n,p)$ algorithm for finding
irreducible polynomials deterministically. 

\subsection*{The Algorithm Map}

We shall assume that $n$ and $p$ are odd. However, these assumptions
can be removed by some tricks, but we shall not see them here. Let $n
= l_1^{e_1}l_2^{e_2}\cdots l_s^{e_s}$, the prime factorization. This
can be computed in $\poly(n)$. 

The algorithm will involve two major steps.
\begin{enumerate}
\item Compute irreducible polynomials over $F$ of degree $l_i^{e_i}$
  for each $i$. 
\item After computing irreducible polynomials of degree $l_i^{e_i}$,
  combine them to get a degree $n$ irreducible polynomial. 
\end{enumerate}

We shall see the first step is essentially the hard step. 

\section{Finding irreducible polynomials of degree $l_i^{e_i}$}

Firstly, is there an easy case? The following fact gives a possibility
of finding a polynomial immediately. We won't be proving this
proposition here though. 

\begin{proposition}
  If $a$ is an $l-$non-residue in $F$, that is there is no element $b
  \in F$ such that $b^l = a$, then the polynomial $x^{l^e} - a$ is
  irreducible for any $e\geq 0$. 
\end{proposition}

Therefore, if we have such non-residues in the field, and if someone
can give us such a non-residue, we have an irreducible polynomial of
the required degree. But will we always have non-residues? Certainly,
if $l = p$, then there is no hope since every element of the field is
a $p$-residue. 

In fact, we can say more. Let us look at the following map:
\begin{eqnarray*}
\pi:\F_p& \longrightarrow & \F_p\\
a& \mapsto & a^l
\end{eqnarray*}
This can also be thought of as a homomorphism between $\F_p$ and
itself. Suppose there was a quadratic non-residue, then this map
cannot be one-one. Therefore, the kernel has to be non-trivial which
means that there is an element of order a factor of $l$. Therefore, if
we can ensure that $l\mid \abs{\F_p} - 1$, then we certainly do have
non-residues in the field. 

How do we go to a larger field $K$ such that $l\mid \abs{K} - 1$? Take
$K$ to be the splitting field of $x^l - 1$! Of course, if $l = p$,
this will just be $(x - 1)^p$ which is not interesting. We shall deal
with the the case when $l = p$ later. Therefore, in this section we
shall assume that $l\neq p$. 

\subsection*{Case 1: $l\neq p$}

The general philosophy would be this. We want an irreducible
polynomial in $F$, but we don't have non-residues. So we go to an
extension $K$ of $F$ that has non-residues. We then construct an
irreducible polynomial over $K$ of degree $l^e$. But we finally need a
degree $l^e$ polynomial over $F$, therefore we scale it down, so to
speak. \\

Let $K$ be the splitting field of $(x^l - 1)$ over $F$. By what we
discussed, this would introduce $l-$-non-residues, say some
element $a$. And it is easy to see that $|K| = p^m$ where $m$ is the
smallest positive integer such that $p^m = 1 \bmod{l}$. 

Now suppose, someone magically gave us the splitting field $K$, and a
$l-$non-residue $a\in K$. Then, we can just take the polynomial
$x^{l^e} - a$ and look at $E = K/(x^{l^e} - a)$. If $\beta$ was a root
of $x^{l^e} - a$, then $E = K(\beta)$. Thus the picture we have is
this:
$$
\begin{CD}
K       @>l^e>> E = K(\beta)\\
@AmAA           @AmAA\\
F = \F_p@>l^e>> H
\end{CD}
$$
For simplicity, let us call $q = l^e$. The extension $H$ we are
looking for, of degree $q$ over $F$, is of the form $F(\gamma)$ for
some $\gamma\in E$. Therefore, we want to find an element $\gamma \in
E$ of order $q$. But suppose we could find such an element, can we
construct its irreducible polynomial over $F$ easily? This is a nice
trick that will be used a few more times in this talk. Here are two
possible methods:
\begin{itemize}
\item Look at $1,\gamma,\gamma^2,\cdots,\gamma^q$. These are linearly
dependant since $\gamma$ is of degree $q$. Therefore, just doing a
gaussian elimination would give us a polynomial such that $\gamma$ is
a root. And this certainly has to be irreducible since the degree of
$\gamma$ is $q$. 
\item Look at $(x - \gamma)(x - \gamma^{p^l})\cdots (x
- \gamma^{p^{l(q-1)}})$. This is a polynomial in $F[x]$ since the
  polynomial is preserved under the Frobenius automorphism.
\end{itemize}

Therefore, it suffices to find an element $\gamma \in K(\beta)$ of
degree $q$ over $F$. Therefore, in some sense, we need to start with
$\beta$ which has degree $q\cdot m$ over $F$, and come down by a
factor of $m$ to get to $\gamma$. This ``coming down'' is exactly what
is achieved by the \emph{trace function}. 
$$
\Tr{\beta} = \sum_{i=0}^{m-1}\beta^{q^i} = \beta + \beta^{q} + \beta^{q^2} + \cdots + \beta^{q^{m-1}}
$$
\begin{claim}
$\gamma = \Tr{\beta}$ has degree $q$ over $F$. 
\end{claim}
\begin{proof}
Firstly, note that $(\Tr{\beta})^q = \Tr{\beta}$ and therefore,
$\Tr{\beta}\in H$. All we need to now show is that the degree doesn't
fall short. 

Assume that the degree of $\gamma$ over $F$ is $l^t$ for some $t <
e$. And clearly, if $\deg_F(\gamma) = l^t$, then surely
$\deg_K(\gamma) \leq l^t$. Now look at $E' =
K(\beta^l) \ni \gamma$. Thus, we now have the following picture:\\
$$
\begin{CD}
K          @>>>    E' = K(\beta^l) @>l>>     E = K(\beta)\\
@AmAA             @.                      @AmAA\\
F = \F_p   @>l^t>> F(\gamma)       @>>>     H
\end{CD}
$$

Now note that $\deg_{E'}(\beta) = l$. We shall, by expressing $\gamma$
differently, show that $\deg_{E'}(\beta) < l$, thus giving us a
contradiction. Recall that $\gamma = \beta + \beta^q + \beta^{q^2} + \cdots
+ \beta^{q^{m-1}}$. Now write each $q^i = x_il + y_i$ where $y_i<
l$. Therefore, 
\begin{eqnarray*}
\gamma & = &\sum_{i=0}^{m-1}\beta^{x_il + y_i}\\
       & = & \sum_{i=0}^{m-1}(\beta^l)^{x_i}\beta^{y_i}\\
       & = & \sum_{i=0}^{m-1}c_i\beta^{y_i}\quad,\quad c_i\in E'\\
\implies \deg_{E'}(\gamma) & \leq & l
\end{eqnarray*}
That gives us the contradiction we were after. There is one subtely
which is to show that not all the $y_i$s are $0$, which is where
$l\neq p$ comes in.
\end{proof}

\subsection{Getting rid of advice}

We used two pieces of advice that were magically given to us, the
splitting field of $(x^l - 1)$ over $F$ and a $l$-th non-residue. This
is where we would use factorization. Otherwise, the entire algorithm
just takes time $\poly(n,\log p)$. To compute the splitting field and
the non-residue, we shall factorize appropriate polynomials. 

The splitting field is easy; just factorize $(x^l - 1)$, keep adding
roots one by one until you've added all of them. 

Finding a non-residue isn't hard either. We know that a non-residue
exists. Therefore, just start with your favourite field element $a$,
and look at $x^l - a$. If it is irreducible, we are done. Else, look
at some linear factor of it; essentially take $l$-th root of $a$ and
continue the process. We will soon hit a non-residue. 

\subsection*{Case 2: $l = p$}

In this case, the following lemma in some sense does it all.

\begin{lemma}
Given any field $F$ with characteristic $p$. Then the polynomial $x^p
- x - a$ for $a\in F$ either completely split or is irreducible. 

Further, if $x^p - x - a$ is irreducible over $F$, and $\alpha$ is a
root in an extension field $E = F(\alpha)$, then $x^p - x -
a\alpha^{p-1}$ is irreducible over $E$.
\end{lemma}

Before we go on to prove this lemma, how would this help? We can just
start with $\F_p$, take $a = 1$, and apply the lemma. We know the
polynomial $x^p - x - 1$ is irreducible over $\F_p$. Take the
extension field $E = \F_p[\alpha]$, and now go one more step there,
and so on to finally give us a $p^e$ degree extension. 

\begin{proof}
The first part is left as an exercise; not too difficult to prove. As
for part $2$, assume not. Then, the polynomial has a root $\beta \in E
= F(\alpha)$. 
\begin{eqnarray*}
\beta & = & \sum_{i=0}^{p-1}b_i\alpha^i \\
\implies \beta^p - \beta - a\alpha^{p-1} & = & \inparen{\sum
b_i\alpha^i}^p - \inparen{\sum b_i\alpha^i} - a\alpha^{p-1} = 0\\
 & = & \sum \beta^p\alpha^{ip} - \sum b_i\alpha^i - a\alpha^{p-1}\\
 \alpha^p - \alpha - a & = & 0 \implies \alpha^p = \alpha + a\\
\implies \beta^p - \beta - a\alpha^{p-1} & = & \sum_{i=0}^{p-1} b_i^p(\alpha +
 a)^i  - \sum_{i=0}^{p-1} b_i\alpha^i - a\alpha^{p-1}
\end{eqnarray*}

The above polynomial is of degree less than $p$. And it can be easily
checked since the coefficient of $\alpha^{p-1}$ is non-zero; and that
gives us the contradiction. 
\end{proof}

\section{Composing the Irreducible Polynomials}

At this point, we have irreducible polynomials of degree $l_i^{e_i}$
for each $i$. Using them, we need to find a degree $n$ irreducible
polynomial. Or, even if we could find an element of degree $n$ that
would be sufficient by the trick we discussed earlier. The following
claim shows how that can be done.

\begin{claim}
If $\alpha,\beta$ are elements such that their degrees over $\F$ are
relatively prime, then $\F(\alpha + \beta) = \F(\alpha,\beta)$. 
\end{claim}
\begin{proof}
Assume not. Then, let $F'$ be the maximal subfield of
$\F(\alpha,\beta)$ that contains $(\alpha + \beta)$. Now, we leave it
as an exercise to show that either $\alpha \in F'$ or $\beta\in F'$,
which would complete the proof. 
\end{proof}

\end{document}