
%Begining of Claudes Finite Field section



\pagebreak
\section{Finite Fields}
%=====================%

\subsection{Polynomials over a field}
%-----------------------------------%
A polynomial over $\GF{p}$ is specified by a finite sequence $(a_n,a_{n-1},...,a_1,a_0)$
of elements from $\GF{p}$, with $a_n\neq 0$. The number $n$ is the 
degree of the polynomial.
We have operations $+, -, \times$ on polynomials analogous to the 
similar integer operations.
Addition and subtraction are performed componentwise using the
addition $+$ and subtraction $-$ of the field $\GF{p}$.

Products are computed by adding all the products of coefficients
associated to pairs of exponents adding to a specific exponent.
Example:
\begin{eqnarray*}
(x^4+x+1)\times(x^3+x^2+x) & = & x^4\times(x^3+x^2+x)+x\times(x^3+x^2+x)+1\times(x^3+x^2+x) \\
& = & (x^7+x^6+x^5)+(x^4+x^3+x^2+)+(x^3+x^2+x) \\
& = & x^7+x^6+x^5+x^4+(1+1)x^3+(1+1)x^2+x \\
& = & x^7+x^6+x^5+x^4+x
\end{eqnarray*}
Similarly we have  operations $g(x) \bmod h(x)$ and $g(x) \mbox{ div } h(x)$
defined as the polynomials $r(x)$ and $q(x)$ such that $g(x)=q(x)h(x)+r(x)$
with $deg(r)<deg(h)$. They are obtained by formal division of $g(x)$
by $h(x)$ similar to what we do with integers.
Example:
\begin{eqnarray*}
x^7+x^6+x^5+x^4+x
& = & (x^2)\times(x^5+x^2+1) + (x^6+x^5+x^2+x) \\
& = & (x^2+x)\times(x^5+x^2+1) + (x^5+x^3+x^2) \\
& = & (x^2+x+1)\times(x^5+x^2+1) + (x^3+1)
\end{eqnarray*}
thus
\begin{eqnarray*}
(x^7+x^6+x^5+x^4+x) \bmod (x^5+x^2+1) = x^3+1\\
(x^7+x^6+x^5+x^4+x) \mbox{ div } (x^5+x^2+1) = x^2+x+1
\end{eqnarray*}

Exponentiations for integer powers modulo a polynomial are computed
using an analogue of algorithm \ref{expmod} and $gcd$ of polynomials or
multiplicative inverses are computed using an analogue of algorithm \ref{euclide}.

\subsection{Irreducible Polynomials}
%----------------------------------%
A polynomial $g(x)$ is {\em irreducible} if it is not
the product of two polynomials $h(x),k(x)$ of lower degrees.
We use the following theorem to find irreducible polynomials.

\begin{theorem}
Let $l_1,l_2,...,l_k$ be the prime factors of $n$ and $m_i = n/l_i$ 
for $1 \leq i \leq k$.
A polynomial $g(x)$ of degree $n$ is {\em irreducible} over $\GF{p}$ 
if and only if
\begin{itemize}
\item[$\bullet$] $g(x) | x^{p^n}-x$
\item[$\bullet$] $gcd(g(x), x^{p^{m_i}}-x)=1$ for $1 \leq i \leq k$
\end{itemize}
\end{theorem}

\algo{Rabin $Irr(p,n)$}{
\label{rabin}
\step{let $l_1,l_2,...,l_k$ be the prime factors of $n$ and $m_i = 
n/l_i$ for $1 \leq i \leq k$,}
\step{{\bf REPEAT}}
\step{pick a random polynomial $h(x)$ of degree $n-1$ over $\GF{p}$,
$g(x)\is x^n + h(x)$,}
\step{{\bf UNTIL} $x^{p^n} \bmod g(x) = x$ and
$gcd(g(x), x^{p^{m_i}}-x)=1$ for $1 \leq i \leq k$,}
\step{{\bf RETURN} $g$.}
}

We use the following theorem to estimate the number of polynomials
we have to try on average before finding one that is irreducible.

\begin{theorem}
Let $m(n)$ be the number of irreducible polynomials $g(x)$ of degree $n$ 
of the form
$g(x) = x^n+h(x)$ where $h(x)$ is a polynomial of degree $n-1$.
We have
$$\frac{p^n}{2n} \leq \frac{p^n-p^{n/2} \log n}{n} \leq m(n) \leq \frac{p^n}{n}.$$
\end{theorem}

\begin{figure}[h]
$$
\begin{array}{|r|r||r||r||r|}
\multicolumn{2}{|c||}{\GF{2}} & \GF{3} & \GF{5} & \GF{7}\\
\hline
x+1 & x^9+x^4+1 & x+1 & x+1 & x+1 \\
x^2+x+1 & x^{10}+x^3+1 & x^2+x+2 & x^2+x+2 & x^2+x+3 \\
x^3+x+1 & x^{11}+x^2+1 & x^3+2x+1 & x^3+3x+2 & x^3+3x+2 \\
x^4+x+1 & x^{12}+x^6+x^4+x+1 & x^4+x+2 & x^4+x^2+x+2\\
x^5+x^2+1 & x^{13}+x^4+x^3+x+1 & x^5+2x+1\\
x^6+x+1 & x^{14}+x^{10}+x^6+x+1 & x^6+x+2 \\
x^7+x^3+1 & x^{15}+x+1\\
x^8+x^4+x^3+x^2+1 & x^{16}+x^{12}+x^3+x+1
\end{array}
$$
\caption{Irreducible (primitive) polynomials over $\GF{2}$ and irreducible 
polynomials over $\GF{3}$,$\GF{5}$,$\GF{7}$.}
\end{figure}

\subsection{General Fields}
%-------------------------%
Let $p$ be a prime number and $n$ a positive integer.
We construct a field with $p^n$ elements from the basis field 
$\GF{p}$ with $p$ elements.

\begin{itemize}
\item[$\bullet$]
The elements of $\GF{p^n}$ are of the form $a_1 a_2 ... a_n$ where $a_i$ 
is an element of $\GF{p}$.

\item[$\bullet$]
The sum of two elements of $\GF{p^n}$ is defined by
$$a_1 a_2 ... a_n + b_1 b_2 ... b_n =
c_1 c_2 ... c_n$$
such that $c_i = a_i + b_i$ for $1\leq i\leq n$.

\item[$\bullet$]
The product of two elements of $\GF{p^n}$ is defined by
$$a_1 a_2 ... a_n \times b_1 b_2 ... b_n =
c_1 c_2 ... c_n$$
such that
$$(c_1 x^{n-1}+c_2 x^{n-2}+...+c_n) =
(a_1 x^{n-1}+a_2 x^{n-2}+...+a_n) \times
(b_1 x^{n-1}+b_2 x^{n-2}+...+b_n) \bmod r(x)$$
where $r(x)$ is an irreducible polynomial of degree $n$ over $\GF{p}$.
\end{itemize}

\paragraph{Examples} computations over $\GF{2^5}$\\
%''''''''''''''''''%
$10011 + 01110 = (1+0)(0+1)(0+1)(1+1)(1+0) = 11101$\\\\
$10011 \times 01110 = 01001$ car
$(x^4+x+1)\times(x^3+x^2+x) \bmod (x^5+x^2+1) = x^3+1$.

\begin{figure}[h]
\begin{center}
\begin{tabular}{|r||c|c|c|c|c|c|c|c|}
\hline
~$+$~ & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111\\
\hline\hline
000 & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111\\
\hline
001 & 001 & 000 & 011 & 010 & 101 & 100 & 111 & 110\\
\hline
010 & 010 & 011 & 000 & 001 & 110 & 111 & 100 & 101\\
\hline
011 & 011 & 010 & 001 & 000 & 111 & 110 & 101 & 100\\
\hline
100 & 100 & 101 & 110 & 111 & 000 & 001 & 010 & 011\\
\hline
101 & 101 & 100 & 111 & 110 & 001 & 000 & 011 & 010\\
\hline
110 & 110 & 111 & 100 & 101 & 010 & 011 & 000 & 001\\
\hline
111 & 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000\\
\hline
\end{tabular}~~~~~~
\begin{tabular}{|r||c|c|c|c|c|c|c|c|}
\hline
~$\times$~ & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111\\
\hline\hline
000 & 000 & 000 & 000 & 000 & 000 & 000 & 000 & 000\\
\hline
001 & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111\\
\hline
010 & 000 & 010 & 100 & 110 & 011 & 001 & 111 & 101\\
\hline
011 & 000 & 011 & 110 & 101 & 111 & 100 & 001 & 010\\
\hline
100 & 000 & 100 & 011 & 111 & 110 & 010 & 101 & 001\\
\hline
101 & 000 & 101 & 001 & 100 & 010 & 111 & 011 & 110\\
\hline
110 & 000 & 110 & 111 & 001 & 101 & 011 & 010 & 100\\
\hline
111 & 000 & 111 & 101 & 010 & 001 & 110 & 100 & 011\\
\hline
\end{tabular}
\end{center}
\caption{operations of $\GF{2^3}$}
\end{figure}

\comment{
\begin{figure}
\begin{center}
\begin{tabular}{|r||c|c|c|c|c|c|c|c|}
\hline
$+$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline\hline
0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline
1 & 1 & 0 & 3 & 2 & 5 & 4 & 7 & 6\\
\hline
2 & 2 & 3 & 0 & 1 & 6 & 7 & 4 & 5\\
\hline
3 & 3 & 2 & 1 & 0 & 7 & 6 & 5 & 4\\
\hline
4 & 4 & 5 & 6 & 7 & 0 & 1 & 2 & 3\\
\hline
5 & 5 & 4 & 7 & 6 & 1 & 0 & 3 & 2\\
\hline
6 & 6 & 7 & 4 & 5 & 2 & 3 & 0 & 1\\
\hline
7 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0\\
\hline
\end{tabular}~~~~~~
\begin{tabular}{|r||c|c|c|c|c|c|c|c|}
\hline
$\times$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
\hline
1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline
2 & 0 & 2 & 4 & 6 & 3 & 1 & 7 & 5\\
\hline
3 & 0 & 3 & 6 & 5 & 7 & 4 & 1 & 2\\
\hline
4 & 0 & 4 & 3 & 7 & 6 & 2 & 5 & 1\\
\hline
5 & 0 & 5 & 1 & 4 & 2 & 7 & 3 & 6\\
\hline
6 & 0 & 6 & 7 & 1 & 5 & 3 & 2 & 4\\
\hline
7 & 0 & 7 & 5 & 2 & 1 & 6 & 4 & 3\\
\hline
\end{tabular}
\end{center}
\caption{op\'erations de $\GF{8}$}
\end{figure}
}
