%% ================================================================
\newpage
\chapter{Introduction}

%% ----------------------------------------------------------------
\section{Purpose}

Finite fields are often given a brief treatment in algebra courses, and when
they are discussed, they are discussed in the abstract.  This is in fact a
testament to the power of theory:  Many properties may be deduced about finite
fields using no other information than that they are fields and that they are
finite.  However, specific computations are interesting as well as useful.
This paper will present elementary techniques that are readily implementable
with pencil and paper, software or electronic circuitry.

%% ----------------------------------------------------------------
\section{Context}

Why do we care about finite fields in the first place?  Among their
applications are the following:

\begin{itemize}

\item They are beautiful and interesting in their own right, which is
sufficient justification for a pure mathematician to care about them.

\item They have applications in number theory, i.e. pure math as applied to
other parts of pure math.

\item As we will see, finite fields have size $p^n$ for some prime integer $p$.
Finite fields with large $p$ and $n=1$ are crucial in many cryptosystems, and
of course cryptography is important in today's electronic commerce as well as
other electronic activities requiring privacy.  For another example, the AES
cryptosystem \cite{bib:aes} is built entirely out of a finite field with $p=2$
and $n=8$ (hence its natural operation on bytes):  even the S-box is just
reciprocation in the finite field.

\item Finite fields with $p=2$ are essential in coding theory (\cite{bib:ms},
\cite{bib:berl}, \cite{bib:golomb}), which is the study of the efficient
detection and correction of errors in a signal.  This is the kind of thing you
use (without even realizing it) whenever you talk on a cell phone or use a data
network.

\end{itemize}

%I haven't yet found a simple, low-level
%introduction to computation in finite fields, which is why I wrote this paper.

%% ----------------------------------------------------------------
\section{Scope}

Whereas finite fields may be presented in the abstract, this paper will take
the opposite approach by first constructing systems which are fields and which
are finite, and then illustrating how the resulting fields have properties
which the theory told us they would have.  As a result, few proofs will be
given; the emphasis is on computation.

%Not only will I eschew proofs in favor of computation, but moreover I will
%defer some computational methods to the appendices, to keep everything simple
%and smoothly flowing in the main discourse.

Since this paper cites many well-known theorems without proof, it is not by any
means a standalone treatise on finite fields.  For the intentionally omitted
theory, please consult any graduate-level text on abstract algebra.  In
particular I recommend Dummit and Foote \cite{bib:df}.  Also, Lidl and
Niederreiter \cite{bib:ln} is the standard (and excellent) reference for finite
fields.  (Note: Any theorem or algorithm in this paper which I've not
attributed to a specific reference either is my own or, more often, is
something I consider to be general knowledge.)  For the software-implementation
section, I assume only basic familiarity with C.

%% ----------------------------------------------------------------
\section{Audience}

My intended audience is non-specialists and fellow students.  For the first few
sections, which discuss how to add, subtract, multiply and divide, I will
presume a general familiarity with abstract algebra, e.g. 444 at Arizona State.
For the later sections on Galois theory, I will of course presume some
knowledge of Galois theory.  This entails a jump in the level of prerequisite
material, so these latter sections may be omitted.  (However, my treatment of
Galois theory is gentle; a reader without previoius exposure with Galois theory
should be able to read these sections.)

My particular concern is for (a) engineers who wish to have a better
understanding of what's going on, and (b) mathematicians who want be able to
perform computations, e.g. for testing out hypotheses.

%% ================================================================
\newpage
\section{Rings and fields; notation}

I will assume familiarity with ring and field axioms.  Fields discussed in this
document are almost always the finite ones, with occasional mention of the
rationals $\Q$, reals $\R$ and complexes $\C$.  The only rings discussed are
the integers $\Z$, as well as the ring of polynomials with coefficients in a
field.  For a field $F$, the latter is written $F[x]$.  The ideal generated by
a ring element $m$ will be written $\langle m \rangle$.

Recall that a ring of polynomials whose coefficients are in a field is a
Euclidean domain, hence a principal ideal domain, hence an integral domain.
(Remember \emph{FEPUI} [feh, pooey!]: fields $\subsetneq$ Euclidean domains
$\subsetneq$ PIDs $\subsetneq$ UFDs $\subsetneq$ integral domains.) This means
that we can factor our integers or polynomials, that an ideal is simply the set
of all multiples of some particular integer or polynomial, and that we can
divide one integer or polynomial by another non-zero integer or polynomial to
get a quotient and remainder.  Furthermore, the remainder is smaller than the
divisor in the usual way in the integers; for polynomials, the remainder has
smaller degree, or is the zero polynomial.

%\begin{item}
%\item In a unique factorization domain, loosely speaking we can factor
%	elements, e.g. in $\Z$, $6 = 2 \cdot 3$ and in $\Z[x]$
%\item In a principal ideal domain, all ideals are single generated, and
%	consist of all the multiples of the generator.  E.g. in $\Z$,
%	$\langle m \rangle =m\Z$ is simply all the multiples of $m$, and in
%	particular %	$(2) 2\Z$ is the set of all even numbers.  The ideal
%	property just means that an even number times either an even or an odd.
%\item In a Euclidean domain, we can divide one element by another, non-zero
%	element and get a quotient along with a remainder which is smaller
%	in some sense:  for $\Z$, smaller in the usual sense; for polynomials,
%	smaller means of smaller degree.
%\end{item}

