%% ================================================================
\part{Arithmetic}
\newpage
\chapter{The field $\F_p$}
\label{chap:fp}

One of the many finite-field theorems which this paper will reference (without
proof) is that all finite fields of a given size are isomorphic to one another.
This means that I may construct certain finite fields with the confidence that
any others will look something like them.  As the canonical representative of a
first family of finite fields, I will select the integers modulo a prime
integer $p$.  These are named $\F_p$, where the font is intended to indicate
that they are of equal importance with $\Q$, $\R$, $\C$, etc.  (An older
notation still occasionally used in the literature is GF($p$), which stands for
\textbf{Galois field}.)

Not all fields are accounted for by the $\F_p$'s, but later we will use the
$\F_p$'s to construct all the remaining finite fields.

%% ----------------------------------------------------------------
\section{Elements of $\F_p$}
\label{sec:elements_of_Fp}

Formally, elements of $\F_p$ are equivalence classes of integers modulo $p$,
where we say that two integers are equivalent mod $p$, written $a \equiv b
\modp$ or simply $a \equiv b (p)$, iff $a-b \,|\, p$.  For example, if $p=5$,
we have a set with five elements:
\begin{eqnarray*}
	\F_5 = \Z / 5 \Z  &=&
	\{\{\ldots, -10, -5, 0, 5, 10, \ldots \} \\
	&&\{\ldots, -9, -4, 1, 6, 11, \ldots \} \\
	&&\{\ldots, -8, -3, 2, 7, 12, \ldots \} \\
	&&\{\ldots, -7, -2, 3, 8, 13, \ldots \} \\
	&&\{\ldots, -6, -1, 4, 9, 14, \ldots \}\}
\end{eqnarray*}

Since the integers $\Z$ are a Euclidean domain, we may divide any integer $a$
by $p$ to obtain a quotient $q$ (which we don't care about) and a remainder $r$
such that $0 \le r < p$.  Clearly, any two elements of the same equivalence
class have the same remainder $r$, so we take the $r$'s to be the canonical
representatives of the equivalence classes.  (It is easy to show that reducing
mod $p$ is a ring homomorphism from $\Z$ to $\Z/p\Z$.) Then, the above
five-element set may be more compactly written as
$$
	\F_5 = \{ \overline{0}, \overline{1}, \overline{2}, \overline{3},
	\overline{4} \}
$$
where the overline refers to an equivalence class.

Then, the following two statements are equivalent:
\begin{eqnarray*}
	7 &\equiv& 2 \modfive \\
	\overline{7} &=& \overline{2}
\end{eqnarray*}
where the former statement involves integers and the latter involves
equivalence classes.  However, I will sloppily omit the overlines and write
$$
	\F_5 = \{ 0,1,2,3,4 \}
$$
where it is now implicit that we are working mod 5.  From a formal point of
view, this is sloppy; however, it is tolerable and helps avoid a forest
of overline bric-a-brac.

%% ----------------------------------------------------------------
\section{Arithmetic in $\F_p$}

Addition, subtraction and multiplication are as you would expect.  Examples,
again with $p=5$:
\begin{itemize}
\item $3+4 = 7$, which is 2 mod 5.
\item $3-4 = -1$, but remember we want our canonical representatives to be
	between 0 and $p-1$, inclusive, so we say $3-4=4$.
\item $3 \cdot 4 = 12$, which is 2 mod 5.
\end{itemize}

Simple enough.  In fact, addition, subtraction and multiplication work like
this in $\Z/m\Z$ for any integer $m$, prime or not.  As we'll see below,
though, to have a field (i.e. to have reciprocals for all non-zero elements) we
need the modulus to be prime.

How do we divide?  Clearly, it suffices to know how to reciprocate, e.g. if we
can compute $1/b$, then we can use multiplication (which we already know how to
do) to compute $a/b = a \cdot (1/b)$.  But how do we reciprocate? For example,
what is $1/2$ mod 5?  There are four methods.

%% ----------------------------------------------------------------
\section{First reciprocation method in $\F_p$}

One answer is to search for a reciprocal.  Since finite fields are finite, it
is possible to enumerate all the elements of the field and see which one works:
2 times 0 is 0, nope; 2 times 1 is 2, nope; 2 times 2 is 4, nope; 2 times 3 is
1, aha, so $1/2 = 3$.  The search method for reciprocation is acceptable for
small $p$, but if, say, you wanted to compute $1/7$ mod 1009 this way, you'd
probably get tired of looking before reaching 865.

%% ----------------------------------------------------------------
\section{Second reciprocation method in $\F_p$}

You might wonder, how do you know there will \emph{be} an inverse --- which is
tantamount to asking, how do we know $\F_p$ is really a field?  (All the other
field axioms besides the existence of multiplicative inverses, i.e.
reciprocals, are easily verified.  That is, the integers mod $m$ form a
commutative ring with identity regardless of whether $m$ is prime.) The proof
of the existence of reciprocals mod $p$ is a constructive proof, and so gives
our second method for reciprocation.

I said above that the homomorphism from $\Z$ to $\F_p$ is the \textbf{mod}
operation.  The opposite operation is called \textbf{lifting}.  This is not an
inverse function, of course, since the mod operation is not one-to-one.
Nonetheless, given an element of $\F_p$, sometimes we want to send it to some
element of $\Z$ --- usually to the canonical representative which is between 0
and $p-1$.

Given an element $a$ of $\F_p$, erase the imaginary overline which I am not
writing, i.e. lift $a$ to the integers.  If $a$ is 0 (or is a multiple of $p$,
which means $a$ is 0 mod $p$), then we expect no reciprocal.  But if $a$ is not
a multiple of $p$, then it is relatively prime to $p$.  This means its GCD with
$p$ is 1.  Using the \textbf{extended GCD}, also known as the \emph{GCD trick},
we can always write the output of the GCD algorithm as a linear combination of
the two inputs, i.e.
$$
	1 = as + pt
$$
for some integers $s$ and $t$.  But $pt$ is a multiple of $p$ and so is zero
mod $p$, so
$$
	1 \equiv as \modp
$$
which means the equivalence class containing $s$ is the reciprocal of the
equivalence class containing $a$.  Above we lifted to $\Z$ to do the GCD; now
we mod back to $\F_p$ by restoring the imaginary overline, and say that $s$ is
the reciprocal of $a$ in $\F_p$.

Now, this is great for proving existence of reciprocals in $\F_p$, but the
details of pencil-and-papering the extended GCD algorithm (details which I've
omitted) are tedious.  (Even using Blankinship's algorithm for extended GCD,
appendix \ref{appx:blankinship} on page \pageref{appx:blankinship}, it's better
but still tedious).  There are two more pleasant ways, as we will see.

%% ----------------------------------------------------------------
\section{Third reciprocation method in $\F_p$}
\label{sec:xpx}

The third method uses a little group theory.  Namely, recall that in any field
$F$, the non-zero elements form a group under multiplication --- this is called
the field's \textbf{multiplicative group}, and is written $F^\times$, or
occasionally $F^*$.  If $\F_p$ has $p$ elements, then there are $p-1$ non-zero
elements in $\F_p^\times$.

Recall Lagrange's theorem, which is your first real theorem in group theory:
the order of a subgroup divides the order of the parent group.  Also, given any
element $a$ of a finite group, you can form the cyclic subgroup generated by
the element, simply by taking powers of $a$ until you get the identity $e$.
(You \emph{will} get the identity eventually:  you will eventually run out of
elements and get a loop wherein $a^i = a^j$ for some $i$ and $j$, and then
you'll have $a^{i-j}=e$.)  Also recall that the order of an element, that is,
the least positive integer $k$ such that $a^k = e$, is the same as the order of
the cyclic subgroup generated by $a$.

So if the order of $a$ is $k$, and since by Lagrange's theorem $k \,\big|\,
|G|$, we have $a^{|G|} = e$ for all $a$ in $G$.  Now, a smaller power might
send a particular $a$ to $e$, and in fact for non-cyclic groups a smaller power
might suffice to send \emph{all} elements to $e$ (e.g. the Klein four-group has
order 4 but all elements have order 1 or 2).  But nevertheless we know that
$a^{|G|}$ will always be $e$, for any element $a$ of any finite group $G$.

For the case $G = \Fpx$, where $|G| = p-1$ and the identity is 1, we have
$$a^{p-1} = 1$$ for all non-zero elements of $\F_p$.  (Hence a quick proof of
Fermat's little theorem.) This has two direct consequences.  First, we can
write $$a^{p-2} = a^{-1}$$ for all non-zero elements, which gives us our third
algorithm for reciprocation, the $p-2$ algorithm.  Second, we can make this
true for all elements of $\F_p$ (including zero) by writing $$a^p = a$$ or
$$x^p-x = 0$$ which is a polynomial satisfied by all elements of $\F_p$.  This
sounds like it might be a useful piece of information to remember.

So, given the $p-2$ algorithm, we can easily reciprocate in $\F_p$.  What is
$1/2$ mod 5? Since $5-2=3$, we can invert any element simply by cubing it.
E.g. $2^3 = 8$ which is 3.  So $1/2=3$ mod 5.  And we can verify this by
writing $2 \cdot 3 = 1$ which checks out.

%% ----------------------------------------------------------------
\section{Repeated-squaring algorithm for exponentiation}
\label{sec:repeated_squaring}

Raising an element $a$ to the $p-2$ power by performing $p-3$ multiplications
is OK for small $p$, but not so good for larger $p$.  (E.g. to find $1/7$ mod
$1009$, 1006 multiplications by 7 is no fun at all.)  However, repeated
squaring makes it a breeze.  To see this by example, let $p=23$.  Then we can
reciprocate any element $a$ of $\F_{23}$ by raising $a$ to the 21st power.
Write out 21 as a sum of powers of 2, e.g. $21 = 16 + 4 + 1$.  Then $a^{21} =
a^{16} a^4 a^1$.  Then given $a$ we can square $a$ to get $a^2$, square that to
get $a^4$, square that to get $a^8$, and square one more time to get $a^{16}$.
Then just multiply the 1st, 4th and 16th powers and discard the 2nd and 8th
powers.

Instead of requiring $p-3$ multiplications, this requires only approximately
$\log_2(p-2)$ multiplications.  So you can raise something to the millionth
power with only 20 multiplications.  On paper this isn't too bad, and in a
computer it takes only an instant.

%% ----------------------------------------------------------------
\section{Fourth reciprocation method in $\F_p$; logarithms}
\label{sec:prims_in_Fp}

One of the finite-field theorems which this paper doesn't prove is that the
multiplicative group of a finite field is \emph{cyclic}.  This goes back at
least to Gauss, who proved that there are always \textbf{primitive elements} mod
$p$, i.e. always at least one element of $\Fpx$ such that all other elements
are powers of it.

In group-theoretic terms, this means there is an element $g$ (\emph{g} for
\emph{generator}) such that for all $a \in \Fpx$ there is a $k$, with $0 \le k
< p-1$, such that $a = g^k$.  Since $a^{p-1} = 1$, these exponents are actually
taken mod $p-1$.  If $a=g^k$, then $a^{-1} = g^{-k}$, or equivalently $a^{-1} =
g^{p-1-k}$.

This is an even quicker way to reciprocate in $\F_p$, but it comes at a little
expense.  The $p-2$ method requires you only to know what $p$ is; this method
requires a little precomputation in order to also find a generator $g$.  How do
you find a generator (i.e. primitive element) mod $p$?  Some slightly more
sophisticated techniques are discussed in appendix \ref{appx:prims_in_Fp} on
page \pageref{appx:prims_in_Fp}, but a simple and quite sufficient method is
just to search for one.  It turns out that either 2 or 3 works most of the
time, and if not, then try 5, etc.  You will find one.

For example, with $p=5$, powers of 2 are

\begin{tabular}{|c||c|c|c|c|}
\hline
$k$   & 1 & 2 & 3 & 4\\
\hline
$2^k$ & 2 & 4 & 3 & 1\\
\hline
\end{tabular}

which runs through all of $\F_5^\times$, so 2 is primitive mod 5.

With $p=7$, powers of 2 are

\begin{tabular}{|c||c|c|c|c|c|c|}
\hline
$k$   & 1 & 2 & 3 & 4 & 5 & 6\\
\hline
$2^k$ & 2 & 4 & 1 & 2 & 4 & 1\\
\hline
\end{tabular}

which doesn't run through all of $\F_7^\times$.  But, powers of 3 are

\begin{tabular}{|c||c|c|c|c|c|c|}
\hline
$k$   & 1 & 2 & 3 & 4 & 5 & 6\\
\hline
$3^k$ & 3 & 2 & 6 & 4 & 5 & 1\\
\hline
\end{tabular}

so 3 is primitive mod 7.

You can similarly show (just by trying it) that 2 is primitive mod 11.  I'll
use 11 as an example of log reciprocation, since 11 is big enough to be a
little more interesting.

We saw above that since $\Fpx$ is cyclic, we can write any non-zero $a$ as
$$a=g^k.$$ Then we define the logarithm base $g$ of $a$ to be $$ \log_g(a) = k
$$  (This is sometimes called a \textbf{discrete log} since it takes only integer
values.)

Now I can tabulate field elements and their logs, sorting by field element, to
obtain a \textbf{log table} (Lidl and Niederreiter call this an \emph{ind table},
for \emph{index}) as follows:

\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $\log_2(a)=k$ & 0 & 1 & 8 & 2 & 4 & 9 & 7 & 3 & 6 &  5 \\
\hline       $a=2^k$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
\end{tabular}

Also, I can sort the log table by log value to obtain an antilog table:

\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|}
\hline $\log_2(a) =   k$ & 0 & 1 & 2 & 3 & 4 &  5 & 6 & 7 & 8 & 9 \\
\hline         $a = 2^k$ & 1 & 2 & 4 & 8 & 5 & 10 & 9 & 7 & 3 & 6 \\
\hline
\end{tabular}

Since $a^{-1} = g^{-k} = g^{p-1-k}$, it's easy to reciprocate just by looking
at the antilog table.  E.g. $8=2^3$ (three places from the left), so $1/8 =
2^{10-3} = 2^7 = 7$ (three places from the right).

You can multiply using the log and antilog tables by the familiar rule
$\log_g(ab) = \log_g(a) + \log_g(b)$, where you must remember to do the
addition mod $p-1$:
$$
ab = g^{\log_g(ab)} = g^{\log_g(a)+\log_g(b)}
$$
Likewise you can do division in a single step (i.e. instead of finding the
reciprocal, then multiplying by the reciprocal) using the familiar $\log_g(a/b)
= \log_g(a) - \log_g(b)$:
$$
a/b = g^{\log_g(a/b)} = g^{\log_g(a)-\log_g(b)}
$$

See also appendix \ref{appx:shanks} on page \pageref{appx:shanks} for an
efficient way to build large log tables (e.g. in a software implementation).

%% ================================================================
\newpage
\chapter{The field $\Fpn$}

That's about it for $\F_p$:  we know how to add, subtract, multiply and divide,
and we have the polynomial $x^p-x = 0$ of which all elements of $\F_p$ are
roots.  Now we can look at all the other finite fields.

I went into some detail with $\F_p$, which may have seemed overkill --- after
all, $\F_p$ is just integers mod $p$, which are familiar, and who really needs
four different techniques for reciprocation when any one of them would suffice?
While $\Fpn$ may be a little less familiar, much of what we for $\Fpn$ will be
in direct analogy to things in $\F_p$, and those analogies will be instructive.
We'll see another reason in the next section.

%% ----------------------------------------------------------------
\section{Field characteristic and prime subfield}
\label{sec:char_p_of_Fpn}

Consider the order of 1 in the additive group of a finite field $F$.  This
order is called the \textbf{characteristic} of the field.  It cannot be infinite
(we would run out of elements) so let $M$ be the order of 1.  Then 1 added to
itself $M$ times is 0, i.e. $M\cdot 1 = 0$.  If $M$ is composite, with
non-trivial factors $a$ and $b$, then we get $(a\cdot 1)(b \cdot 1) = 0$ which
gives zero divisors which are not present in a field.  So, $M$ must be prime
and without further ado I rename $M$ to be $p$.

Furthermore, it's easy to show that the set of distinct repeated sums of 1 in
$F$ (i.e. $1$, $1+1$, etc.) forms a subfield which is isomorphic to $\F_p$.

%% ----------------------------------------------------------------
\section{Existence of $\Fpn$}
\label{sec:existence_of_Fpn}

Whenever we have a smaller field $K$ (finite or not) and a bigger field $F$
with $K$ a subset of $F$, we say that $K$ is a \textbf{subfield} of $F$, and
that $F$ is an \textbf{extension field} of $K$.  If you write down the axioms
for a vector space $V$ over a field $K$ (i.e. scalars are elements of $K$),
then replace the $V$'s with $F$'s (i.e. vectors are elements of $F$), you can
simply check off all the axioms and see that they're all satisfied.  This means
that $F$ is necessarily a \emph{vector space} over $K$, and in particular, any
finite field is a vector space over $\F_p$ for some $p$.  Since the vector
space is finite, the dimension of that vector space is finite; I'll call it
$n$.  This forces the size of any finite field $F$ to be $p^n$ for some prime
$p$ and some positive integer $n$.  So if we construct a finite field, we know
it will have prime-power order.

Another finite-field theorem tells us that all finite fields of a given size
are isomorphic to one another.  This means that if, given $p$ and $n$, I can
construct even a single finite field of order $p^n$, I'll in some sense have
constructed them all.  It remains only to actually construct such a field.

To do that, we start by looking at the ring of polynomials with coefficients in
the field $\F_p$, which we call $\F_p[x]$.  While each coefficient has only $p$
possible values, the degree can be arbitrarily large --- in particular, even
though the coefficients are taken mod $p$, the exponents are not, so you can
have $x^{100}$, $x^{1000}$, etc.

Also notice that there are $p-1$ possible degree-0 polynomials (excluding 0
itself), $(p-1)p$ of degree 1 (leading coefficient must be non-zero for the
polynomial to be linear and the rest can be anything mod $p$), $(p-1)p^2$ of
degree 2, etc. and in general $(p-1)p^n$ of degree $n$.  So although $\F_p[x]$
has infinitely many polynomials in it, there are only \emph{finitely many}
polynomials of a given degree $n$, and likewise only finitely many polynomials
of degree less than $n$.

Second, since $\F_p$ is a field, $\F_p[x]$ is a Euclidean domain (hence a PID
and an integral domain) so it makes sense to talk about \emph{irreducible
polynomials} in $\F_p[x]$, and for simplicity we will take our irreducibles to
be \textbf{monic}, i.e. with 1 for the leading coefficient\footnote{There are
technical distinctions between \emph{prime} and \emph{irreducible}, which
disappear for PIDs.  I will nonetheless choose to reserve the term \emph{prime}
for integers $p$ which don't factor any more than into $\pm p$ and $\pm 1$, and
I will reserve the term \emph{irreducible} for polynomials which don't factor
into the product of polynomials of lesser degree.  Over $\F_p$, or any field
for that matter, we can always play with the leading coefficient and pull out a
scalar factor --- but I won't consider this to be an interesting factorization.
That is, over a field, polynomial factorization is interesting only up to
scalars, which is why we choose monics as our standard irreducibles.}.

Given a monic irreducible $r(x)$ (for this to be sensible we require $\deg(r)
\ge 1$), we can form the ideal $\langle r(x) \rangle$ generated by it.  Since
$\F_p[x]$ is a commutative ring with identity, this ideal is nothing more than
the set of all multiples of $r(x)$, that is, all those polynomials in $\F_p[x]$
which, when factored into irreducibles, have $r(x)$ as one of their factors.
This is in exact analogy to $\langle p \rangle$ being an ideal of $\Z$: the
ideal $\langle p \rangle$ is the set of all multiples of $p$ in $\Z$; the ideal
$\langle r(x) \rangle$ is the set of all multiples of $r(x)$ in $\F_p[x]$.
Also, since $r(x)$ is irreducible, the ideal $\langle r(x) \rangle$ is maximal
in $\F_p[x]$.

Now\footnote{In the general theory, one allows $\F_q$, with $q=p^m$, to be the
base field and studies $\F_{q^n}$ as an extension.  However, $\F_q$ is
precisely what we're still learning to construct, so I'll defer use of this
idiom.} we simply take the quotient ring $\F_p[x] / \langle r(x) \rangle$.
Since $\F_p[x]$ is commutative and $\langle r(x) \rangle$ is maximal, $\F_p[x]
/ \langle r(x) \rangle$ is a field --- this is what the theory guarantees for
us.  Let $n$ be the degree of $r(x)$.  Then we write $$\Fpn = \F_p[x] / \langle
r(x) \rangle$$

(When we formed $\F_p = \Z/p\Z$, we saw that we got a ring whether or not $p$
was prime, but needed $p$ prime to get a field.  Here too, $\F_p[x]/\langle
r(x) \rangle$ is a ring regardless of whether $r(x)$ is irreducible, but we'll
need it to be irreducible so that we can reciprocate all non-zero elements.)

You might ask if there is a monic irreducible for all $p$ and $n$, and you
might also ask what happens if there is more than one --- how can $\Fpn$ be
uniquely defined?  The short answer is that the finite-field theorems guarantee
there is in fact always at least one monic irreducible (see section
\ref{sec:count_irrs_and_prims}) for all $p$ and $n$, and if there is more than
one (which generally there is) then all such fields are isomorphic to one
another.  Later on in this paper we'll look at those isomorphisms in more
detail.

So what does one of these $\Fpn$'s  look like?  How do we compute in it?
Where's the beef?

When we constructed $\F_p$, we took the infinite set $\Z$, then divided by $p$,
discarded the quotient and kept the remainder to get a finite set of possible
remainders $0$ through $p-1$.  We defined elements of $\F_p$ to be the set of
equivalence classes where two integers were equivalent if they had the same
remainder.

Here we can do the same thing: $\F_p[x]$ is a Euclidean domain so we can divide
any polynomial by $r(x)$ to get a remainder.  Now, $\F_p[x]$ is not totally
ordered, but it is partially ordered by degree.  When we divide by $r(x)$, we
get a quotient which we again discard, and we get a remainder which is zero, or
whose degree is less than $r(x)$'s degree.  To see how that works, I'll do a
few more computational examples.

%% ----------------------------------------------------------------
\section{Computation in $\F_p[x]$}
\label{sec:computation_in_fp_x}

Since $\F_p[x]$ is a ring, we can add, subtract and multiply.  Since it's a
Euclidean domain, we can divide and get a quotient and a remainder.  It's
important to remember this distinction:  e.g. in $\Z$, $9/4$ has quotient 2 and
remainder 1, whereas in $\Q$ it's exactly  $9/4$ with never any remainder.
Here we're doing ring division, with quotient and remainder \footnote{$\F_p[x]$
does have a field of fractions, as $\Z$ has $\Q$, which we call $\F_p(x)$: the
field of rational functions in $x$ with coefficients in $\F_p$.  This is an
infinite field of characteristic $p$, which makes it a little interesting.
However, we won't deal at all with the field $\F_p(x)$ in this paper.  To
dispel another frequent misconception while we're at it:  $\Fpn$ is not
$\Z/p^n\Z$, except for $n=1$:  in particular $\Z/p^n\Z$ has zero divisor $p$
whenever $n>1$ so it cannot be a field.}.

All these operations are done in precisely the same way you learned to do
arithmetic in elementary school --- with one small exception.

First, for brevity of notation I'll often strip off the $x$'s, exponents and
plus signs from elements of $\F_p[x]$.  E.g. $x^3+x^2+1$ will be simply 1101.
(If $p$ were greater than 10, which it won't be from here on out, I would write
$1,1,0,1$ to avoid ambiguity.) This \textbf{compact notation} will be familiar
from synthetic division in high school.  Then $x^3+x^2+1$ is an example of what
I will refer to as \textbf{full notation}.

Now, addition is just like integer addition in elementary school (and similar
to synthetic addition of polynomials in high school) with the one small
exception that there are no carries.  E.g. with $p=5$,

\begin{verbatim}
  1044
+  231
------
  1220
\end{verbatim}

Likewise,

\begin{verbatim}
  1044
-  231
------
  1313
\end{verbatim}

We simply operate coefficientwise, using $\F_p$ arithmetic which we already
know how to do.  Remember that since the coefficients are in $\F_p$, we always
want coefficients between $0$ and $p-1$, so if a coefficient goes negative on
subtraction, add $p$ to the difference.

Multiplication is more of the same:  form partial products by multiplying
scalars times polynomials, then add the partial products.  Again with $p=5$:

\begin{verbatim}
  1044
*  231
------
  1044
 3022
2033
------
234014
\end{verbatim}

The last thing to do is division.  (I emphasize that this is still
quotient-and-remainder division in the ring $\F_p[x]$.)  And it's just what
you'd think.  Remember that you don't do carries, but also remember that
there's no concept of ``less than'' for coefficients.  E.g. the integer 231
doesn't go into the integer 114 because 231 is bigger than 114.  But here, no
problem.  To get each quotient digit, divide the leading coefficient of your
running remainder by the leading coefficient of the divisor (which is
necessarily non-zero since you're not dividing by zero), and we saw in chapter
\ref{chap:fp} that you can always do that in $\F_p$.  But do stop when the
\emph{degree} of the running remainder is less than the degree of the divisor.
For example:

\begin{verbatim}
         33 = quotient
    +--------
231 |  1044
    |- 143    1st quotient digit = 3 since 1/2 = 3 mod 5; 231 * 3 = 143
    +--------
    |   114
    |-  143   2nd quotient digit = 3 since 1/2 = 3 mod 5; 231 * 3 = 143
    +--------
    |    21 = remainder
\end{verbatim}

so here the quotient is 33 and the remainder is 21.  Using the full notation,
this means $x^3+4x+4$ is $2x+1$ mod $2x^2+3x+1$.  (Note that $231$ is not
irreducible, and doesn't need to be --- this example merely shows ring division
for some arbitrary ring elements.)

Next we need to know how to find irreducibles $r(x)$, and then we'll have all
the machinery we need to take remainders when constructing $\F_p[x] / \langle
r(x) \rangle$.

%% ----------------------------------------------------------------
\section{Simple determination of irreducibles in $\F_p[x]$}
\label{sec:find_irreds}

In appendix \ref{appx:irreds_in_Fp} on page \pageref{appx:irreds_in_Fp} I give
some techniques for irreducibility testing.  Here I'll just give some simple
methods.

If a polynomial has degree 3 or less and factors into smaller-degree terms,
then at least one of the factors must be linear.  We know that linear factors
correspond to roots:  If $a$ is a root of $f(x)$, then $f(x)$ has $x-a$ as a
factor and vice versa.  And it's easy to check for roots in $\F_p$, since
$\F_p$ is finite:  Just try all the elements.

This gives one method for irreducibility testing for $n \le 3$:  Evaluate
$r(0)$, $r(1)$, \ldots, $r(p-1)$ and if those are all non-zero, $r(x)$ is
irreducible.  E.g. with $p=2$ and $r(x) = x^3+x+1$, $r(0) = 1$ and $r(1) = 1$
so $x^3+x+1$ is irreducible.

Even for polynomials of degree higher than 3, the root test can be used to
quickly determine that a polynomial is \emph{not} irreducible.  When $p=2$,
this is particularly easy:  $r(0)$ is just the constant term, so if the
constant term is 0, $r(x)$ is reducible (except for $r(x) = x$).  Also, $r(1)$
is just the sum of coefficients mod 2, so if there is an even number of
non-zero coefficients, $r(x)$ is reducible (except for $r(x) = x+1$).  E.g.
with $p=2$, $x^{37}+x^{28}+x^9+x^7+x$ is reducible, as is
$x^{37}+x^{28}+x^9+1$.

The second simple method for irreducibility testing (after you've already
checked for linear factors via the root test) is trial division.  Since there
are finitely many polynomials in $\F_p[x]$ with degree less than the degree of
$r(x)$, just try them all.  To be a little more sophisticated, avoid the trial
factors you know are reducible.  (An analogy with the integers:  You don't have
to test 6 as a factor of some number $n$, if you've already tried, or will try,
2 and 3.)  Also, try factors with degree only up to $n/2$, since if there were
factors of higher degree, you'd have already found the corresponding factor of
lower degree.  (Another analogy with the integers: when factoring an integer
$n$ by trial division, try only up to $\sqrt{n}$.)

Let's use the above to enumerate all irreducible polynomials of degree up to 4
with $p=2$.

For $n=1$, we have $x$ and $x+1$ (10 and 11 using the compact notation), which
are already linear and therefore irreducible.

For $n=2$, we have (using the compact notation) $100$, $101$, $110$ and $111$.
Two of these have a zero constant term and so have 0 as a root; $101$ has an
even number of 1's and so has 1 as a root.  That leaves 111 ($x^2+x+1$)
which is quadratic and rootless, therefore irreducible.

For $n=3$, there are the eight possibilities
$$
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
$$
All those ending in 0 have 0 as a root; 1001, 1010, 1100 and 1111 have
1 as a root.  That leaves 1011 and 1101 ($x^3+x+1$ and $x^3+x^2+1$)
which are irreducible since quadratic and rootless.

For $n=4$, there are the sixteen possibilities
\begin{eqnarray*}
&&10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111, \\
&&11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111
\end{eqnarray*}
The root test pares the list down to
$$
10011, 10101, 11001, 11111
$$
Since the root test excludes all linear factors, only the quadratic factors
remain and we may restrict ourselves to the irreducible quadratics.  There is
only one, namely, 111.  Synthetic division as above shows that $10101 = 111^2$;
the other three have non-zero remainder and therefore must be irreducible.

To summarize:

Monic irreducibles with $p=2$, $n=1$ through 4

\begin{tabular}{|c|r|r|}
\hline $n$ & Compact notation & Full notation \\
\hline
\hline 1 &  10 & $x$ \\
         &  11 & $x+1$ \\
\hline 2 &  111 & $x^2+x+1$ \\
\hline 3 &  1011 & $x^3+x+1$ \\
         &  1101 & $x^3+x^2+1$ \\
\hline 4 &  10011 & $x^4+x+1$ \\
         &  11001 & $x^4+x^3+1$ \\
         &  11111 & $x^4+x^3+x^2+x+1$ \\
\hline
\end{tabular}

These will be used frequently in the examples to follow.

A third and time-honored method for irreducibility testing is simply to consult
a table.  See Lidl and Niederreiter for lots of tables, or my very abbreviated
version in appendix \ref{appx:tables_of_irreds_in_Fp} on page
\pageref{appx:tables_of_irreds_in_Fp}.

%% ----------------------------------------------------------------
\section{Elements of $\Fpn$}
\label{sec:adjoin_u}

So now we know how to find monic irreducibles $r(x)$ for any $p$ and $n$.  (The
theory guarantees us we will find at least one.)  Also, we know how to do ring
division by $r(x)$, to produce remainders.  Note that if $r(x)$ has degree $n$,
then the remainders all have degree less than $n$.  E.g. with $p=2$ and $n=2$,
selecting $r(x) = x^2+x+1$, possible remainders are
$$
	0, 1, x, x+1
$$
so there are four equivalence classes (i.e. all polynomials whose remainder mod
$r(x)$ is $0$, $1$, $x$ or $x+1$).

%just as in section \ref{sec:elements_of_Fp} on page
%\pageref{sec:elements_of_Fp}.

More generally, there are $p$ possibilities for each coefficient, and $n$ of
them:  from the $x^0$ term up to and including the $x^{n-1}$ term.  Thus there
are $p^n$ elements in this set which jives with what the theory told us above,
from vector-space considerations.

For the integers mod $p$, I said we often sloppily move between equivalence
classes mod $p$, and canonical representatives.  E.g. $7 \equiv 2 \textrm{ mod }
5$ (correct), $\overline{7}=\overline{2}$ (correct), $7=2$ (sloppy).  And I did
that fully aware of the sloppiness --- since it is tolerable, and since the
alternative is an undesirable forest of overlines.

However, with this second mod --- polynomials mod $r(x)$ --- I will not be
sloppy.  Rather, I'll use a more precise notation from field theory.  Let $x +
\langle r(x) \rangle$ be the set of all multiples of $r(x)$, plus $x$.  Let $u
= x + \langle r(x) \rangle$.  (If you like, $u=\overline{x}$ using the overline
notation from section \ref{sec:elements_of_Fp} on page
\pageref{sec:elements_of_Fp}.)  These are all the polynomials in $\F_p[x]$
which are in the same equivalence class as $x$.  Then I write

$$ \F_p[x] / \langle r(x) \rangle \cong \F_p(u) $$

i.e. we \emph{adjoin} to the field $\F_p$ a root $u$ of $r(x)$.

My first reaction to this a few months ago was, ``Where did this $u$ come from?
What was wrong with $x$?''  But in fact, $x$ is an element of $\F_p[x]$, the
polynomial ring, and $u$ is an element of the finite field $\Fpn = \F_p[x] /
\langle r(x) \rangle$ (which we haven't yet seen is really a field).  This
apparently subtle distinction turns out to be important later on, so that we
don't go mad when we talk about splitting fields.  And really, $u$ does behave
much like $x$ does, so it's not a completely new thing:  if $r(x)$ is, say,
$x^4+x+1$ with $p=2$, then $u^4+u+1$ is zero.

I will occasionally write such elements either using the full notation such as
$$
	0,1,u,u+1
$$
or in the compact notation such as
$$
	00,01,10,11
$$
(Notice that, without context, one can't distinguish compactly written ring
elements (in $x$) from field elements (in $u$).  So, in what follows I will be
careful to always make it clear what I'm referring to.)

%% ----------------------------------------------------------------
\section{Addition, subtraction and multiplication in $\Fpn$}
\label{sec:RAR_and_RER}

Addition and subtraction of elements of $\Fpn$ is easy:  Just do it
componentwise.  Addition and subtraction are just the same as in $\F_p[x]$ so I
won't even write new examples.

For multiplication, there are two methods.  The first is what I call the
\textbf{ring-and-reduce} method; the second is \textbf{reduce-en-route}.  (You
can call them RAR and RER, and pretend you're a dog --- or a car that won't
start.  Your acquaintances will think you're daft, if they didn't already.)

For the former (RAR), just combine lifting, ring multiplication and reduction
mod $r(x)$, which were described in section \ref{sec:computation_in_fp_x} on
page \pageref{sec:computation_in_fp_x}.  (E.g. to compute $3 \cdot 4$ in
$\F_p$, we lifted 3 and 4 from $\F_p$ to $\Z$, took 3 times 4 is 12 in the ring
$\Z$, then divided by 5 to get the remainder 2 back in $\F_p$.)  For example,
with $p=2$ and $r(x) = x^4+x+1$, to compute $(u^3+1)\cdot(u^2+u+1)$, first lift
from $\Fpn$ to $\Fp[x]$ to obtain $(x^3+1)\cdot(x^2+x+1)$, then multiply in
$\Fp[x]$:

\begin{verbatim}
  1001
* 0111
------
  1001
 1001
1001
------
111111
\end{verbatim}

which gets you the unreduced product.  Then divide by $r(x)$ and take
the remainder, discarding the quotient:

\begin{verbatim}
            11
      +--------
10011 | 111111
      | 10011
      +--------
      |  11001
      |  10011
      +--------
      |   1010
\end{verbatim}

So, with $p=2$ and $r(x) = x^4+x+1$, $$ 1001 \cdot 0111 = 1010 $$ or with full
notation, $$ (u^3+1) \cdot (u^2+u+1) = u^3+u $$

The second multiplication method (RER) is essentially the same, but is
sometimes handier.  Proceeding by example with $p=2$ and $r(x) = x^4+x+1$,
$$u^4+u+1  = 0$$ from which $$u^4 = -u - 1$$  With $p=2$, minuses are pluses so
$$ u^4 = u + 1 $$ but please be careful for $p \ne 2$.  In the RAR method,
since input degrees are $n-1$ or less, the degree of the unreduced product can
be as big as $2n-2$.  In the RER method, whenever you see anything of degree
$n$, reduce it at first appearance by replacing, for example, $u^4$ with $u+1$.

Why RER?  Two reasons.  First, in a computer program, the RAR method takes
twice the storage space for the unreduced product; the RER method does not.
But more importantly for pencil-and-paper arithmetic, while the RAR method is
probably easier for multiplication in general, the RER method is easier when
you're multiplying by $u$, as we'll see in the next section.

%% ----------------------------------------------------------------
\section{Primitivity in $\Fpn$}

We saw above that the multiplicative group $\F_p^\times$ is cyclic, and so
there are always primitive elements mod $p$.   Your first guess for a generator
might be 2, and often 2 is a generator, but not always.  For $p=7$, we saw that
2 doesn't generate $\F_7^\times$, but 3 does.

Likewise, it can be shown that the multiplicative group $\Fpn^\times$ is
cyclic, and so there are always primitive elements mod $r(x)$.  Your first
guess might be $u$, which sometimes is primitive but not always\footnote{
Whether or not $u$ is a primitive element, it has some order in the
multiplicative group.  Lidl and Niederreiter \cite{bib:ln} (as well as
Berlekamp \cite{bib:berl}) call this order the \textbf{period} of $r(x)$.  In
their tables, they call the period $e$.}.  If $u$ is primitive, for brevity I
say that $u$ is a \textbf{generating root}.  Also, $r(x)$ in $\F_p[x]$ is said to
be a \textbf{primitive polynomial}\footnote{For polynomials with coefficients
merely in a ring rather than a field, there is a completely different
definition of primitive polynomial --- namely, a polynomial the GCD of whose
coefficients is a unit.  However, it's clear from the context which kind of
primitivity we're talking about.} if $u$ is a primitive element mod $r(x)$.

(Note:  This is a somewhat non-standard use of the terms \emph{primitive} and
\emph{generator} in the context of field theory, as described in more detail in
section \ref{sec:generator_two_defs}.)

We saw above that there exists a count function for the number of monic
irreducibles given $p$ and $n$.  That function always takes positive values, so
you'll always find a monic irreducible.  Likewise there exists a count function
for the number of primitive monic irreducibles given $p$ and $n$ (see section
\ref{sec:count_irrs_and_prims}).  This function also always takes positive
values, so you'll always find a primitive monic irreducible.  In particular,
when there is only one monic irreducible ($p=2$, $n=2$), then that monic
irreducible is necessarily primitive.

%% ----------------------------------------------------------------
\section{Powers of $u$ and LFSRs}
\label{sec:RER}

Taking powers of $u$ is where the RER method for multiplication shines.  You
can do the following:

\begin{itemize}
\item Start with $u$.
\item In the compact notation, shift all coefficients left by one position.
This amounts to multiplying by $u$.
\item If there is a non-zero coefficient in the $u^n$ position, use $r(u)$ to
get rid of it.
\end{itemize}

For example, with $p=2$, $n=4$, $r(x) = x^4+x+1$, which is 10011, $u^4+u+1 = 0$
so I may solve for $u^4$ to get $u^4 = -u - 1$, which is $u+1$ since $p=2$.  So
whenever I see $10000$, I can subtract it out and add in $0011$.

\begin{tabular}{|r|rr|}
\hline
$k$ & $u^k$ & \\
\hline
\hline
 1 & &$0010$ \\
 2 & &$0100$ \\
 3 & &$1000$ \\
 4 &$10000$ & $= 0011$\\
 5 & &$0110$  \\
 6 & &$1100$  \\
 7 & $11000$ &$= 1011$ \\
 8 & $10110$ &$= 0101$ \\
 9 & &$1010$  \\
10 & $10100$ & $0111$\\
11 & &$1110$  \\
12 & $11100$ & $1111$\\
13 & $11110$ & $1101$\\
14 & $11010$ & $1001$\\
15 & $10010$ & $0001$\\
\hline
\end{tabular}

When $p=2$, regardless of $n$, addition is the XOR operation (exclusive or).
This shift-left-and-fold-in business can be implemented efficiently in an
electronic circuit in which case it is called, aptly enough, a \textbf{linear
feedback shift register}, or LFSR\footnote{Specifically, what I show here is a
\emph{reflected Galois-configuration LFSR}, which is distinct from
Fibonacci-configuration LFSRs which you may encounter in the literature.
Nonetheless, characteristic polynomials are the same.}.  These circuits are
important in coding theory and cryptography.  With initial data set to $1$,
clearly the number of iterations before the sequence repeats will be maximal
when $u$ is a primitive element, i.e. when $r(x)$ is primitive, since a left
shift is equivalent to multiplying by $u$.  Hence the saying that ``primitive
polynomials give rise to maximum-period linear feedback shift registers''.
Schneier \cite{bib:sch} has a lot more to say about LFSRs.  I also discuss
LFSRs in part \ref{part:LFSRs} of this paper.  I discuss primitivity testing in
greater detail in appendix \ref{appx:prims_in_Fpx} on page
\pageref{appx:prims_in_Fpx}.

%% ----------------------------------------------------------------
\section{First reciprocation method in $\Fpn$}

We now know how to add, subtract and multiply in $\Fpn$, and as with $\Z/m\Z$,
all this works regardless of whether $r(x)$ is irreducible, i.e. whether or not
$\F_p[x]/\langle r(x) \rangle$ is a field.  But how do we divide? Given $a/b$,
it suffices to know how to reciprocate $b$, since then we can use
multiplication (which we already know how to do) to multiply $a$ and $1/b$.

As with $\F_p$, there are four methods for reciprocation.  The first is simply
a search, and for small $p^n$ this is quite fine.  What is $1/u$ mod $x^4+x+1$?
You can try $0000$, $0001$, $0010$, etc. until you happen upon $1001$.

%% ----------------------------------------------------------------
\section{Second reciprocation method in $\Fpn$}

You might wonder if the search method will always work, i.e. if $\Fpn$ is
really a field.  The proof of the existence of reciprocals mod $r(x)$ is a
constructive proof, and so gives our second method for reciprocation.

As with integers, given $f(u)$ in $\Fpn$, lift to $f(x)$ in $\F_p[x]$.  If
$f(x)$ is 0 (or is a multiple of $r(x)$, which means $f(x)$ is 0 mod $r(x)$),
then we expect no reciprocal.  But if $f(x)$ is not a multiple of $r(x)$, then
it is relatively prime to $r(x)$ since $r(x)$ is irreducible.  This means its
GCD with $r(x)$ is 1.  Using the extended GCD, we can always write the output
of the GCD algorithm as a linear combination of the two inputs, i.e.
$$
	1 = f(x) s(x) + r(x) t(x)
$$
for some $s(x)$ and $t(x)$ in $\F_p[x]$.  But $rt$ is a multiple of $r$ and so
is zero mod $r$, so
$$
	1 \equiv f(x)s(x) \mod r(x)
$$
which means the equivalence class of $s(x)$ is the reciprocal of the
equivalence class of $f(x)$. After doing the mod operation to get back to
$\Fpn$, $s(u)=1/f(u)$.  (Actually, the GCD is a scalar, not necessarily 1, so
go ahead and compute the GCD, then divide $s(x)$ by it.)

This is great for proving existence of reciprocals, but just as in the $\F_p$
case, the details of pencil-and-papering the extended GCD algorithm  are
tedious.  (See appendix \ref{appx:blankinship} on page
\pageref{appx:blankinship} for more information on the extended-GCD method.)
There are two better ways, as we will see.

%% ----------------------------------------------------------------
\section{Third reciprocation method in $\Fpn$}
\label{sec:pn2_recip}

Third, we can use Lagrange's theorem, just as in $\F_p$, and recognize
that the multiplicative group $\Fpn^\times$ has order $p^n-1$.  Therefore
for all $a$ in $\Fpn^\times$,
$$ a^{p^n-1} = 1$$
from which
$$ a^{p^n-2} = a^{-1}$$
This is the $p^n-2$ rule for reciprocation.  E.g. in $\F_{2^4}$, we just raise
$a$ to the 14th power.  As above, the repeated-squaring method for
exponentiation (section \ref{sec:repeated_squaring}, page
\pageref{sec:repeated_squaring}) can dramatically reduce the number of
multiplications needed.

Note also that we can make this true for 0 as well, i.e. for all of $\Fpn$,
by writing
$$ x^{p^n} - x = 0$$
so we have a polynomial of which all elements of $\Fpn$ are roots.

%% ----------------------------------------------------------------
\section{Fourth reciprocation method in $\Fpn$; logarithms}
\label{sec:fpn_recip_4_and_logs}

Fourth, we can use the fact that $\Fpn^\times$ is a cyclic group, then
precompute a primitive element.  (If we already know that $r(x)$ is a primitive
polynomial, then we know $u$ will be a primitive element.)  Then, we can use
logarithms.  If $g$ is a primitive element mod $r(x)$, then for all $a$ in
$\Fpn$, $$a = g^k$$ for some $0 \le k < p^n-1$.  Then $$a^{-1} = g^{-k} =
g^{p^n-1-k}$$

For example, with $p=2$, $n=4$ and $r(x) = x^4+x+1$ as above, and using $g=u$,
take powers of $u$ using the RER method and sort by field element to obtain the
log table:

\begin{tabular}{|r|r|}
\hline
$\log_g(a) = k$ & $a = g^k$ \\
\hline
\hline
15 & $0001$ \\
 1 & $0010$ \\
 4 & $0011$ \\
 2 & $0100$ \\
 8 & $0101$ \\
 5 & $0110$ \\
10 & $0111$ \\
 3 & $1000$ \\
14 & $1001$ \\
 9 & $1010$ \\
 7 & $1011$ \\
 6 & $1100$ \\
13 & $1101$ \\
11 & $1110$ \\
12 & $1111$ \\
\hline
\end{tabular}

and sort by log value to obtain the antilog table:

\begin{tabular}{|r|r|}
\hline
$\log_g(a) = k$ & $a = g^k$ \\
\hline
\hline
 1 & $0010$ \\
 2 & $0100$ \\
 3 & $1000$ \\
 4 & $0011$ \\
 5 & $0110$ \\
 6 & $1100$ \\
 7 & $1011$ \\
 8 & $0101$ \\
 9 & $1010$ \\
10 & $0111$ \\
11 & $1110$ \\
12 & $1111$ \\
13 & $1101$ \\
14 & $1001$ \\
15 & $0001$ \\
\hline
\end{tabular}

It's easy to reciprocate just by looking at the tables.  E.g.  $0011=0010^4$,
so $1/0011 = 0010^{15-4} = 0010^{11} = 1110$.

You can multiply using the log and antilog tables by the familiar rule
$\log_g(ab) = \log_g(a) + \log_g(b)$, where you must remember to do the
addition mod $p^n-1$:
$$
ab = g^{\log_g(ab)} = g^{\log_g(a)+\log_g(b)}
$$
Likewise you can do division in a single step (i.e. instead of finding the
reciprocal, then multiplying by the reciprocal) using the familiar $\log_g(a/b)
= \log_g(a) - \log_g(b)$:
$$
a/b = g^{\log_g(a/b)} = g^{\log_g(a)-\log_g(b)}
$$
As well, you can use logs to exponentiate (which will be useful below):
$$
a^p = g^{\log_g(a^p)} = g^{p\log_g(a)}
$$

See also the tables in section \ref{appx:Fp_log_tables} on page
\pageref{appx:Fp_log_tables}, or the much more extensive list in Lidl
and Niederreiter \cite{bib:ln}.

In the pre-electronic era, such tables were the bee's knees.  Nowadays, log
tables might not seem as useful as they once were.  But in fact, they can be
used inside a computer program to implement lightning-fast finite-field
arithmetic --- at least, for fields that are small enough to tabulate in main
memory.  For example, the reference implementation of the AES cryptosystem
\cite{bib:aes} multiplies in $\F_{2^8}$ using log and antilog tables, with a
modest memory requirement of half a kilobyte.

See also appendix \ref{appx:shanks} on page \pageref{appx:shanks} for an
efficient way to build large log tables (e.g. in a software implementation).

