%% ================================================================
\newpage
\chapter{Proofs}

In contrast with most mathematical writing, this paper does not follow a
traditional theorem-proof-theorem-proof pattern.  Since the focus of this paper
is on how to compute, proofs (non-constructive proofs in particular) would
detract from the main thread; also, I have attempted to make this paper at
least somewhat palatable to an applied audience, for whom proofs are likely a
distraction at best.  (Nonetheless, several theorems \emph{are} proved in the
main body of this paper but simply are not labelled as such.)

On the other hand, the more mathematically inclined reader may rightly find
fault with the number of unsubstantiated results claimed herein.  As well, some
of the proofs are enlightening and contribute toward practical understanding of
the material.

I will take as given the standard results of group theory, field theory and
linear algebra; proving only those items pertaining specifically to finite
fields.  None of these are specifically attributed, as they are standard
results which are found (modulo vagaries of phrasing) in e.g.  Dummit and
Foote's \emph{Abstract Algebra}, Lidl and Niederreiter's \emph{Finite Fields},
Serre's \emph{A Course in Arithmetic}, Berlekamp's \emph{Algebraic Coding
Theory}, Koblitz's \emph{A Course in Number Theory and Cryptography}, etc.

%% ----------------------------------------------------------------
\section{Characteristic and order of finite fields}

\begin{defn}
Let $R$ be a finite ring with identity $1_R$.  Write $1$ for $1_R$.  Let $n \in
\Z$.  Then $n \cdot 1_R$ denotes $1_R + \ldots + 1_R$, $n$ times.
\end{defn}

\begin{thm}
Let $R$ be a finite ring with 1.  There is a positive integer $c$, called the
\bfidx{characteristic} of $R$, such that for all $r \in R$, $cr = 0$, and for
all positive integers less than $c$ and for all non-zero $r \in R$, $cr \ne 0$.
\begin{proof}
\ldots
\end{proof}
\end{thm}

% r = 1r
% cr = c1r

\begin{thm}
Let $F$ be a finite field.  The characteristic of $F$ is a prime integer.
\begin{proof}
\ldots
\end{proof}
\end{thm}

xxx def prime subfield.

\begin{thm}
Let $F$ be a finite field.  The order of $F$, written $\#F$, is $p^n$ for some
prime integer $p$ and some positive integer $n$.
\begin{proof}
\ldots
\end{proof}
\end{thm}

%% ----------------------------------------------------------------
\section{Existence of finite fields}

\begin{thm}
Let $p$ be a prime integer, and let $n$ be a positive integer.
There exists a finite field of order $p^n$.
\begin{proof}
\ldots
\end{proof}
\end{thm}

%% ----------------------------------------------------------------
\section{Uniqueness of finite fields}

\begin{thm}
Let $p$ be a prime integer, and let $n$ be a positive integer.  Let $K$ and $L$
be two fields of order $p^n$.  There exists an isomorphism of fields between
$K$ and $L$.
\begin{proof}
\ldots
\end{proof}
\end{thm}

%% ----------------------------------------------------------------
\section{Cyclicity of finite subgroup of a field}

\begin{thm}
\label{thm:fin_sgr_fld_cyc}
Let $K$ be any field.  Let $H$ be a finite subgroup of the multiplicative group
of $K$.  Then $H$ is a cyclic group.
\begin{proof}
Let $e$ be the exponent of the subgroup, i.e. the smallest integer such that
$x^e$ for all $x \in H$.  Let $d$ be the order of the subgroup.  Suppose that
$e<d$.  Then $x^e-1$ has $d$ roots, with $e<d$.  This is absurd, since over a
field, each polynomial of degree $e$ has at most $d$ roots.  Therefore $e \ge
d$.  By Lagrange's theorem $e \le d$.  Therefore $e = d$ and thus $H$ is
cyclic.
\end{proof}
\end{thm}

%% ----------------------------------------------------------------
\section{Existence of reciprocals in $\F_p$}

\begin{thm}
$\F_p$ is a field.
\begin{proof}
I take as given that $\Z/m\Z$ is a commutative ring with identity for
arbitrary integer $m$.  It remains only to show that $\Fp = \Z/p\Z$ contains
multiplicative inverses for all non-zero elements, which was shown in
section \ref{sec:fp_invs}.
\end{proof}
\end{thm}

%%% ----------------------------------------------------------------
%\section{$\Fpn$ is a vector space over $\Fp$}
%
%In section \ref{sec:existence_of_Fpn} I proved that if there exists a finite
%field $F$, with characteristic $p$, then $F$ is necessarily a
%finite-dimensional vector space over $\Fp$.  Letting $n$ be that dimension, we
%denote $F$ by $\Fpn$.  Thus, all finite fields must have prime-power order.
%
%%% ----------------------------------------------------------------
%\section{Existence of $\Fpn$}
%
%Here we show that there does in fact exist a finite field of order $p^n$ for
%each prime $p$ and each $n \ge 1$.
%
%\ldots
%
%%% ----------------------------------------------------------------
%\section{Uniqueness of $\Fpn$}
%
%\ldots

%% ----------------------------------------------------------------
\section{Cyclicity of $\F_p^\times$}

This follows immediately from theorem
\ref{thm:fin_sgr_fld_cyc}:  take $H = \F_q^\times$.

%\begin{thm}
%Any finite multiplicative subgroup of a field $F$ is cyclic.
%\begin{rem*}
%This applies to finite subgroups of infinite fields, e.g. $\{\pm1\}$ in
%$\R$, and the $m$th roots of unity in $\C$.
%\end{rem*}
%
%\begin{proof}
%The proof takes three parts.  First, a number-theoretical result.
%
%\begin{lem*}[2a]
%$m = \sum_{d|m} \phi(d)$
%\begin{proof}
%
%From group theory we know that in the additive cyclic group $(\Z/m\Z, \oplus)$,
%each of the $m$ residue classes $0$ through $m-1$ generates a cyclic subgroup
%of $\Z/m\Z$.  On the other hand, we know the subgroups of the cyclic group of
%order $m$:  there is precisely one subgroup, which is cyclic, for each $d|m$,
%each having $\phi(d)$ generators.  Thus each of the $m$ elements of $\Z/m\Z$ is
%accounted for by one generator, proving the claim.
%
%For example, $m=15$ has divisors $d=1,3,5,15$.  In $\Z/15\Z$:
%\begin{itemize}
%\item 0 generates $\{0\}$
%\item 5 and 10 generate $\{0,5,10\}$, and $\phi(3)=2$.
%\item 3, 6, 9 and 12 generate $\{0,3,6,9,12\}$, and $\phi(5)=4$.
%\item 1, 2, 4, 7, 8, 11, 13, and 14 generate all of $\Z/15\Z$, and
%	$\phi(15)=8$.
%\item $15 = 1 + 2 + 4 + 8$.
%\end{itemize}
%
%\end{proof}
%\end{lem*}
%
%Second, a group-theoretic result.
%\begin{lem*}[2b]
%Let $G$ be a group of order $m$ such that for all $d|m$, there are at most
%$d$ elements satisfying $x^d=e$.  Then $G$ is cyclic.
%\begin{proof}
%
%Since $G$ has order $m$, by Lagrange's theorem any element of $G$ has order $d$
%for some $d|m$.  To count how \emph{many} such elements there are, first
%suppose there either is or is not an order-$d$ element $a$ for a given $d$.  If
%there is, then $a$ generates a cyclic order-$d$ subgroup of $G$, all the
%elements of which satisfy $x^d=e$.  Since this is a cyclic subgroup, there are
%$\phi(d)$ generators.  Since we have $d$ elements satisfying $x^d=e$ and since
%we assume there are at most $d$ such elements, there are no other order-$d$
%elements in $G$.  Thus, there are either $0$ or $\phi(d)$ elements of order $d$
%in $G$.
%
%Now, $G$ consists of all the order-$d$ elements (call this number $N_d$) for
%all $d|m$.  This means that $m = \sum_{d|m} N_d$.  We just saw that $N_d \le
%\phi(d)$, and from the previous lemma, $m = \sum_{d|m} \phi(d)$.  Thus $G$
%must have elements of all orders $d|m$, else there are not enough elements
%to fill the group (which would be a contradiction).  In particular, since
%$m|m$, there is an order-$m$ element of $G$ which suffices to show that $G$
%is cyclic.
%
%For example, $m=15$ has divisors $d=1,3,5,15$.  In $G=\Z/15\Z$, there is
%$N_1=1$ element of order 1 (0), $N_3=2$ elements of order 2 (5, 10), $N_5=4$
%elements of order 5 (3, 6, 9, 12), and $N_{15}=8$ elements of order 15 (1, 2,
%4, 7, 8, 11, 13, 14).  We have $15 = 1 + 2 + 4 + 8$.
%
%\end{proof}
%\end{lem*}
%
%Third, the field-theoretic conclusion:  Let $F$ be a field and let $G$
%be a finite multiplicative subgroup of $F^\times$.  Since $F$ is a field,
%$x^d-1=0$ has at most $d$ roots.  Therefore $G$ is cyclic by the previous
%lemma.
%
%Note that in particular this applies to $G=\F_p^\times$, with $m=p-1$.
%(As well, it will apply to $G=\F_{p^n}^\times$, with $m=p^n-1$).
%\end{proof}
%\end{thm}

%% ----------------------------------------------------------------
\section{Galois group of finite fields}

\begin{thm}
Let $F$ be a finite field of characteristic $p$.  Let $\sigma_p:F \to F$ be
given by $\sigma_p(a) = a^p$, for $a \in F$.  Then $\sigma_p$ is an
automorphism of $F$, called the \bfidx{Frobenius automorphism} of $F$.
\begin{proof}
\ldots
\end{proof}
\end{thm}

xxx show that $F$ is a Galois extension of $\F_p$.

\begin{thm}
Let $F$ be a finite field of characteristic $p$.  Let $\sigma_p:F \to F$ be the
Frobenius automorphism.  Then the Galois group of $F$ over $\F_p$ is cyclic of
order $n$, generated by $\sigma_p$.
\begin{proof}
\ldots
\end{proof}
\end{thm}

%% ----------------------------------------------------------------
\section{Correctness of Berlekamp's algorithm}

Please see http://johnkerl.org/doc/iw2009/berlekamp.pdf

%\begin{itemize}
%\item xxx magic of frizn of $x^{p^n} - x$ over $\Fp$
%\item xxx roots thereof over $\Fpn$
%\item xxx gal what?
%\item sfld degs $d|n$
%\item sfld/log crit'n
%\item frob aut
%\item min poly $|$ char poly
%\item fld isoms
%\item Existence of reciprocals in $\F_p$
%\item Cyclicity of $\F_p^\times$
%\item xxx irred count
%\item xxx prim count
%\item xxx var-e's count
%\item how $x^{p^n}-x$ factors over $\Fpd$
%\end{itemize}
