%====================================================================
%
%
%---------------------------------------- this is a LaTeX-2e document
%====================================================================

%\documentclass[12pt]{amsart}
\documentclass[12pt]{article}
\parindent=0pt \parskip=8pt

\usepackage{verbatim}
\usepackage{fullpage}

\usepackage{amssymb,amsmath,amsthm}
\input{../tex/isomath}
\input{../tex/mathenv}

%\newcommand{\mod}{\mathrm{mod }}
\newcommand{\modp}{\,(\mathrm{mod } \,p)}
\newcommand{\veps}{\varepsilon}
\newcommand{\modfive}{\,(\mathrm{mod } \,5)}
\newcommand{\Fpx}{\F_p^\times}
\newcommand{\Fpd}{\F_{p^d}}

%--------------------------------------------------------------------
\begin{document}
\title{Computation in finite fields}
\author{John Kerl \\ Arizona State University and Avnet Design Services}
%\date{\today}
\date{January 11, 2004}

\maketitle

\begin{abstract}
Elementary techniques for computation in finite fields are presented, at a
level appropriate for an engineering or mathematical audience.  Additionally,
elementary Galois theory for finite fields is presented at a level appropriate
for undergraduate or beginning graduate students in mathematics.  For the
latter, illustrative properties of a novel \emph{logarithmic root chart} are
developed.
\end{abstract}

%% ----------------------------------------------------------------
%\newpage
\addcontentsline{toc}{section}{Contents}
\tableofcontents

%% ================================================================
\newpage

\section{Overview}

Finite fields are often given a brief treatment in algebra courses (at least at
Arizona State), 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.

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:berl},
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.

Whereas finite fields may be presented in the abstract, this paper will take
the opposite approach by first constructing systems which are finite and which
are fields, 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.

My intended audience is 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.)

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 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.)

%% ================================================================
\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}

%% ================================================================
\newpage
\section{The field $\F_p$}
\label{sec: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
\emph{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.

%% ----------------------------------------------------------------
\subsection{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.

%% ----------------------------------------------------------------
\subsection{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.

%% ----------------------------------------------------------------
\subsection{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.

%% ----------------------------------------------------------------
\subsection{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 \emph{mod}
operation.  The opposite operation is called \emph{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 ``extended GCD'', also known as the ``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.

%% ----------------------------------------------------------------
\subsection{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 \emph{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.

%% ----------------------------------------------------------------
\subsection{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.

%% ----------------------------------------------------------------
\subsection{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 \emph{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 \emph{discrete log} since it takes only integer
values.)

Now I can tabulate field elements and their logs, sorting by field element, to
obtain a \emph{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
\section{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 do 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.

%% ----------------------------------------------------------------
\subsection{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 \emph{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$.

%% ----------------------------------------------------------------
\subsection{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 \emph{subfield} of $F$, and that
$F$ is an \emph{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 \emph{monic}, i.e. with 1 for the leading coefficient\footnote{There are
technical distinctions between ``prime'' and ``irreducible'', which disappear
for PIDs.  I will nonetheless choose to reserve the term ``prime'' for integers
$p$ which don't factor any more than into $\pm p$ and $\pm 1$, and I will
reserve the term ``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 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.

%% ----------------------------------------------------------------
\subsection{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 \emph{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 \emph{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 section
\ref{sec:fp} on page \pageref{sec: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$.

%% ----------------------------------------------------------------
\subsection{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 cubic 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}.

%% ----------------------------------------------------------------
\subsection{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.)

%% ----------------------------------------------------------------
\subsection{Addition, subtraction and multiplication in $\Fpn$}

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
\emph{ring-and-reduce} method; the second is \emph{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.

%% ----------------------------------------------------------------
\subsection{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 \emph{period} of $r(x)$.  In
their tables, they call the period $e$.}.  If $u$ is primitive, for brevity I
say that $u$ is a \emph{generating root}.  Also, $r(x)$ in $\F_p[x]$ is said to
be a \emph{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 ``primitive'' and
``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.

%% ----------------------------------------------------------------
\subsection{Powers of $u$ and LFSRs}

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 \emph{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 discuss primitivity testing in greater detail in appendix
\ref{appx:prims_in_Fpx} on page \pageref{appx:prims_in_Fpx}.

%% ----------------------------------------------------------------
\subsection{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$.

%% ----------------------------------------------------------------
\subsection{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.

%% ----------------------------------------------------------------
\subsection{Third reciprocation method in $\Fpn$}

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.

%% ----------------------------------------------------------------
\subsection{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 \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).

%% ================================================================
\newpage
\section{The universal polynomial $x^{p^n}-x$}
\label{sec:univ_poly}

Now we know how to add, subtract, multiply and divide in $\Fpn$, and we have
the polynomial $x^{p^n}-x = 0$ of which all elements of $\Fpn$ are roots.  It's
time now to look at the \emph{universal polynomial} $x^{p^n}-x$.

The universal polynomial is really the key to the castle.  From here we'll get
all sorts of information about splitting fields, subfields, Galois structure,
etc.

%% ----------------------------------------------------------------
\subsection{Reducibility of the universal polynomial over $\F_p$}

The first theorem of interest is that $x^{p^n}-x$ is reducible in $\F_p[x]$,
and factors\footnote{Above we discussed how to find irreducibles.  Assuming we
know how to factor (in fact there are efficient factorization algorithms for
$\F_p[x]$, e.g. the Berlekamp algorithm \cite[Ch.~4.1]{bib:ln} and appendix
\ref{appx:berlekamp}), we know we can find monic irreducibles merely by
factoring.} into all the monic irreducibles of degree $d$ for all $d$ dividing
$n$.

For example, in section \ref{sec:find_irreds} on page \pageref{sec:find_irreds}
we listed out all the monic irreducibles for $p=2$, and $n$ up to 4.  What are
the divisors $d$ of 4?  Of course, 1, 2 and 4.  It is easy to see (you can
check by multiplying the factors back up again) that $x^{16}-x$ has the
following six factors in $\F_2[x]$:

\begin{tabular}{rccc}
	$d=1$: & $x$, & $x+1$ \\
	$d=2$: & $x^2+x+1$  \\
	$d=4$: & $x^4+x+1$, & $x^4+x^3+1$, & $x^4+x^3+x^2+x+1$ \\
\end{tabular}

%% ----------------------------------------------------------------
\subsection{$\Fpn$ as a splitting field}

Now, this factorization of $x^{p^n}-x$ is in $\F_p[x]$ so it as yet has nothing
to do with $\Fpn$.  The next key theorem is that $x^{p^n}-x$ splits\footnote{
More generally, a monic irreducible $f(x)$ of degree $n$ in $\F_p[x]$ factors
into $d$ terms each of degree $n/d$ in $\F_{p^d}[x]$ for all $d|n$.  For $d=n$,
we have $n$ terms of degree 1, i.e. a splitting into linear factors.} into
linear factors in $\Fpn[x]$, that is, $\Fpn$ is the \emph{splitting field} of
$x^{p^n}-x$.  (In fact, in a theoretical approach to finite fields, in
constrast to the computational approach taken in this paper, one often starts
with the universal polynomial and defines $\Fpn$ as its splitting field.)
Specifically, $x^{p^n}-x$ has no multiple roots, and the $p^n$ distinct roots
are precisely the $p^n$ distinct elements of $\Fpn$.

What does it really mean for $\Fpn$ to be a splitting field of a polynomial
with coefficients in $\F_p$, i.e. for $\Fpn$ to be an extension field of
$\F_p$?  Here is precisely where it matters that I kept $x$ and $u$ distinct in
section \ref{sec:adjoin_u} on page \pageref{sec:adjoin_u}.  Also the compact
notation comes in handy.

Here is an analogy with the reals:  The polynomial $x^2+1$ is irreducible over
$\R$, yet it splits into linear terms over $\C$, namely, $x^2+1 = (x+i)(x-i)$.
Also recall that sometimes when first proving that $\C$ is a field, we write
complex numbers $a+bi$ as ordered pairs $(a,b)$:  $a$ is the base part and $b$
is the extension part.  Likewise, numbers such as 0001, 0011, 1011 etc. are
elements of the extension field $\Fpn$, where the last digit is the base part
(in $\F_p$) and the others are the extension parts.

So $x^2+1$ has coefficients strictly in $\R$, but it takes $\C$ to get it
factored down to linear terms.  Going the other way, notice that $(x+i)(x-i)$
has complex numbers in it, but when we do the multiplication back to $x^2+1$,
the imaginary parts magically cancel out leaving only purely real coefficents.

Likewise for polynomials in $\F_p[x]$.  It can be proved that any irreducible
polynomial $f(x)$ of degree $n$ with coefficients in $\F_p$ splits into linear
terms as long as the coefficients are extended to be in $\Fpn$.  For example,
$x^2+x+1$ was above shown irreducible over $\F_2$.  Yet it's easy to verify by
FOILing that $(x+10)(x+11)$, using compact notation, or $(x+u)(x+u+1)$ using
the full notation,  is a factorization in $\F_{2^2}$.  Recall that anything
plus itself is zero in $\F_2$ and that $u^2=u+1$ in $\F_{2^2}$, using $x^2+x+1$
as the monic irreducible:
\begin{eqnarray*}
	(x+u)(x+u+1) &=& x^2 + ux + x + ux + u^2 + u\\
	&=& x^2 + x + u^2 + u\\
	&=& x^2 + x + u + 1 + u\\
	&=& x^2 + x + 1
\end{eqnarray*}

%% ----------------------------------------------------------------
\subsection{The root chart}
\label{sec:split_upoly}

The factorization of $x^{p^n}-x$ into irreducibles over $\F_p$ is unique, but
the details of the factorization into linear terms over $\Fpn$ clearly will
depend on our choice of $r(x)$ defining $\Fpn$ arithmetic.  (One of the field
theorems is that any two splitting fields of the same polynomial are
isomorphic, which together with the universal polynomial can be used to show
that any two finite fields of order $p^n$ are isomorphic.  Yet the arithmetic
isn't bodily identical.)

For $p=2$, $n=4$, we saw in section \ref{sec:find_irreds} on page
\pageref{sec:find_irreds} that there are three possibilities for $r(x)$.  Let
\begin{eqnarray*}
	r_1(x) &=& x^4+x+1 = 10011 \\
	r_2(x) &=& x^4+x^3+1 = 11001 \\
	r_3(x) &=& x^4+x^3+x^2+x+1 = 11111
\end{eqnarray*}
be the three monic irreducibles for $\F_{2^4}$.

I'll spare the details of the factorization algorithm (which in any case are
better left to a computer).  The factorization of $x^{16}-x$ into linears over
$\F_{2^4}$, using $r_1$, $r_2$ and $r_3$ to define the finite-field arithmetic,
is as follows.  Since I'm factoring into linear terms over a splitting field,
all the factors are of the form $(x-a)$ for some $a$.  To save space, I'll just
write the roots (the $a$'s).

Note:  The compact notation in the first column (elements of the polynomial
ring $\F_2[x]$) omits the variable $x$; the compact notation in subsequent
columns (elements of the field $\F_{2^4}$) omits the variable $u$.

\begin{tabular}{|cc|cccc|cccc|cccc|}
\multicolumn{14}{c}{Root chart for $x^{16}-x$ over $\F_{2^4}$} \\
\hline
\multicolumn{2}{|l}{Irr. factors} &
\multicolumn{4}{|l}{Roots mod $r_1=10011$} &
\multicolumn{4}{|l}{Roots mod $r_2=11001$} &
\multicolumn{4}{|l|}{Roots mod $r_3=11111$} \\
\multicolumn{2}{|l}{over $\F_2$} &
\multicolumn{4}{|l}{} &
\multicolumn{4}{|l}{} &
\multicolumn{4}{|l|}{} \\
%\hline
%\hline       &00010 &0000&    &    &    & 0000&    &    &    & 0000&    &    &     \\
%\hline       &00011 &0001&    &    &    & 0001&    &    &    & 0001&    &    &     \\
%\hline       &00111 &0110&0111&    &    & 1010&1011&    &    & 1100&1101&    &     \\
%\hline $r_1$:&10011 &0010&0011&0100&0101& 0110&0111&1100&1101& 0110&0111&1010&1011 \\
%\hline $r_2$:&11001 &1001&1011&1101&1110& 0010&0100&1001&1110& 0011&0101&1001&1110 \\
%\hline $r_3$:&11111 &1000&1010&1100&1111& 0011&0101&1000&1111& 0010&0100&1000&1111 \\
%\hline
\hline
\hline      &00010&0000&&&&0000&&&&0000&&&\\
\hline      &00011&0001&&&&0001&&&&0001&&&\\
\hline      &00111&0110&0111&&&1011&1010&&&1101&1100&&\\
\hline$r_1$:&10011&0010&0100&0011&0101&0111&1100&0110&1101&0111&1010&0110&1011\\
\hline$r_1$:&11001&1011&1001&1101&1110&0010&0100&1001&1110&0011&0101&1110&1001\\
\hline$r_1$:&11111&1000&1100&1111&1010&1000&1111&0011&0101&1111&1000&0010&0100\\
\hline
\end{tabular}

Also, in the first column where I write the monic irreducibles for degrees $d$
dividing 4, I've marked the $r_i$'s since these are the same three polynomials
that define $\F_{2^4}$ the arithmetic.  That is, we are factoring $r_i$ mod
$r_j$.  (The smaller-degree factors of $x^{p^n}-x$ have to do with subfields,
as we shall see below.)

Note:  This chart may be obtained in a top-down fashion by factoring the
universal polynomial $x^{p^n}-x$ over $\Fpn$, or it may be obtained in a
bottom-up fashion (with far less effort).  Both methods are described in
appendix \ref{appx:root_chart_how_to} on page \pageref{appx:root_chart_how_to}.

The root chart is chock-full of information, as the next several sections will
explore.

%% ================================================================
\newpage
\section{Basic Galois theory for $\Fpn$}
\label{sec:galois_theory}

\bigskip
\begin{center}
\emph{Eadem mutata resurgo (Though changed, I arise the same)} --- Jakob
Bernoulli
\end{center}
\bigskip

One of this paper's main purposes is to provide examples to assist in the study
of Galois theory.  Now, since (as we shall see) the Galois group of a finite
field is always cyclic, and since all extensions are Galois\footnote{ The
Galois group is cyclic, hence abelian, so all subgroups of the Galois group are
normal, so all the subfields are Galois over $\F_p$.  }, one does not obtain
the full panoply of behavior exhibited by algebraic number fields.  However,
finite fields are nice in part because we can write down all the elements of
the field (try that with an algebraic number field!).  Also, once you are
comfortable with computing in finite fields you'll be in a good position to
compute in algebraic number fields --- a lot of the same quotient-and-remainder
business over a polynomial ring comes into play.

%% ----------------------------------------------------------------
\subsection{Subfields}

For each $\Fpn$, there is a unique subfield $\Fpd$ for all $d \,|\, n$.  Why?
First, for the dimension $p^d$:  suppose you have a subfield of $\Fpn$.  By the
vector-space considerations as discussed in section \ref{sec:existence_of_Fpn},
the subfield is an extension field of its prime subfield $\F_p$ and so its size
is necessarily a $p$-power, $p^d$, for some $1 \le d \le n$.  So, we can call
it an $\Fpd$.  For the same reason, since $\Fpn$ is an extension field of
$\Fpd$, $p^n$ is a power of $p^d$, from which $d|n$.

(As well, if $\Fpd$ is a subfield of $\Fpn$, the multiplicative group of the
former must be a subgroup of the multiplicative group of the latter, so $p^d-1$
must divide $p^n-1$.  It's easy to see, using integer division, that $d|n$ if
and only if $p^d-1 \,|\, p^n-1$.)

So, \emph{if} there is a subfield of $\Fpn$, then it is an $\Fpd$ for $d|n$.
As above, the prime subfield $\F_p$ always exists.  The fact that a unique
$\Fpd$ does in fact exist as a subfield of $\Fpn$ for all the remaining $d|n$
is proved using Galois theory\footnote{As will be seen below, $\Gal(\Fpn/\F_p)
= \langle \rho \rangle$ with $|\rho|=n$, where $\rho$ is the $p$-power map.
From group theory, a cyclic group of order $n$ has a unique subgroup of order
$d$ for all $d|n$.  By the Galois correspondence, this means there is a unique
$\Fpd$ for all $d|n$.}.

For example, for $\F_{2^6}$ we expect subfields $\F_2$, $\F_{2^2}$ and
$\F_{2^3}$, along with $\F_{2^6}$ itself.  These subfields are easy to
construct.  Recall that any field consists of 0 along with the field's
multiplicative group, and that the multiplicative group of any finite field is
cyclic.  Any subfield of a finite field must contain 0, and the multiplicative
group of the subfield must be a subgroup of the multiplicative group of the
larger field.  The former will have $p^d-1$ elements; the latter will have
$p^n-1$ elements, and as above, $p^d-1\,|\,p^n-1$ when $d|n$.

Suppose we have a cyclic group of order $ab$ with generator $g$.  Then there is
a subgroup of order $b$ generated by $g^a$.  E.g. $(\Z_6,\oplus)$ has order 6
and generator 1; elements are 0, 1, 2, 3, 4 and 5.  There is an order-3
subgroup generated by 2, with elements 0, 2 and 4.

Back to finite fields, by the same token, if $\Fpn^\times$ has generator $g$,
then $\F_{p^d}^\times$ has generator $g^{(p^n-1)/(p^d-1)}$.  For example, let
$g$ be a generator of $\F_{2^6}^\times$.  To construct $\F_{2^3}$ as a subfield
of $\F_{2^6}$, let $g$ be a generator of $\F_{2^6}^\times$.  Then $\F_{2^3}$ is
the 0 element along with the 7 distinct powers of $g^{63/7} = g^9$.  (For now,
I'm saying that this $\F_{2^3}$ is the specified subset of $\F_{2^6}$, but I'm
not yet saying which elements of this $\F_{2^3}$ map isomorphically to which
elements of a standard $\F_{2^3}$, where by ``standard'' I mean a field defined
by a monic irreducible cubic in $\F_2[x]$.  More on that below.)

In the root chart, we can see subfields.  Look at the elements 0 and 1, along
with the roots of $x^2+x+1$.  Mod $x^4+x+1$, these four elements are $0$, $1$,
$u^2+u$ and $u^2+u+1$.  Using addition, subtraction, multiplication and
division you can easily see that these four elements satisfy all the field
axioms, and so must be a field.

With reference to the antilogarithm table in section
\ref{sec:fpn_recip_4_and_logs} on page \pageref{sec:fpn_recip_4_and_logs}, note
that $u^2+u$, $u^2+u+1$ and 1 have logarithms 5, 10 and 15, respectively with
respect to the generator $u$, i.e.  the elements of the copy of $\F_{2^2}$
inside $\F_{2^4}$ are 0, $u^5$, $u^{10}$ and $u^{15}=1$.  I refer to this as
the ``subfield/log criterion'':  elements of a subfield may be determined by
their logarithms.  Specifically, an element of $\F_{p^n}$ is also an element of
an $\F_{p^d}$, where $d|n$, if and only if it is zero or its logarithm is a
multiple of $(p^n-1)/(p^d-1)$.

On the other hand, earlier in this paper we saw one (in fact, the only) monic
irreducible for $p=2$, $n=2$:  namely, $x^2+x+1$.  (The root chart bears this
out since there is only one quadratic factor for $x^{16}-x$.)  This leads to an
$\F_{2^2}$ with elements $0$, $1$, $v$, $v+1$ where I use $v$ instead of $u$ to
emphasize that these are different equivalence classes.  Since these two copies
of $\F_{2^2}$ are fields and have the same order, they must be isomorphic.
Below we'll construct an explicit isomorphism between the two.  More
importantly, \emph{this} is what people mean when they say things like
``$\F_{2^2} \subset \F_{2^4}$'':  They do \emph{not} mean that the $x^2+x+1$
field is a subfield of the $x^4+x+1$ subfield with $v$ mapping to $u$ (it
clearly is not).  Rather they mean that the $\F_{2^2}$ field of $x^2+x+1$ may
be \emph{embedded} (i.e. mapped with a 1-1 homomorphism) into the $x^4+x+1$
field $\F_{2^4}$.

%% ----------------------------------------------------------------
\subsection{Frobenius automorphisms}

It is easy to show that the map which raises elements of $\Fpn$ to the $p$th
power is an automorphism on $\Fpn$, called the \emph{Frobenius automorphism}.
For the additive homomorphism property, use the ``freshman's dream'' for fields
of characteristic $p$:  $(a+b)^p = (a^p+b^p)$.  (In the binomial expansion, ${p
\choose i}$ is 0 mod $p$ except for $i=0,p$ in which case it is 1.) For the
multiplicative homomorphism property, $(ab)^p=a^pb^p$.  For injectivity, $a^p
=b^p \implies a^p-b^p = 0 = (a-b)^p \implies a=b$ since fields have no zero
divisors.  For surjectivity, the preimage of any $a$ under the Frobenius map is
$a^{p^{n-1}}$.

Recall from section \ref{sec:xpx} on page \pageref{sec:xpx} that we have $a^p =
a$ for all elements of $\F_p$.  That is, the automorphism $\rho$ which takes
$p$th powers is the identity on the prime subfield $\F_p$ of $\Fpn$.

%% ----------------------------------------------------------------
\subsection{Galois group and Frobenius orbits}

Look at the action of $\rho$ on an element $a$ of $\Fpn$: $\rho(a) = a^p$;
$\rho^2(a) = \rho(\rho(a)) = (a^p)^p = a^{p^2}$; etc. up to $\rho^{n-1}(a) =
a^{p^{n-1}}$.  But then $\rho^{n}(a) = a^{p^{n}} = a$ so $\rho^n = \rho^0 =
\iota$, the identity map.  This is how we see\footnote{That the $\rho^i$'s
account for \emph{all} automorphisms on $\Fpn$ is proved using Galois theory:
the $n$ distinct powers of $\rho$ are enough to fill the Galois group since
$[\Fpn : \F_p] = n$.} that the Galois group is in fact cyclic of order $n$,
generated by the $p$-power map $\rho$.  That is:

$$
\Gal(\Fpn/\F_p) = \langle \rho \rangle; \, |\rho| = n
$$

Given $a$ in $\Fpn$, the $\rho^i(a)$'s are the \emph{orbit} of $a$ under the
\emph{action} of the automorphism group.  There is an obvious equivalence
relation on the field for any elements which are $p^i$ powers of one another.
These equivalence classes partition the field, as is clear from the root chart.

Also we saw that $a^{p^n}=a$ for all elements of $\Fpn$, so as well $a^{p^d}=a$
for all elements of $\Fpd$.  This means that when we look at the Galois
correspondence below, when we view $\Fpd$ as a subfield of $\Fpn$ we will have
$\rho^d$ being an identity on the base field $\Fpd$ and we will expect

$$
\Gal(\Fpn/\Fpd) = \langle \rho^d \rangle; \, |\rho^d| = n/d
$$

which will have group order $n/d$.  E.g. the Galois group for $\F_{2^6}$ over
$\F_{2^2}$ will consist of the three automorphisms $a \mapsto a$, $a \mapsto
a^4$ and $a \mapsto a^{16}$.

%% ----------------------------------------------------------------
\subsection{Characteristic and minimal polynomials}

The \emph{characteristic polynomial} for an element $a$ of a field $F$ with
respect to a base field $K$ is defined to be $$ \prod_{\sigma \in \Gal(F/K)} x
- \sigma(a) $$ which is clearly monic but not necessarily irreducible.  For
$\Fpn$ over $\Fp$, this becomes $$ \prod_{i=0}^{n-1} x - a^{p^i} $$ For our
example $\F_{2^4}$ over $\F_2$, this is $$ (x-a)(x-a^2)(x-a^4)(x-a^8) $$

The \emph{minimal polynomial} of $a$ is the unique monic irreducible polynomial
having $a$ as a root.  It is shown in field theory \cite[Ch.~14.2]{bib:df} that
the characteristic polynomial is a power of the minimal polynomial, and in
particular
$$
	C_a(x) = M_a(x)^{n/d}
$$
where $d$ is the degree of the smallest extension field over the base
containing $a$, which is the same as the degree of $a$'s minimal polynomial.
Since $n/d$ is an integer, $d$ always divides $n$.  That is, the minimal
polynomial is like the characteristic polynomial, but we only include
\emph{distinct} $\sigma(a)$'s.

In the root chart, this behavior is very clear:

\begin{itemize}

\item For the elements $0$, $1$ of $\F_{2^4}$ which are also elements of the
base field $\F_2$, $a^2=a$ so the product $$ (x-a)(x-a^2)(x-a^4)(x-a^8) $$
reduces to $$ (x-a)^4 $$ where the minimal polynomial is $$ (x-a) $$ which is
of degree one (the $4$ applications of the Frobenius map wrap around four
times), corresponding to the fact that 0 and 1 are elements of $\F_2$.

\item For the elements $110$, $111$ of $\F_{2^4}$ which are also elements of
the intermediate field $\F_{2^2}$, $a^4=a$ so the product $$
(x-a)(x-a^2)(x-a^4)(x-a^8) $$ reduces to $$ (x-a)^2(x-a^2)^2 $$ where the
minimal polynomial is $$ (x-a)(x-a^2) $$ which is of degree two (the $4$
applications of the Frobenius map wrap around twice), corresponding to the fact
that 110 and 111 are elements of $\F_{2^2}$ but not elements of $\F_2$.

\item For the remaining elements of $\F_{2^4}$, the $a^{p^i}$'s are all
distinct so the product $$ (x-a)(x-a^2)(x-a^4)(x-a^8) $$ does not reduce and
the minimal polynomial is the same as the characteristic polynomial, which is
of degree four (the $4$ applications of the Frobenius map do not wrap around),
corresponding to the fact that these elements of $\F_{2^4}$ are not elements of
any smaller field.

\end{itemize}

%% ----------------------------------------------------------------
\subsection{Conjugates}

Two elements of the field are said to be \emph{conjugates} if they are roots of
the same minimal polynomial, and clearly this also makes an equivalence
relation on the elements of the field.  From the root chart we see a clear
example that conjugacy classes are the same as Frobenius orbits.  For example,
the polynomial $r_1=x^4+x+1$, using $r_1$ arithmetic, has roots $u$, $u^2$,
$u^4 = u+1$, $u^8 = u^2+1$.

%% ----------------------------------------------------------------
\subsection{Orders and logs}

In section \ref{sec:split_upoly} I showed the root chart for $\F_{2^4}$.  Here
is the same chart, but instead of field elements I show their logarithms.  The
polynomials $r_1(x)=x^4+x+1$ and $r_2(x)=x^4+x^3+1$ are primitive, so
$g_1=g_2=u=10$ can be used as a generator; $r_3(x)=x^4+x^3+x^2+x+1$ is
imprimitive and I've selected $g_3=u+1=11$ as a generator.

\begin{tabular}{|cc||cccc|cccc|cccc|c|}
\multicolumn{15}{c}{Logarithmic root chart for $x^{16}-x$ over $\F_{2^4}$} \\
\hline
\multicolumn{2}{|l}{Irr. factors} &
\multicolumn{4}{|l}{Roots mod } &
\multicolumn{4}{|l}{Roots mod } &
\multicolumn{4}{|l|}{Roots mod } &
\multicolumn{1}{l|}{Order} \\
\multicolumn{2}{|l}{over $\F_2$} &
\multicolumn{4}{|l}{$r_1=10011$} &
\multicolumn{4}{|l}{$r_2=11001$} &
\multicolumn{4}{|l|}{$r_3=11111$} &
\multicolumn{1}{l|}{} \\
\multicolumn{2}{|l}{} &
\multicolumn{4}{|l}{$g_1=0010$} &
\multicolumn{4}{|l}{$g_2=0010$} &
\multicolumn{4}{|l|}{$g_3=0011$} &
\multicolumn{1}{l|}{} \\
%\hline
%\hline       &00010 &N/A &   &   &    &N/A&  &   &    &N/A&  &   &   & N/A\\
%\hline       &00011 & 15 &   &   &    &15 &  &   &    &15 &  &   &   &  1 \\
%\hline
%\hline       &00111 &  5 &10 &   &    &10 &5 &   &    &10 &5 &   &   &  3 \\
%\hline
%\hline $r_1$:&10011 &  1 & 4 & 2 & 8  &13 &7 &14 &11  &13 &7 &14 &11 & 15 \\
%\hline $r_2$:&11001 & 14 & 7 &13 &11  & 1 &2 & 4 & 8  & 1 &2 & 8 & 4 & 15 \\
%\hline $r_3$:&11111 &  3 & 9 & 6 &12  &12 &9 & 3 & 6  &12 &9 & 6 & 3 &  5 \\
\hline
\hline        &00010 &N/A&&  &  &      N/A& & &  &      N/A& & &   &N/A\\
\hline        &00011 &0&  &  &  &      0&  &  &  &      0&  &  & 1 &   \\
\hline        &00111 &5&10&  &  &      5&10&  &  &      5&10&  & 3 &   \\
\hline $r_1$: &10011 &1& 2& 4& 8&      7&14&13&11&      7&14&13&11 & 15\\
\hline $r_2$: &11001 &7&14&13&11&      1& 2& 4& 8&      1& 2& 4& 8 & 15\\
\hline $r_3$: &11111 &3& 6&12& 9&      3& 6&12& 9&      3& 6&12& 9 &  5\\
\hline
\end{tabular}

Here the subfield/log criterion is clear:  1, which is in $\F_2$, is
$g_i^{15}$; the other two non-zero elements of $\F_{2^2}$ are $g_i^{5}$ and
$g_i^{10}$.  All conjugates have a log which is some power of two times the
logs of the other conjugates.

Also, as Lidl and Niederreiter \cite{bib:ln} point out, roots of $r_1$ and
$r_2$ (which are primitive) have full order, i.e. 15, regardless of which $r_j$
is used for the splitting arithmetic; roots of $r_3$ (which is imprimitive)
have smaller order regardless of $r_j$.

%% ----------------------------------------------------------------
\subsection{Two definitions of ``generator''}
\label{sec:generator_two_defs}

In this paper, when I refer to a generator of $\F_{p^n}$, I refer to an element
that ``generates'' the multiplicative group $\F_{p^n}^\times$, i.e. an element
which can produce all the other non-zero elements only using multiplication.
As well, I call such an element ``primitive''.

I should come clean and admit that this terminology is non-standard (although
multiple authors use the term ``primitive polynomial'' in the sense I do).  In
field theory, it is common to define the field ``generated'' by an element
$\alpha$ to be the smallest field containing $\alpha$, and to say that $\alpha$
is a ``primitive'' element of a field $F$ if it generates $F$ in this sense.
This simply means that $\alpha$ is in $F$, but not in any proper subfield.

That is, when one talks of a field generated by $\alpha$, one refers to all the
elements which can be obtained from $\alpha$ using multiplication \emph{and}
addition.  Clearly, all you need to generate an $\F_{p^n}$ is any element with
a degree-$n$ minimal polynomial.  Then, multiplication will give you $n$
distinct powers $1, \alpha, \alpha^2, \ldots, \alpha^{n-1}$, and then addition
will give you all the remaining $p^n$ elements.

In the root chart above, it is clear that there are 12 elements which are field
generators in this sense:  roots of the three quartics 10011, 11001 and 11111.
However, only 8 of those 12 generate the multiplicative group using only
multiplication.

My choice of using the terms ``primitive'' and ``generator'' in the
group-theoretic sense rather than in the field-theoretic sense is because
logarithms are key throughout this paper, and in order to define logarithms
one needs a generator of the multiplicative group.

%% ----------------------------------------------------------------
\subsection{The irreducible-count and primitive-count formulae}
\label{sec:count_irrs_and_prims}

Above I noted that there are formulae for the number of monic irreducibles of a
given degree in $\F_p[x]$, and for the number of those which are also primitive.
The root chart makes the derivations of
those formulae obvious.

For the irreducible-count formula \cite[Ch.~14.3]{bib:df}: When we factor
$x^{p^n}-x$ in $\F_p[x]$, the result is all the monic irreducibles in $\F_p[x]$
of degree $d$ for all $d$ dividing $n$.  Equating degrees, we have that $$ p^n
= \sum_{d|n} d I(d) $$ where $I(d)$ is the number of monic irreducibles of
degree $d$.  E.g. in the root chart for $\F_{2^4}$, $I(1)=2$ (2 factors of
egree 1), $I(2)=1$ (1 factor of degree 2) and $I(4)=3$ (3 factors of degree
4), and $2 \cdot 1 + 1 \cdot 2 + 3 \cdot 4 = 16$.  Take as given the M\"obius
inversion formula from elementary number theory, and recall that $\mu(m)$, for
integer $m$, is 0 if $m$ is not squarefree, $+1$ if $m$ has an even number of
distinct prime factors, or $-1$ if $m$ has an odd number of distinct prime
factors.  Note that we have a function of $n$ (namely, $p^n$) expressed in
terms of a sum over divisors of $d$ of $n$ (namely, $dI(d)$) so we may invert
$d$ and $n$ to write $$ nI(n) = \sum_{d|n} \mu(d) p^{n/d} $$ from which $$ I(n)
= \frac{1}{n} \sum_{d|n} \mu(d) p^{n/d} $$ This function always has positive
value, which then guarantees the existence of at least one monic irreducible
for any prime $p$ and positive integer $n$.

For the primitive-count formula \cite{bib:murphy}:  The multiplicative group of
$\F_{p^n}$ is cyclic with order $p^n-1$.  From elementary number theory we know
that this cyclic group is generated by elements whose logs are relatively prime
to $p^n-1$.  The number of such logs has a name:  the Euler \emph{totient
function}, or \emph{phi function}.  Thus there are $\phi(p^n-1)$ generators of
the multiplicative group of $\F_{p^n}$.  Since they generate all of
$\F_{p^n}^\times$, they can't be elements of a proper subfield so their minimal
polynomials all have degree $n$.  (In the logarithmic root chart for
$\F_{2^4}$, the polynomials $10011$ and $11001$ are primitive since their roots
have full order 15; $11111$ is imprimitive since its roots only have order 5.)
Also, if one of the roots of a polynomial is primitive, all of them
are\footnote{Given $a \in \F_{p^n}$, an arbitrary conjugate is $a^{p^i}$ for
some integer $i$.  If $a^k=1$ then $(a^{p^i})^k = a^{kp^i} = (a^k)^{p^i}= 1$.
If $a^k \ne 1$ then likewise $ (a^{p^i})^k= (a^k)^{p^i} $, and since raising to
the $p^i$ power is an automorphism on $\F_{p^n}$, a non-1 element is not sent
to 1.  Therefore conjugates have the same multiplicative order.}.  So the
$\phi(p^n-1)$ generators are accounted for by their $\phi(p^n-1)/n$ minimal
polynomials, each of which is primitive.  Like the primitive-count function,
this irreducible-count function always takes a positive value, guaranteeing the
existence of at least one primitive monic irreducible for any prime $p$ and
positive integer $n$.

%% ----------------------------------------------------------------
\subsection{The Galois correspondence}
\label{sec:f24_gal_corresp}

We saw that the Galois group of $\Fpn$ is cyclic of order $n$, generated by the
Frobenius automorphism $\rho$.  Also we just took a look at subfields.  It is
now natural to ask more about the Galois correspondence for finite fields.

From the above discussions about subfields and Galois groups we have the
following:

\setlength{\unitlength}{1.0in}
\begin{picture}(6,2.5)

\put(0.50,2.25){$\F_{2^4} = \F_2(\gamma), \, \gamma^4 + \gamma + 1 = 0
	= \F_2(\alpha)(\beta)$}
\put(0.60,1.40){\line(0,1){.75}}
\put(0.50,1.25){$\F_{2^2} = \F_2(\alpha), \, \alpha^2 + \alpha + 1 = 0$}
\put(0.60,0.40){\line(0,1){.75}}
\put(0.50,0.25){$\F_2$}

\put(5.30,2.25){$\langle \rho^4=\iota \rangle$}
\put(5.60,1.40){\line(0,1){.75}}
\put(5.50,1.25){$\langle \rho^2 \rangle$}
\put(5.60,0.40){\line(0,1){.75}}
\put(5.50,0.25){$\langle \rho \rangle$}

\end{picture}

As mentioned above:

\begin{itemize}

\item The $p$-power map, $\rho$, is the identity on $\F_2$.  The four maps
	$\rho$, $\rho^2$, $\rho^4$ and $\rho^{16}=\iota$ are distinct
	automorphisms on $\F_{2^4}$, forming the Galois group of $\F_{2^4}$
	over $\F_2$.

\item The $p$-power map, $\rho$, is the identity on $\F_2$.  The two maps
	$\rho$ and $\rho^2=\iota$ are distinct automorphisms on $\F_{2^2}$,
	forming the Galois group of $\F_{2^2}$ over $\F_2$.

\item The $p^2$-power map, $\rho^2$, is the identity on $\F_{2^2}$.  The two
	maps $\rho^2$ and $\rho^4=\iota$ are distinct automorphisms on
	$\F_{2^2}$, forming the Galois group of $\F_{2^4}$ over $\F_{2^2}$.

\end{itemize}

%% ----------------------------------------------------------------
\subsection{Field isomorphisms}

Above we saw that in an automorphism, i.e. an isomorphism from a finite field
to itself, roots of a given minimal polynomial map to other roots of the same
minimal polynomial.  Also, that mapping was $\alpha \mapsto \alpha^{p^i}$ for
some $0 \le i < n$.

Also, above several times I mentioned that finite fields of a given order are
isomorphic.  But, what is the nature of that isomorphism?  It is one thing to
prove the existence of something, but it is another thing to produce that item.
It can be shown that these isomorphisms can be explicitly constructed as
follows:

\begin{itemize}

\item A field homomorphism must be a group homomorphism on the additive group.
	In particular, 0 maps to 0.

\item A field homomorphism must be a group homomorphism on the multiplicative
	group as well, and the multiplicative group is cyclic.  Recall that for
	a homomorphism $\phi$ between cyclic groups, it suffices to specify the
	image of a generator $g$.  By the homomomorphism property, for any
	$a = g^k$ in the first field, $\phi(a) = \phi(g^k) = \phi(g)^k$ in the
	second field.  (Not all the group homomorphisms will be field
	homomorphisms, of course --- they all preserve multiplication, but
	they won't necessarily all preserve addition as well.)

\item Since the multiplicative groups of both fields are cyclic, there is at
	least one primitive element in the first field.  Call that primitive
	element $g_1$.  Also it is clear that primitive elements will have a
	minimal polynomial of degree $n$, not less, i.e. the minimal polynomial
	for a primitive element is the same as its characteristic polynomial.
	This is because a primitive element of the multiplicative group cannot
	be an element of a multiplicative subgroup, so such an element can't be
	belong to a subfield either.

\item Find the minimal polynomial of the chosen generator in the first field.

\item Map $g_1$ to one of the $n$ roots of that same minimal polynomial in the
	second field.  It can be shown that these roots are all primitive
	elements in the second field.  Call your choice $g_2$.

\item Zero maps to zero.  All remaining elements $a_1$ in the first field
	map to $a_2$ in the second field by
$$
	a_2 = g_2^{log_{g_1}(a_1)}
$$

\end{itemize}

For example, in the root chart, we can construct an isomorphism between the
$x^4+x+1$ field and the $x^4+x^3+1$ field.  Consult the log tables in appendix
\ref{appx:Fp_log_tables} on page \pageref{appx:Fp_log_tables} to find a
generator for the $x^4+x+1$ field, namely, $0010$.  Its minimal polynomial is
in the left-hand column, namely, $x^4+x+1$.  In the $x^4+x^3+1$ field,
$x^4+x+1$ has roots 0110, 0111, 1100 and 1101 so there are four possible
isomorphisms.  I'll arbitrarily choose the first.  Remember that 0 maps to 0,
and consult the log tables in appendix \ref{appx:Fp_log_tables} on page
\pageref{appx:Fp_log_tables} to write down the following:

\begin{tabular}{|r|r|r|}
\multicolumn{1}{c}{} &
\multicolumn{1}{c}{$x^4+x+1$:} &
\multicolumn{1}{c}{$x^4+x^3+1$:} \\
\hline $k$ & $g^k$ & $\phi(g)^k$ \\
\hline   1 & 0010 & 0110 \\
\hline   2 & 0100 & 1101 \\
\hline   3 & 1000 & 0101 \\
\hline   4 & 0011 & 0111 \\
\hline   5 & 0110 & 1011 \\
\hline   6 & 1100 & 1000 \\
\hline   7 & 1011 & 0010 \\
\hline   8 & 0101 & 1100 \\
\hline   9 & 1010 & 0011 \\
\hline  10 & 0111 & 1010 \\
\hline  11 & 1110 & 1110 \\
\hline  12 & 1111 & 1111 \\
\hline  13 & 1101 & 1001 \\
\hline  14 & 1001 & 0100 \\
\hline  15 & 0001 & 0001 \\
\hline N/A & 0000 & 0000 \\
\hline
\end{tabular}

%% ----------------------------------------------------------------
\subsection{Embeddings and unembeddings}
\label{sec:embed}

The above isomorphism works as well for embedding a smaller field in a larger
one.  Here, we want to see not only that an $\F_{p^d}$ is a subset of an
$\F_{p^n}$, where $d|n$, but we also want to see which element of the former
maps to which element of the latter, in a way that preserves addition and
multiplication.  Likewise, given an $\F_{p^d}$ embedded inside an $\F_{p^n}$,
it would be nice to map those elements back to a standard $\F_{p^d}$, i.e. an
$\F_{p^d}$ defined by a degree-$d$ monic irreducible in $\F_p[x]$.

The technique is as follows.

\begin{itemize}

\item Find the minimal polynomial of an arbitrarily chosen generator $g_s$ in
	the smaller field, the standard $\F_{p^d}$.  This will be a
	degree-$d$ monic irreducible in $\F_p[x]$.

\item Factor the minimal polynomial in the larger field.
	(To do this, either construct or consult a root chart, e.g. appendix
	\ref{appx:root_chart_how_to}, or use a factorization algorithm, e.g.
	appendix \ref{appx:berlekamp}.) Select one of the roots; call your
	choice $g_l$.  Note that this is not a generator of all of $\F_{p^n}$,
	but rather only a generator of the subfield $\F_{p^d}$ inside
	$\F_{p^n}$.

\item To embed the smaller $\F_{p^d}$ into the larger $\F_{p^n}$,
	zero maps to zero and all remaining elements $a_s$ in the smaller
	field map to $a_l$ in the second field by
	$$ a_l = g_l^{log_{g_s}(a_s)} $$

\item To unembed the copy of $\F_{p^d}$ contained in the larger field
	$\F_{p^n}$, to a standard $\F_{p^d}$,
	zero maps to zero and the remaining elements $a_l$ in the larger
	field map to $a_s$ in the second field by
	$$ a_s = g_s^{log_{g_l}(a_l)} $$
	Note that this log will only be defined for those element of $\F_{p^n}$
	which are actually elements of $\F_{p^d}$:  this is another instance of
	the subfield/log criterion.

\end{itemize}

%(In fact, the universal polynomial $x^{2^2}-x$ factors over $\F_2$ as
%$(x)(x+1)(x^2+x+1)$, and splits over $\F_{2^2}$ as $(x-0)(x-1)(x-u) (x-u-1)$.)

Let's explicitly construct an isomorphism between $\F_{2^2}$ as defined by
$x^2+x+1$ and $\F_{2^2}$ as a subfield of $\F_{2^4}$ with $x^4+x+1$.  We know
that $g_s=u$ is a generator of the former, with minimal polynomial $x^2+x+1$.
From the root chart, we know that $x^2+x+1$ has roots $v^2+v$ and $v^2+v+1$ in
$\F_{2^4}$.  Select $g_l = v^2+v$.  Then:

\begin{tabular}{|r|r|r|}
\multicolumn{1}{c}{} &
\multicolumn{1}{c}{$x^2+x+1$:} &
\multicolumn{1}{c}{$x^4+x+1$ subfield:} \\
\hline $k$ & $g_s^k$ & $g_l^k$ \\
\hline N/A &  00 &        0000 \\
\hline   1 &  10 &        0110 \\
\hline   2 &  11 &        0111 \\
\hline   3 &  01 &        0001 \\
\hline
\end{tabular}

%% ----------------------------------------------------------------
\subsection{Composite fields}
\label{sec:composita}

Using this technique it is easy to compute composites of finite fields.  Given
two fields of degree $n$ and $m$, let $c$ be the least common multiple of $n$
and $m$.  Use the above formula to map elements of $\F_{p^n}$ into $\F_{p^c}$,
and elements of $\F_{p^m}$ into $\F_{p^c}$.  Any irreducible degree-$c$
polynomial in $\F_p[x]$ may be used to define the $\F_{p^c}$ arithmetic.

%% ----------------------------------------------------------------
\subsection{Algebraic closure of $\F_p$}

Above I used the example of $x^2+1$ in $\R[x]$.  In this case, $\C$ is the
splitting field for $x^2+1$, that is, $\C$ splits this \emph{particular}
polynomial.  But moreover, $\C$ is the \emph{algebraic closure} of $\R[x]$,
i.e. $\C$ splits \emph{all} polynomials in $\R[x]$.  Furthermore, any
polynomial in $\C[x]$ splits in $\C[x]$.

For finite fields, the situation is a little different:  $\Fpn$ is the
splitting field for any particular irreducible degree-$n$ polynomial in
$\F_p[x]$ (in fact, for \emph{all} degree-$n$ irreducibles), but $\Fpn$ fails
to split higher-degree polynomials with coefficients in $\F_p$.  Furthermore,
$\Fpn$ does not split all degree-$n$ polynomials with coefficients in the
extension field $\Fpn$.  It can be shown, in fact \cite[Ch.~14.3]{bib:df}, that
no finite field is algebraically closed, and that the algebraic closure of
$\F_p$, written $\overline{\F_p}$, is the infinite field which is the union of
$\Fpn$ for all integer $n$.

What does it mean to take such a union?  This is the kind of thing we did in
section \ref{sec:embed}, where we embedded a smaller field in a larger one.
Computation in $\overline{\F_p}$ requires liberal amounts of these kinds of
embeddings.

%% ================================================================
\section{Multiple extensions}

Up to now in this document we've looked at single extensions, i.e. an $\F_{p^n}
= \F_p(\alpha)$ is an extension field of $\F_p$ when $\alpha$ is a root of some
degree-$n$ monic irreducible polynomial in $\F_p[x]$.  Here I want to consider
multiple extensions: for example, let $\alpha$ again be a root of some
degree-$n$ monic irreducible polynomial in $\F_p[x]$, and then let $\beta$ be a
root of some degree-$m$ monic irreducible polynomial in $\F_p(\alpha)[y]$.  The
result is an $\F_{p^{nm}}$ which may be written as $\F_p(\alpha)(\beta)$.

The terms and ``single extension'' and ``multiple extension'' are somewhat
non-standard.  In field theory, it is shown that for so-called \emph{perfect
fields}, which includes all the finite fields, any multiple extension
$F(\alpha)(\beta)$ is ``simple'' if it can be written as $F(\gamma)$ for some
$\gamma$.  For finite fields, this is always the case --- we \emph{can} write
all extensions thus.  However, in this section I want to consider the case when
we \emph{choose} not to do so.  Why?  Principally, to test our understanding of
Galois theory.  In particular, I want to show how to compute in a multiple
extension, and to show how elements of an $\F_p(\gamma)$ line up with their
counterparts in an $\F_p(\alpha)(\beta)$.

%% ----------------------------------------------------------------
\subsection{Minimal polynomials over intermediate fields}

Of course, we can think of $\F_{2^2}$ as an extension of $\F_2$, all by itself.
This $\F_{2^2}$ is $\F_2$ adjoin $\alpha$ where $\alpha$ is a root of
$x^2+x=1$.  (Up to now I've been using $u$ for the extension variable, but now
that I need more than one I'll switch over to $\alpha$, $\beta$ and $\gamma$
for this section and the next.) This is a quadratic extension whose elements
are linear combinations of $1$ and $\alpha$ with coefficients in the base field
$\F_2$, i.e. elements are $0,1,\alpha,\alpha+1$.  As above, the Galois group of
this extension is $\{\iota, \rho\}$ and $a^2=a$ for all $a$ in the base field
$\F_2$.  The minimal polynomial of $\alpha$ is $$(x-\alpha)(x-\alpha^2) =
(x-\alpha)(x-\alpha-1) = x^2+x+1$$ using $\alpha^2+\alpha+1$ arithmetic.

Also we can think of $\F_{2^4}$ as an extension of $\F_2$:  this $\F_{2^4}$ is
$\F_2$ adjoin $\gamma$ where $\gamma$ is a root of $x^4+x+1$.  This is a
quartic extension whose elements are linear combinations of $1$, $\gamma$,
$\gamma^2$ and $\gamma^3$ with coefficients in the base field $\F_2$.  The
Galois group of this extension is $\{\iota, \rho, \rho^2, \rho^3\}$, and
$a^2=a$ for all elements $a$ of the base field.  The minimal polynomial of
$\gamma$ is $$ (x-\gamma) (x-\gamma^2) (x-\gamma^4) (x-\gamma^8) =(x-\gamma)
(x-\gamma^2) (x-\gamma-1) (x-\gamma^2-1) = x^4+x+1$$ using $\gamma^4+\gamma+1$
arithmetic.

Third, we've seen how $\F_{2^2}$ sits as a subfield of $\F_{2^4}$: this
$\F_{2^2}$ is $\{0,1,\gamma^2+\gamma,\gamma^2+\gamma+1\}$ as above (when
$\gamma$ was called $u$).

Now, how do we see $\F_{2^4}$ as an extension field not of $\F_2$ but rather of
$\F_{2^2}$?  If $\F_{2^2} = \F_2(\alpha)$, then we should be able to write
$\F_{2^4}$ as $\F_2(\alpha)(\beta)$ for some $\beta$.  This will be a quadratic
extension of $\F_2(\alpha)$ so elements of this $\F_{2^4}$ will be linear
combinations of $1$ and $\beta$ with coefficients in $\F_2(\alpha)$.

We lack the minimal polynomial of $\beta$.  We need this to do arithmetic in
$\F_2(\alpha)(\beta)$:  otherwise we can't simplify powers of $\beta$, in the
way that $\alpha^2+\alpha+1=0$ allows us to simplify powers of $\alpha$.  That
is, we need $M_\beta(y)$ in order to write $$ \F_{2^4} = \F_2(\alpha)[y] /
\langle M_\beta(y) \rangle $$

The Galois group of the extension $\F_{2^4}/\F_{2^2}$ is $\langle \rho^2
\rangle = \{\iota, \rho^2\}$, since $y^4=y$ on the base field $\F_{2^2}$.

We need to select a generator $\beta$ of $\F_{2^4}$.  Since $x^4+x+1$ is a
primitive polynomial, $\gamma$ is a generator of $\F_{2^4}$ and we can use
$\gamma$'s polynomial and say that $\beta^4+\beta+1 = 0$.  Then, consulting
the log table in appendix \ref{appx:Fp_log_tables} for multiplication, we
have
\begin{eqnarray*}
	M_\beta(y) &=& \prod_{\sigma \in \Gal(\F_{2^4}/\F_{2^2})}
		(y - \sigma(\beta)) \\
	&=& (y - \beta)(y - \beta^4) \\
	&=& (y + \beta)(y + \beta^4)  \textrm{ since $p=2$} \\
	&=& (y + 0010)(y + 0011) \\
	&=& y^2 + y + 0110 \\
	&=& y^2 + y + \beta^2 + \beta
\end{eqnarray*}

To get this as a polynomial with coefficients in $\F_{2^2}$, i.e. with
coefficients in $\alpha$ rather than in $\beta$, use the unembedding technique
above and observe (perhaps from the root chart) that $\beta^2 + \beta$ is an
element of the $\F_{2^2}$ inside $\F_{2^4}$.  It is the 1st power of
$\beta^2+\beta$, whose minimal polynomial is $y^2+y+1$.  Over the standard
$\F_{2^2}$, this factors as $(y-\alpha)(y-\alpha-1)$.  Arbitrarily select the
first root, $\alpha$, and take its 1st power to write

$$
	M_\beta(y) = y^2 + y + \alpha \\
$$

Was it just good fortune that the coefficient $\beta^2+\beta$ was an element of
$\F_{2^2}$, allowing us to replace it with an $\alpha$?  No; in fact, this is
precisely what the Galois theory guarantees.

%% ----------------------------------------------------------------
\subsection{Double-compact notation}

Now that we have this minimal polynomial for $\beta$, just as we used
$\alpha^2+\alpha+1 = 0$ to simplify powers of $\alpha$ by $\alpha^2 =
\alpha+1$, here also we can simplify powers of $\beta$ by $\beta^2 = \beta +
\alpha$.  The resulting log table, after some pencil-and-paper work which I've
omitted, is as follows.  First I must introduce the \emph{double compact
notation}, of the form 11:10.  The adjacent digits are assumed to be in
$\alpha$, e.g. $11=\alpha+1$; the colon-delimited extended digits are in
$\beta$, e.g. $1:1 = \beta+1$.  So, 11:10 would be $(\alpha+1)\beta + \alpha =
\alpha\beta + \beta + \alpha$.

\begin{tabular}{|r|r|r|r|r|}
\hline
$k$ & $\gamma^k$ (compact) & $\gamma^k$ (full)&
$\beta^k$ (compact) &
$\beta^k$ (full)\\
\hline
\hline
1  & $0010$ & $\gamma$                     &  01:00 &$\beta$ \\
2  & $0100$ & $\gamma^2$                   &  01:10 &$\beta+\alpha$ \\
3  & $1000$ & $\gamma^3$                   &  11:10 &$(\alpha+1)\beta+\alpha$ \\
4  & $0011$ & $\gamma+1$                   &  01:01 &$\beta+1$ \\
5  & $0110$ & $\gamma^2+\gamma$            &  00:10 &$\alpha$ \\
6  & $1100$ & $\gamma^3+\gamma^2$          &  10:00 &$\alpha\beta$ \\
7  & $1011$ & $\gamma^3+\gamma+1$          &  10:11 &$\alpha\beta+\alpha+1$ \\
8  & $0101$ & $\gamma^2+1$                 &  01:11 &$\beta+\alpha+1$ \\
9  & $1010$ & $\gamma^3+\gamma$            &  10:10 &$\alpha\beta+\alpha$ \\
10 & $0111$ & $\gamma^2+\gamma+1$          &  00:11 &$\alpha+1$ \\
11 & $1110$ & $\gamma^3+\gamma^2+\gamma$   &  11:00 &$(\alpha+1)\beta$ \\
12 & $1111$ & $\gamma^3+\gamma^2+\gamma+1$ &  11:01 &$(\alpha+1)\beta+1$ \\
13 & $1101$ & $\gamma^3+\gamma^2+1$        &  10:01 &$\alpha\beta+1$ \\
14 & $1001$ & $\gamma^3+1$                 &  11:11 &$(\alpha+1)\beta+\alpha+1$ \\
15 & $0001$ & $1$                          &  00:01 &$1$ \\
\hline
\end{tabular}

%% ----------------------------------------------------------------
\subsection{Second example for intermediate fields}
\label{sec:f26_gal_corresp}

Throughout much of this paper I've used finite fields with $p=2$, $n=4$: these
are small enough that it's easy to write down all the field elements, yet large
enough that there is some interesting behavior, namely, more than one monic
irreducible (which doesn't happen e.g.  with $p=2$, $n=2$), and an intermediate
field (which doesn't happen e.g. with any $p$ for $n=3$).

However, the $p=2$, $n=4$ case doesn't give quite as interesting a subfield
diagram as it could.  The next smallest more interesting case is $p=2$, $n=6$.
Here I won't write down all the irreducibles:  there are 9 of them, and I'll
choose $x^6+x+1$ which happens to be primitive\footnote{You might suspect a
pattern here: $x^2+x+1$, $x^3+x+1$, $x^4+x+1$ and $x^6+x+1$ are all irreducible
and primitive in $\F_2[x]$.  But don't be fooled:  it is not the case that
$x^n+x+1$ is irreducible for all $n$, let alone primitive.}.

\setlength{\unitlength}{1.0in}
\begin{picture}(6,2.5)

\put(0.30,2.25){$\F_{2^6}
	= \F_2(\alpha)(\delta)
	= \F_2(\beta)(\veps)
	= \F_2(\gamma), \,\gamma^6 + \gamma + 1 = 0 $}
\put(0.80,1.30){\line(2,3){.55}}
\put(1.50,2.10){\line(3,-2){.77}}
\put(0.00,1.00){$\F_{2^2} = \F_2(\alpha), \, \alpha^2 + \alpha + 1 = 0$}
\put(2.50,1.50){$\F_{2^3} = \F_2(\beta), \, \beta^3 + \beta + 1 = 0$}
\put(1.40,0.40){\line(-3,2){.60}}
\put(1.60,0.40){\line(2,3){.70}}
\put(1.45,0.25){$\F_2$}

\put(5.10,2.25){$\langle \rho^6=\iota \rangle$}
\put(4.80,1.30){\line(2,3){.55}}
\put(5.50,2.10){\line(3,-2){.77}}
\put(4.50,1.00){$\langle \rho^2 \rangle$}
\put(6.50,1.50){$\langle \rho^3 \rangle$}
\put(5.40,0.40){\line(-3,2){.60}}
\put(5.60,0.40){\line(2,3){.70}}
\put(5.40,0.25){$\langle \rho \rangle$}

\end{picture}

Here is a root chart for $\F_{2^6}$, but displaying, for brevity, only roots
mod the single monic irreducible $x^6+x+1$ rather than mod all the sextics.
(For $\F_{2^4}$, I tabulated roots mod all the quartics.) Logarithms with
respect to generator $u=000010$ are displayed in parentheses to the right of
the field elements.  This makes the root chart a log table as well (although
entries aren't in a convenient order) so we can consult this for
multiplication.  Also I include root charts for the standard subfields
$\F_{2^3}$ and $\F_{2^2}$.

%\begin{verbatim}
%Root chart for F_2^6 defined by x^6 + x + 1:
%Linears
%  0000010: 000000(--)
%  0000011: 000001(63)
%Quadratic
%  0000111: 111010(42) 111011(21)
%Cubics
%  0001011: 001110(27) 010111(54) 011001(45)
%  0001101: 001111(18) 010110(36) 011000( 9)
%Sextics
%  1000011: 000010( 1) 000100( 2) 001001(32) 001100( 8) 010000( 4) 010011(16)
%  1001001: 000110( 7) 001011(35) 010100(14) 011010(49) 011100(28) 011111(56)
%  1010111: 000011( 6) 000101(12) 001000( 3) 001101(48) 010001(24) 010010(33)
%  1011011: 000111(26) 001010(13) 010101(52) 011011(38) 011101(41) 011110(19)
%  1100001: 100001(62) 100101(31) 100111(47) 101110(55) 110001(61) 111101(59)
%  1100111: 100000( 5) 100100(34) 100110(17) 101111(40) 110000(10) 111100(20)
%  1101101: 100010(25) 100011(11) 101100(37) 101101(44) 110100(50) 110101(22)
%  1110011: 101001(23) 101010(53) 110010(46) 110111(43) 111000(29) 111111(58)
%  1110101: 101000(15) 101011(51) 110011(30) 110110(39) 111001(60) 111110(57)
%\end{verbatim}

\begin{verbatim}
Root chart for 1000011, g = 000010
Linears
  0000010: 000000( -)
  0000011: 000001( 0)
Quadratic
  0000111: 111011(21) 111010(42)
Cubics
  0001011: 001110(27) 010111(54) 011001(45)
  0001101: 011000( 9) 001111(18) 010110(36)
Sextics
  1000011: 000010( 1) 000100( 2) 010000( 4) 001100( 8) 010011(16) 001001(32)
  1001001: 000110( 7) 010100(14) 011100(28) 011111(56) 011010(49) 001011(35)
  1010111: 001000( 3) 000011( 6) 000101(12) 010001(24) 001101(48) 010010(33)
  1011011: 001010(13) 000111(26) 010101(52) 011101(41) 011110(19) 011011(38)
  1100001: 100101(31) 100001(62) 110001(61) 111101(59) 101110(55) 100111(47)
  1100111: 100000( 5) 110000(10) 111100(20) 101111(40) 100110(17) 100100(34)
  1101101: 100011(11) 110101(22) 101101(44) 100010(25) 110100(50) 101100(37)
  1110011: 101001(23) 110010(46) 111000(29) 111111(58) 101010(53) 110111(43)
  1110101: 101000(15) 110011(30) 111001(60) 111110(57) 101011(51) 110110(39)
\end{verbatim}

Observe again the subfield/log criterion: the roots of the linears and the
quadratic have logs divisible by $21=(2^6-1)/(2^2-1) $; the roots of the
linears and the cubics have logs divisible by $9=(2^6-1)/(2^3-1)$.

\begin{verbatim}
Root chart for 1011, g = 010
Linears
  0010: 000(-)
  0011: 001(0)
Cubics
  1011: 010(1) 100(2) 110(4)
  1101: 011(3) 101(6) 111(5)
\end{verbatim}

\begin{verbatim}
Root chart for 111, g = 10
Linears
  010: 00(-)
  011: 01(0)
Quadratic
  111: 10(1) 11(2)
\end{verbatim}

$\F_{2^2}$ is an extension of $\F_2$.  Likewise, $\F_{2^3}$ is an extension of
$\F_2$.  Also we can think of $\F_{2^6}$ as an extension of $\F_2$:  this
$\F_{2^6}$ is $\F_2$ adjoin $\gamma$ where $\gamma$ is a root of $x^6+x+1$.
(In the root chart, $\gamma$ appears as $000010$.) $\F_{2^6}$ is a sextic
extension of $\F_2$ whose elements are linear combinations of $1$, $\gamma$,
$\gamma^2$, $\gamma^3$, $\gamma^4$ and $\gamma^5$ with coefficients in the base
field $\F_2$.  The Galois group of this extension is $\{\iota, \rho, \rho^2,
\rho^3, \rho^4, \rho^5\}$ and $a^2=a$ for all $a$ in the base field $\F_2$.
The minimal polynomial of $\gamma$ is
\begin{eqnarray*}
	&&(x-\gamma) (x-\gamma^2) (x-\gamma^4)
	(x-\gamma^8) (x-\gamma^{16}) (x-\gamma^{32}) \\
	&=& (x+000010) (x+000100) (x+010000) (x+001100) (x+010011) (x+001001) \\
	&=& x^6+x+1
\end{eqnarray*}
using $\gamma^6+\gamma+1$ arithmetic.

Now, how do we see $\F_{2^6}$ as an extension field not of $\F_2$ but rather of
$\F_{2^2}$ and $\F_{2^3}$? We should be able to write $\F_{2^6}$ as
$\F_2(\alpha)(\delta)$ for some $\delta$.  This will be a cubic extension of
$\F_2(\alpha)$ so elements of this $\F_{2^6}$ will be linear combinations of
$1$, $\delta$ and $\delta^2$ with coefficients in $\F_2(\alpha)$.  Likewise, we
should be able to write $\F_{2^6}$ as $\F_2(\beta)(\veps)$ for some $\veps$.
This will be a quadratic extension of $\F_2(\beta)$ so elements of this
$\F_{2^6}$ will be linear combinations of $1$ and $\veps$ with coefficients in
$\F_2(\beta)$.

We lack the minimal polynomials of $\delta$ and $\veps$.  We need them to
simplify powers of $\delta$ and $\veps$ so we can do arithmetic in
$$ \F_{2^6} = \F_2(\alpha)[y] / \langle M_\delta(y) \rangle $$
and
$$ \F_{2^6} = \F_2(\beta)[y] / \langle M_\veps(y) \rangle $$

The Galois group of $\F_2(\alpha)(\delta)$ over $\F_2(\alpha)$ is $\langle
\rho^2 \rangle = \{\iota, \rho^2, \rho^4\}$, since $a^4=a$ fixes the base
field $\F_{2^2}$.  Likewise, the Galois group of $\F_2(\beta)(\veps)$ over
$\F_2(\beta)$ is $\langle \rho^3 \rangle = \{\iota, \rho^3\}$, since
$a^8=a$ fixes the base field $\F_{2^3}$.

To find the minimal polynomials of $\delta$ and $\veps$, obtain a generator of
the $\F_{2^6}$ defined by $\gamma$.  Since $x^6+x=1$ is a primitive polynomial,
$\gamma$ generates the multiplicative group.  Again we appropriate $\gamma$'s
polynomial for $\delta$ and $\veps$, so $\delta^6+\delta+1=0$ and
$\veps^6+\veps+1=0$.  Since the Galois groups of $\F_{2^6}/\F_{2^2}$ and
$\F_{2^6}/\F_{2^3}$ are $\langle \rho^2 \rangle$ and $\langle \rho^3 \rangle$,
respectively, by definition the minimal polynomials are
\begin{eqnarray*}
	M_\delta(y) &=& (y - \delta) (y - \delta^4) (y - \delta^{16}) \\
	M_\veps(y) &=& (y - \veps) (y - \veps^8)
\end{eqnarray*}

Using the logarithms included in the $\F_{2^6}$ root chart for multiplication,
the former simplifies to
\begin{eqnarray*}
	M_\delta(y) &=& (y - \delta) (y - \delta^4) (y - \delta^{16}) \\
	&=& (y + \delta) (y + \delta^4) (y + \delta^{16}) \\
	&=& (y + 000010) (y + 010000) (y + 010011) \\
	&=& (y + 000010) (y^2 + 000011 y + 111100) \\
	&=& y^3 + y^2 + 111010 y + 111011
\end{eqnarray*}

With reference to the root chart for $\F_{2^6}$, 111010 is $\delta^{42}$ and
111011 is $\delta^{21}=(\delta^{21})^2$.  These are roots of $x^2+x+1$ in
$\F_{2^6}$, which from the root chart for $\F_{2^2}$ has corresponding roots
$\alpha$ and $\alpha+1$.  Thus, using the unembedding $\delta^{42} \mapsto
\alpha$,
$$
	M_\delta(y) = y^3 + y^2 + \alpha y + \alpha+1
$$

Likewise,
\begin{eqnarray*}
	M_\veps(y) &=& (y - \veps) (y - \veps^8)\\
	&=& (y + \veps) (y + \veps^8)\\
	&=& (y + 000010) (y + 001100)\\
	&=& y^2 + 001110 y + 011100
\end{eqnarray*}

%% Root chart for 1000011, g = 000010
%% 0000010: 000000( -)
%% 0000011: 000001( 0)
%% 0000111: 111011(21) 111010(42)
%% 0001011: 001110(27) 010111(54) 011001(45)
%% 0001101: 011000( 9) 001111(18) 010110(36)
%% 1000011: 000010( 1) 000100( 2) 010000( 4) 001100( 8) 010011(16) 001001(32)
%% 1001001: 000110( 7) 010100(14) 011100(28) 011111(56) 011010(49) 001011(35)
%% 1010111: 001000( 3) 000011( 6) 000101(12) 010001(24) 001101(48) 010010(33)
%% 1011011: 001010(13) 000111(26) 010101(52) 011101(41) 011110(19) 011011(38)
%% 1100001: 100101(31) 100001(62) 110001(61) 111101(59) 101110(55) 100111(47)
%% 1100111: 100000( 5) 110000(10) 111100(20) 101111(40) 100110(17) 100100(34)
%% 1101101: 100011(11) 110101(22) 101101(44) 100010(25) 110100(50) 101100(37)
%% 1110011: 101001(23) 110010(46) 111000(29) 111111(58) 101010(53) 110111(43)
%% 1110101: 101000(15) 110011(30) 111001(60) 111110(57) 101011(51) 110110(39)

With reference to the root chart for $\F_{2^6}$, 001110 is $\veps^{27}$ and
011000 is $\veps^{9}$.  The former, $\veps^{27}$, is a root of $x^3+x+1$ in
$\F_{2^6}$, which from the root chart for $\F_{2^3}$ has a corresponding root
$\beta$.  The other coefficient, $\veps^9$, is $(\veps^{27})^5$ which maps to
$\beta^5=\beta^2+\beta+1$.  Thus, using the unembedding $\veps^{27} \mapsto
\beta$,
$$
	M_\veps(y) = y^2 + \beta y + \beta^2+\beta+1
$$

As a sanity check, one can verify by factorization (e.g. appendix
\ref{appx:berlekamp}) that these two minimal polynomials are irreducible over
their respective base fields and have $\delta$ and $\veps$, respectively, as
roots.

(Also note that one can obtain the minimal polynomials $M_\delta$ and $M_\veps$
by factoring $y^6+y+1$ over $\F_{2^2}$ and $\F_{2^3}$, respectively, and
selecting in each case the factors of which $\delta$ and $\veps$, respectively,
are roots.  I've not pursued that method in this paper since it is more
time-consuming on paper.)

Now that the minimal polynomials have been obtained, we can write a log table
as above.  Since there are 64 field elements, I'll show only a few rows.

\begin{tabular}{|r|r|r|r|}
\hline
$k$ & $\delta^k$ (compact) & $\veps^k$ (compact) & $\gamma^k$ (compact) \\
\hline
 1 &    01:00 & 001:000 & 000010 \\
 2 & 01:00:00 & 010:111 & 000100 \\
 3 & 01:10:11 & 011:101 & 001000 \\
 4 & 11:01:11 & 011:010 & 010000 \\
 5 & 10:10:10 & 100:010 & 100000 \\
 6 &    01:01 & 001:001 & 000011 \\
 7 & 01:01:00 & 011:111 & 000110 \\
 8 &    10:11 & 001:010 & 001100 \\
 9 & 10:11:00 &     111 & 011000 \\
\vdots & \vdots & \vdots & \vdots \\
21 &       11 & 101:100 & 111011 \\
\vdots & \vdots & \vdots & \vdots \\
27 &    11:11 &     010 & 001110 \\
\vdots & \vdots & \vdots & \vdots \\
42 &       10 & 101:101 & 111010  \\
\vdots & \vdots & \vdots & \vdots \\
61 & 01:11:00 & 111:001 & 110001 \\
62 & 10:10:11 & 100:011 & 100001 \\
63 &       01 &     001 & 000001 \\
\hline
\end{tabular}

%% To summarize, the minimal polynomials
%% $M_\gamma(x)$,
%% $M_\delta(y)$ and
%% $M_\veps(y)$
%% are found as follows:
%%
%% \begin{eqnarray*}
%% 	M_\gamma(x) &=&
%% 		(x - \gamma) (x-\gamma^{2}) (x-\gamma^{4})
%% 		(x-\gamma^{8}) (x-\gamma^{16}) (x-\gamma^{32}) \\
%% 	M_\delta(y) &=&
%% 		(y - \gamma)  (y-\gamma^{4}) (y-\gamma^{16})  \\
%% 	M_\veps(y) &=&
%% 		(y - \gamma) (y-\gamma^{8})  \\
%% \end{eqnarray*}

%% ================================================================
\appendix

%% ================================================================
\newpage
\section{Blankinship's algorithm for extended GCD}
\label{appx:blankinship}

Since $\Z$ and $\F_p[x]$ are both Euclidean domains, we have a Euclidean GCD
algorithm for both.  This algorithm is usually (in my experience) presented as
follows:

\begin{itemize}
\item Input $a$, $b$; output $g$.
\item If $b=0$, $g:=a$; stop.  (This avoids a divide-by-zero exception below.)
\item Let $c := a$, $d := b$.
\item Top of loop:
\begin{itemize}
	\item Use integer or polynomial division on $c$ and $d$ to obtain
	quotient $q$ and remainder $r$ such that $q=cd+r$ and $r<d$ (for
	integers) or $\deg(r) < \deg(d)$ (for polynomials).
	\item If $r = 0$, $g=d$; stop.
	\item $c := d$, $d := r$.
	\item Go to top of loop.
\end{itemize}
\end{itemize}

To then obtain $m$, $n$ such that $ma + nb = g$, one then works the algorithm
in reverse.  Not only is this tedious, but also it requires one to remember (on
paper) or allocate space for (in software) all the intermediate $c$, $d$
values.

A superior method is due to Blankinship \cite[Ch.~1.2.1]{bib:knu1}.  The
derivation is given in Knuth; here I will describe the algorithm.  The key is
that $m$ and $n$ are computed along with the GCD $g$, with no need for
backtracking.  The algorithm is:

\begin{itemize}
\item Input $a$, $b$; output $g$.
\item If $b=0$, $g:=a$; stop.  (This avoids a divide-by-zero exception below.)
\item Let $c := a$, $d := b$.
\item Let $m' := 1$, $m := 0$, $n' := 0$, $n := 1$.
\item Top of loop:
\begin{itemize}
	\item Use integer or polynomial division on $c$ and $d$ to obtain
	quotient $q$ and remainder $r$ such that $q=cd+r$ and $r<d$ (for
	integers) or $\deg(r) < \deg(d)$ (for polynomials).
	\item If $r = 0$, $g:=d$; stop.
	\item $c := d$, $d := r$.
	\item Let $t := m'$, $m' := m$, $m = t - qm$.
	\item Let $t := n'$, $n' := n$, $n = t - qn$.
	\item Go to top of loop.
\end{itemize}
\end{itemize}

%% ================================================================
\newpage
\section{Shanks algorithm for discrete logs in a cyclic group}
\label{appx:shanks}

Above we saw how to compute logs using a linear search.  That is, given a
cyclic group $G$ of order $N$, a generator $g$ and an element $a$, simply test
all the $N$ powers $g^0$, $g^1$, $g^2$, \ldots, $g^{N-1}$ to find which one is
equal to $a$.  (If none of them equals $a$, then $G$ is not a group, its order
isn't really $N$, $g$ isn't really a generator, or $a$ isn't really a member of
the group.)

This is fine for small groups.  The time requirement is clearly $O(N)$, with
storage space $O(1)$.  However, for large groups there is a method due to
Shanks \cite{bib:odlyzko} with much better execution time, at the expense of
more storage space.

Let $G$, $N$, $g$ and $a$ be as above, and let $k$ be the logarithm of $a$ with
respect to $g$, i.e. $a=g^k$, with $0 \le k < N$.  The trick is to view $k$ as
a two-digit, base-$m$ number $i+jm$ where $m = \lfloor \sqrt{N} \rfloor$, and
$0 \le i, j < m$.  Then
\begin{eqnarray*}
	a &=& g^{i+jm} \\
	&=& g^i g^{jm} \\
	a g^{-i} &=& g^{jm}
\end{eqnarray*}

The algorithm is as follows:

\begin{itemize}

\item Make two arrays of ordered pairs.  The first array consists of the $m$
pairs $(i, ag^{-i})$; the second consists of the $m$ pairs $(j, g^{jm})$.
(When you generate these arrays, probably you'll loop over the $i$'s and $j$'s,
so the arrays will already be sorted by $i$'s and $j$'s.)

\item Choose some ordering of group elements and sort both arrays by the second
elements of the ordered pairs, i.e. the $ag^{-i}$'s and the $g^{jm}$'s.

\item Search the arrays for a pair of pairs such that $ag^{-i} = g^{jm}$.

\end{itemize}

It can be shown (and is easy to see) that you can search a pair of sorted
length-$m$ arrays in $O(m)$ comparisons.  Clearly this is $O(\sqrt{N})$ in
space, more expensive than the linear search.  But the time savings from $O(N)$
to $O(\sqrt{N})$ is dramatic.


%% ================================================================
\newpage
\section{How to find primitive elements of $\F_p$}
\label{appx:prims_in_Fp}

In section \ref{sec:prims_in_Fp} on page \pageref{sec:prims_in_Fp} I discussed
one way to find a primitive element of $\F_p$:  search for it.  That is, given
a non-zero element $g$ of $\F_p$, write down all the $p-2$ powers $g$, $g^2$,
\ldots, $g^{p-1}$ and check if they are all distinct.  While this suffices to
show that an element is a generator, it is more work than necessary.

From group theory, recall that if $g$ is a generator of the multiplicative
group $\F_p^\times$ which has order $p-1$, then $g^{p-1} = 1$ and no smaller
positive power sends $g$ to 1.  Also recall that if $g$ were to have smaller
order $k$, i.e. $g^k=1$ for $k < p-1$, that order would need to divide the
order of the group, i.e. $k \,|\,p-1$.  Thus we can factor $p-1$, and raise $g$
only to powers dividing $p-1$.  If any proper divisor sends $g$ to 1, $g$ is
not a generator.  As an error check on one's computations, it is nice to also
verify that $g^{p-1}$ \emph{is} 1.

For example, let's see if 2 generates $\F_{23}$.  Since proper divisors of
$p-1=22$ are 1, 2 and 11, we only need to check $2$, $2^2$ and $2^{11}$.
Clearly, neither 2 nor 4 is 1 mod 23; $2^{11}=2048$, which mod 23 is 1 since
$2047 = 23\cdot  89$.  Therefore 2 is not a generator.  Likewise 3 and 4 fail,
but 5 succeeds.

%% ================================================================
\newpage
\section{How to find irreducible polynomials in $\F_p[x]$}
\label{appx:irreds_in_Fp}

In section \ref{sec:find_irreds} on page \pageref{sec:find_irreds} I discussed
a few techniques for finding irreducible polynomials in $\F_p[x]$:

\begin{itemize}
\item For degree three or less, use the root test since if there is a
	non-trivial factorization, at least one factor must be linear.
\item For degree four above, first use the root test to check for linear
	factors, then use trial division by factors of degree 2 through $n/2$.
\end{itemize}

Here are a few more options.

%% ----------------------------------------------------------------
\subsection{Universal-polynomial algorithm}

There is an irreducibility algorithm, much more efficient than trial division,
which I found in a snippet of C code on thee web a while back.  I would
attribute it to the proper person, but I have since lost the URL and haven't
found it in any other references.  Nonetheless, I've discovered that the
concept is very simple.

In section \ref{sec:univ_poly} on page \pageref{sec:univ_poly} I defined the
universal polynomial $x^{p^n} - x$, and noted that this factors into the
product of all monic irreducibles of degree $d$ for all $d$ dividing $n$.
Suppose $r(x)$ is a given polynomial in $\F_p[x]$ and let $m$ be the degree of
$r(x)$.  Divide $r(x)$ by its leading coefficient to make it monic, if it is
not already:  thus any factors of $r$ will also be monic.  If $r(x)$ has an
irreducible factor of degree $i$ less than $m$, then that factor will divide
$x^{p^i}-x$.  Contrapositively, if $r(x)$ has no common factors with
$x^{p^i}-x$ for $i<m$, then $r(x)$ is irreducible.

(Example:  Suppose $r(x)$ is of degree 8, with irreducible factors $r_1$ and
$r_2$ of degrees 3 and 5, respectively.  Then $r_1$ must be one of the factors
of $x^{p^3}-x$, and $r_2$ must be one of the factors of $x^{p^5}-x$.)

% x^{p^1 - x}: 1
% x^{p^2 - x}: 1,2
% x^{p^3 - x}: 1,3       *
% x^{p^4 - x}: 1,2,4
% x^{p^5 - x}: 1,5       *
% x^{p^6 - x}: 1,2,3     *
% x^{p^7 - x}: 1,7
% x^{p^8 - x}: 1,2,4,8

Now, $x^{p^m}-x$ can be a very high-degree polynomial, which makes sense since
it can have a lot of factors.  Fortunately, we don't care about all of those
factors, so we can avoid huge polynomials as follows:  For each $i$ from 1 up
to and including $m-1$, find $x^{p^i}-x$ mod $r(x)$ and compute the GCD of $r$
with the remainder.  If there is a common factor, it will be retained mod
$r(x)$.  Reducing mod $r(x)$ just keeps the degree reasonable.  If the GCD is 1
for each power, $r$ is irreducible.

More specifically, here is the algorithm:

\begin{itemize}
\item Input $p$ a prime, $r(x)$ in $\F_p[x]$.
\item Set $m := \deg\langle r(x) \rangle$
\item Set $U(x) := x$
\item For $i$ from 1 to $m-1$:
	\begin{itemize}
	\item Set $U(x) := (U(x))^p \mod r$.  (Here, $U$ is $x^{p^i}$ mod $r$.)
	\item Set $g(x) := \textrm{GCD}(r(x), U(x)-x)$
	\item If $g(x) \ne 1$ then return REDUCIBLE
	\end{itemize}
\item Return IRREDUCIBLE
\end{itemize}

%//	for (i = 1; i < d; i++) {
%//		// u = u**2 mod r; test GCD(u - x, r)
%//		u = z2ipolymod_mul(u, u, r);
%//		ux = u^x;
%//		g = z2ipoly_gcd(r, ux);
%//
%//		if (g != 1) {
%//			// If we got here, r is known to be reducible and g
%//			// is a factor.
%//			z2ipoly_t q = z2ipoly_div(r, g);
%//			pre_berlekamp2i(g, pirred_factors, pnum_irred_factors);
%//			pre_berlekamp2i(q, pirred_factors, pnum_irred_factors);
%//			return;
%//		}
%//	}

%% ----------------------------------------------------------------
\subsection{Derivative test for multiple factors}

One may quickly test for repeated factors by computing the GCD of $r$ and its
formal derivative.  This is not an irreducibility test, but it can be a quick
way to reveal some factors.  Also it is a necessary preliminary for the next
option.

%% ----------------------------------------------------------------
\subsection{One pass of Berlekamp's algorithm}

The above universal-polynomial algorithm is efficient, but for implementation
in a computer program it turns out that it is even more efficient to run one
pass of Berlekamp's factorization algorithm (which requires squarefree input):
\cite[Ch.~4.1]{bib:ln} and appendix \ref{appx:berlekamp}.

%% ----------------------------------------------------------------
\subsection{All-irreducibles algorithm}
\label{appx:all_irreds_algm}

The discussion in section \ref{sec:split_upoly} on page
\pageref{sec:split_upoly} immediately suggests a technique to produce all the
remaining irreducibles of a given degree, given a single one (found e.g. by one
of the above methods).

\begin{itemize}
\item Given $r(x)$ of degree $n$ in $\F_p[x]$, write down all the $p^n$
	elements of the finite field $\F_p[x]/\langle r(x) \rangle$.
\item Perhaps after making up a log table to facilitate computation,
	for each element $\alpha$ take repeated $p$th powers until you get a
	repetition.  This will give you Frobenius orbits of each element.
\item For each Frobenius orbit, take all the distinct $\rho^i(\alpha)$'s, write
	down $\prod_i (x-\rho^i(\alpha))$ and multiply it out using arithmetic
	defined by $r(x)$.  This will give you minimal polynomials for each
	element.
\item You will obtain a result much like the root chart in section
	\ref{sec:split_upoly} on page \pageref{sec:split_upoly}.  Discard all
	minimal polynomials of degree less than $n$.  The remaining minimal
	polynomials are all the monic irreducibles of degree $n$.
\end{itemize}

Example:

\begin{itemize}
\item Given $x^3+x+1$ of degree $3$ in $\F_2[x]$, we have the eight
	field elements $000$, $001$, $010$, $011$, $100$, $101$, $110$, $111$.

\item $000^2 = 000$
\item $001^2 = 001$
\item $010^2 = 100$; $100^2 = 110$; $110^2 = 010$.
\item $011^2 = 101$; $101^2 = 111$; $111^2 = 011$.

\item $(x-000) = x$
\item $(x-001) = x+1$
\item $(x-010)(x-100)(x-110) = x^3+x+1$
\item $(x-011)(x-101)(x-111) = x^3+x^2+1$

\item Degree-3 polynomials in the above are $x^3+x+1$ and $x^3+x^2+1$.
\end{itemize}

%% ================================================================
\newpage
\section{How to find primitive polynomials in $\F_p[x]$}
\label{appx:prims_in_Fpx}

In appendix \ref{appx:prims_in_Fp} on page \pageref{appx:prims_in_Fp} I
discussed how to find primitive elements of $\F_p$.  The key is that
$\F_p^\times$ is cyclic of order $p-1$; given $a$ in $\F_p$, it suffices to
check that $a^d \ne 1$ for all proper divisors $d$ of $p-1$.

Here the same concept applies.  Given $r(x)$, first test that $r(x)$ is
irreducible as described in appendix \ref{appx:irreds_in_Fp} on page
\pageref{appx:irreds_in_Fp}.  Second, $r(x)$ will be primitive if $u$ is a
primitive element mod $r$.  Let $n=\deg(r)$ and work in the finite field
$\F_p[x]/\langle r(x) \rangle$.  Recall that this field has a multiplicative
group of order $p^n-1$.  Find all proper divisors $d$ of $p^n-1$.  If $u^d \ne
1$ for all of them, then $u$ is a primitive element mod $r$, and $r$ is a
primitive polynomial.  Otherwise, $r$ is not primitive.

Note:  The amount of work involved depends highly on the factorization of
$p^n-1$.  Also note that for $p=3$ and $n=2$, or for $p=2$ and various values
of $n$, $p^n-1$ can be a prime number.  In such cases, \emph{all} monic
irreducibles of degree $n$ are primitive, by Lagrange's theorem.  (In fact, by
Lagrange's theorem all elements of the field other than 0 and 1 have order
$p^n-1$.)

%% ================================================================
\newpage
\section{Factoring in $\F_p[x]$ and $\F_{p^n}[x]$}
\label{appx:berlekamp}

In the main body of the paper I discussed factoring by trial division, which is
possible since given a polynomial $f(x)$ in $\F_{p^n}[x]$ there are finitely
many polynomials of degree less than the degree of $f(x)$.  This is fine (and
even preferable) for small $p$, $n$ and degree.  However, for factoring larger
polynomials in a software implementation, a much more efficient method is
available.

The following algorithm (Berlekamp's along with necessary preprocessing) is
proved correct in \cite{bib:ln}; here, I show only the algorithm itself.  I
note that, in contrast to the much harder problem of factoring polynomials over
$\Z[x]$ or $\Q[x]$, this algorithm is easy to implement in software and also is
very efficient.  That is, factoring polynomials in $\F_p[x]$ and $\F_{p^n}[x]$
is ``easy'' whereas factoring in $\Z[x]$ or $\Q[x]$ (by current methods, at
least) is ``hard''.

Input is $f(x) \in \F_{p^n}[x]$.  For input in $\F_p[x]$, just use $n=1$.
Let $m=\deg(f(x))$.

%% ----------------------------------------------------------------
\subsection{Recursion}

The algorithm is recursive:  as presented here, it will either determine that a
polynomial is irreducible, or it will produce a pair of non-trivial factors.
If one's goal is merely to determine whether $f(x)$ is irreducible, this pass
is sufficient, but if one's goal is to produce a complete factorization of
$f(x)$, one must repeat the algorithm for both factors.

%% ----------------------------------------------------------------
\subsection{Squarefree preparation}

Berlekamp's algorithm requires squarefree input.  This may be obtained by first
taking the GCD of the input polynomial and its derivative:

\begin{itemize}
\item Assume that the input $f(x)$ is non-zero and has degree
	greater than 1 (otherwise we don't need to be here).
\item $g(x) = \mathrm{GCD}(f(x), f'(x))$
\item If $g(x)$ has degree 0, $f(x)$ is squarefree; proceed to Berlekamp's
	algorithm.
\item Else if $f'(x)=0$, the input is a perfect $p$ power of the form
	$$a_k x^{kp} + a_{k-1}x^{(k-1)p} + \ldots + a_1 x^p + a_0$$
	for $k=m/p$, with $p$th root
	$$a_k x^{k} + a_{k-1}x^{k-1} + \ldots + a_1 x + a_0$$
	This root may or may not be squarefree; recursively apply this step
	to the $p$th root.
\item Else $f(x)$ has proper factors $g(x)$ and $f(x)/g(x)$.  Repeat this step
	for the former, and proceed to Berlekamp's algorithm for the latter.
\end{itemize}

%% ----------------------------------------------------------------
\subsection{Berlekamp's algorithm}

Input $f(x) \in \F_{p^n}[x]$ is assumed squarefree as described above, with
$m=\deg(f(x))$.  The key insight \cite{bib:ln} is that if we can find an $h(x)
\in \F_{p^n}[x]$ such that $h(x)^{p^n} \equiv h(x)$ mod $f(x)$, then $$ f(x) =
\prod_{c \in \F_{p^n}} \mathrm{GCD}(f(x), h(x) - c)$$ The algorithm uses
linear algebra on the field $\F_{p^n}$ to find such an $h(x)$.

\begin{itemize}
\item Allocate an $m \times m$ matrix $B$, whose elements will be elements of
	$\F_{p^n}$.
\item Populate the $B$ matrix with row $i$ equal to the coefficients of
	$x^{p^n i}$ mod $f(x)$, for $0 \le i < m$.
\item Replace $B$ with $B-I$, i.e. subtract 1 on the main diagonal.
\item Transpose the $B$ matrix, i.e. $B := B^t$.
\item Using row reduction, put the matrix in row echelon form.
	(Note:  One can use column reduction with an untransposed $B$,
	but I feel that, at least for myself, row reduction is more familiar
	and less error-prone.)
\item The nullity of the matrix is the number of irreducible factors of
	$f(x)$.  However, as presented here the algorithm will only consider
	the cases when the nullity is 1, or greater than 1.
\item Compute a basis for the nullspace of the reduced matrix.  If the
	nullspace has dimension 1 (i.e. if the rank of the reduced matrix
	is $m-1$), then $f(x)$ is irreducible in $\F_{p^n}[x]$; stop.
\item For each row, let $h(x)$ have coefficients corresponding to row
	elements; for each $c \in \F_{p^n}$, compute $f_1(x) =
	\mathrm{GCD}(f(x), h(x)-c)$.
\item	When an $h(x)$ and a $c$ is found\footnote{Such will always be found,
	but not all rows will suffice: e.g.  one row will produce $h(x)=1$,
	which does not lead to a non-trivial factorization.} such that
	$\deg(f_1(x))$ is greater than 0 and less than $\deg(f(x))$, $f_1(x)$
	and $f_2(x) = f(x)/f_1(x)$ are proper factors.  Recursively apply this
	algorithm to each of them until a factorization into irreducibles has
	been obtained.
\end{itemize}

%% ================================================================
\newpage
\section{How to construct a root chart}
\label{appx:root_chart_how_to}

There are two ways to construct a root chart (example root charts appear in
sections \ref{sec:split_upoly} and \ref{sec:f26_gal_corresp}):

\begin{enumerate}

\item Given the polynomial $x^{p^n}-x$ and a monic irreducible degree-$n$
polynomial $r(x)$ in $\F_p[x]$ (see appendix \ref{appx:irreds_in_Fp} for
irreducibility testing) with which to define arithmetic for an $\F_{p^n}$, use
Berlekamp's algorithm (appendix \ref{appx:berlekamp}) to factor $x^{p^n}-x$ in
$\F_p[x]$.  Then, for each resulting monic irreducible factor, use Berlekamp's
algorithm in $\F_{p^n}[x]$, or use trial evaluations over all elements of
$\F_{p^n}$, to find roots in $\F_{p^n}$ for each of the resulting factors.

\item Use Galois theory as described in section \ref{sec:galois_theory}:

\begin{itemize}

\item Write down a logarithm table for $\F_{p^n}$.

\item For increasing divisors $d$ of $n$, use the subfield/log criterion to
find elements of $\F_{p^d}$, i.e. elements whose log is a multiple of
$(p^n-1)/(p^d-1)$.

\item For each resulting element $a$ of $\F_{p^d}$, write down the $d$ distinct
Frobenius-orbit elements $a$, $a^p$, \ldots, $a^{p^{d-1}}$.  Cross them all off
from the log table so they will be processed only once.  Also compute the
product $$\prod_{i=1}^d (x-a^{p^i})$$  This is the minimal polynomial for all
$d$ elements in the Frobenius orbit.  Write down this minimal polynomial,
followed by the $d$ roots.

\item Once all elements in the log table have been crossed off, sort rows of
the root chart lexically by the minimal polynomials in the left-hand column.

\end{itemize}

\end{enumerate}

The latter method is far easier to implement with pencil and paper, and also
runs faster in software.

%% ================================================================
\newpage
\section{Tables}

%% ----------------------------------------------------------------
\subsection{Tables of some irreducible polynomials in $\F_p[x]$}
\label{appx:tables_of_irreds_in_Fp}

Primitive polynomials are marked with an asterisk.  Please see Lidl and
Niederreiter \cite{bib:ln} for much more extensive tables.

\begin{tabular}{|rr|rr|rr|rr|rr|rr|}
\hline $\F_{2^2}$ && $\F_{2^3}$ && $\F_{2^4}$ && $\F_{2^5}$ && $\F_{2^6}$ &\\
\hline
111  &*    &1011 &*    &10011 &*    &100101 &*    &1000011 &* \\
     &     &1101 &*    &11001 &*    &101001 &*    &1001001 &  \\
     &     &     &     &11111 &     &101111 &*    &1010111 &  \\
     &     &     &     &      &     &110111 &*    &1011011 &* \\
     &     &     &     &      &     &111011 &*    &1100001 &* \\
     &     &     &     &      &     &111101 &*    &1100111 &* \\
     &     &     &     &      &     &       &     &1101101 &* \\
     &     &     &     &      &     &       &     &1110011 &* \\
     &     &     &     &      &     &       &     &1110101 &  \\
\hline
\end{tabular}

\begin{tabular}{|rr|rr|}
\hline $\F_{3^2}$ && $\F_{3^3}$ & \\
\hline
101  &     &  1021  & * \\
112  &*    &  1022  &   \\
122  &*    &  1102  &   \\
     &     &  1112  &   \\
     &     &  1121  & * \\
     &     &  1201  & * \\
     &     &  1211  & * \\
     &     &  1222  &   \\
\hline
\end{tabular}

%% ----------------------------------------------------------------
\subsection{Some logarithm tables for $\Fpn$}
\label{appx:Fp_log_tables}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=111$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 3 &01 &1 \\
\hline 1 &10 &3 \\
\hline 2 &11 &3 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=111$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 1 &10 &3 \\
\hline 2 &11 &3 \\
\hline 3 &01 &1 \\
\hline
\end{tabular}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=1011$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 7 &001 &1 \\
\hline 1 &010 &7 \\
\hline 3 &011 &7 \\
\hline 2 &100 &7 \\
\hline 6 &101 &7 \\
\hline 4 &110 &7 \\
\hline 5 &111 &7 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=1011$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 1 &010 &7 \\
\hline 2 &100 &7 \\
\hline 3 &011 &7 \\
\hline 4 &110 &7 \\
\hline 5 &111 &7 \\
\hline 6 &101 &7 \\
\hline 7 &001 &1 \\
\hline
\end{tabular}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=1101$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 7 &001 &1 \\
\hline 1 &010 &7 \\
\hline 5 &011 &7 \\
\hline 2 &100 &7 \\
\hline 3 &101 &7 \\
\hline 6 &110 &7 \\
\hline 4 &111 &7 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=1101$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 1 &010 &7 \\
\hline 2 &100 &7 \\
\hline 3 &101 &7 \\
\hline 4 &111 &7 \\
\hline 5 &011 &7 \\
\hline 6 &110 &7 \\
\hline 7 &001 &1 \\
\hline
\end{tabular}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=10011$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 15 & 0001 &  1 \\
\hline  1 & 0010 & 15 \\
\hline  4 & 0011 & 15 \\
\hline  2 & 0100 & 15 \\
\hline  8 & 0101 & 15 \\
\hline  5 & 0110 &  3 \\
\hline 10 & 0111 &  3 \\
\hline  3 & 1000 &  5 \\
\hline 14 & 1001 & 15 \\
\hline  9 & 1010 &  5 \\
\hline  7 & 1011 & 15 \\
\hline  6 & 1100 &  5 \\
\hline 13 & 1101 & 15 \\
\hline 11 & 1110 & 15 \\
\hline 12 & 1111 &  5 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=10011$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline  1 & 0010 & 15 \\
\hline  2 & 0100 & 15 \\
\hline  3 & 1000 &  5 \\
\hline  4 & 0011 & 15 \\
\hline  5 & 0110 &  3 \\
\hline  6 & 1100 &  5 \\
\hline  7 & 1011 & 15 \\
\hline  8 & 0101 & 15 \\
\hline  9 & 1010 &  5 \\
\hline 10 & 0111 &  3 \\
\hline 11 & 1110 & 15 \\
\hline 12 & 1111 &  5 \\
\hline 13 & 1101 & 15 \\
\hline 14 & 1001 & 15 \\
\hline 15 & 0001 &  1 \\
\hline
\end{tabular}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=11001$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 15 & 0001 &  1 \\
\hline  1 & 0010 & 15 \\
\hline 12 & 0011 &  5 \\
\hline  2 & 0100 & 15 \\
\hline  9 & 0101 &  5 \\
\hline 13 & 0110 & 15 \\
\hline  7 & 0111 & 15 \\
\hline  3 & 1000 &  5 \\
\hline  4 & 1001 & 15 \\
\hline 10 & 1010 &  3 \\
\hline  5 & 1011 &  3 \\
\hline 14 & 1100 & 15 \\
\hline 11 & 1101 & 15 \\
\hline  8 & 1110 & 15 \\
\hline  6 & 1111 &  5 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=11001$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline  1 & 0010 & 15 \\
\hline  2 & 0100 & 15 \\
\hline  3 & 1000 &  5 \\
\hline  4 & 1001 & 15 \\
\hline  5 & 1011 &  3 \\
\hline  6 & 1111 &  5 \\
\hline  7 & 0111 & 15 \\
\hline  8 & 1110 & 15 \\
\hline  9 & 0101 &  5 \\
\hline 10 & 1010 &  3 \\
\hline 11 & 1101 & 15 \\
\hline 12 & 0011 &  5 \\
\hline 13 & 0110 & 15 \\
\hline 14 & 1100 & 15 \\
\hline 15 & 0001 &  1 \\
\hline
\end{tabular}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=11111$, $g=11$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 15 & 0001 &  1 \\
\hline 12 & 0010 &  5 \\
\hline  1 & 0011 & 15 \\
\hline  9 & 0100 &  5 \\
\hline  2 & 0101 & 15 \\
\hline 13 & 0110 & 15 \\
\hline  7 & 0111 & 15 \\
\hline  6 & 1000 &  5 \\
\hline  8 & 1001 & 15 \\
\hline 14 & 1010 & 15 \\
\hline 11 & 1011 & 15 \\
\hline 10 & 1100 &  3 \\
\hline  5 & 1101 &  3 \\
\hline  4 & 1110 & 15 \\
\hline  3 & 1111 &  5 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=11111$, $g=11$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline  1 & 0011 & 15 \\
\hline  2 & 0101 & 15 \\
\hline  3 & 1111 &  5 \\
\hline  4 & 1110 & 15 \\
\hline  5 & 1101 &  3 \\
\hline  6 & 1000 &  5 \\
\hline  7 & 0111 & 15 \\
\hline  8 & 1001 & 15 \\
\hline  9 & 0100 &  5 \\
\hline 10 & 1100 &  3 \\
\hline 11 & 1011 & 15 \\
\hline 12 & 0010 &  5 \\
\hline 13 & 0110 & 15 \\
\hline 14 & 1010 & 15 \\
\hline 15 & 0001 &  1 \\
\hline
\end{tabular}

%% ================================================================
\newpage
\section{Storage representations}

We've already seen a few different ways to represent elements of finite fields,
using the canonical embodiment $\F_p[x]/\langle r(x) \rangle$:

\begin{itemize}
\item As equivalence classes of remainders mod $r$, e.g.
	$x^2 + x + \langle x^4 + x + 1 \rangle$.
\item As $\F_p[u] \cong \F_p[x] / \langle r(x) \rangle$, with $u$ a root
	of $r(x)$, e.g. $u^2 + u$.
\item As an array or $n$-tuple of coefficients, e.g. $[0,1,1,0]$ or $(0,1,1,0)$
	but usually written just $0110$.
\end{itemize}

There are some other notations that are also encountered in the literature:

\begin{itemize}
\item As logarithms, as discussed above.  This is sometimes referred to as the
	``log domain''.  It leaves you with the question of how to write 0,
	which doesn't have a log.
\item We can treat an $n$-tuple of coefficients as a base-$p$ integer, then
	convert bases from $p$ to 10.  E.g. elements of $\F_{2^4}$ would then
	convert from $0000$, $0001$, $0010$, \ldots, $1111$ to 0, 1, 2, \ldots,
	15.  Since this is decimal, it looks confusingly like arithmetic mod
	$p^n$ but of course, unless $n=1$, it's not (which is one reason I
	don't like this notation).
\item For base $p=2$, engineers often use base-16 or \emph{hexadecimal}
	notation.  For digits, use 0-9 for 0-9 and a-f (or A-F, depending on
	personal preference) for 11-15; prefix with 0x to distinguish from
	decimal.  E.g. $1010$ is 10 in decimal, which is 0xa in hex.  Likewise,
	$10101110$ is 0xae in hex.  The three monic irreducibles in $\F_{2^4}$
	are written 0x13, 0x19 and 0x1f; 0x104c11db7 is a degree-32
	irreducible, primitive polynomial in $\F_2[x]$ (which incidentally is
	used for error detection in Ethernet networking); the AES polynomial
	\cite{bib:aes} is 0x11b.
\end{itemize}

%% ================================================================
\newpage
\section{Computing with finite fields in GP}
\label{appx:gp_in_Fpx}

If you haven't guessed by now, even though all the methods presented in this
paper can be done by hand, it quickly gets tedious even with the assistance of
tables.  It can become more entertaining, however, if you let a machine do the
repetitive work (but only after you know how to also do it yourself, with the
machine turned off!).

The computational algebraic number theory package GP \cite{bib:gp} can be used
to compute in finite fields.  (Also you can use Mathematica, Maple, GAP and
probably several other packages.  Here I'll talk about GP.)

As described in \ref{sec:adjoin_u} on page \pageref{sec:adjoin_u}, we use the
equivalence $\F_p[x] / \langle r(x) \rangle \cong \F_p(u)$.  Throughout this
paper I've used the latter; GP uses the former.  I'll show how to convert
notations using GP.

%% ----------------------------------------------------------------
\subsection{$\F_p$ in GP}

Modular arithmetic (modulo integers or polynomials) is implemented in GP
using \texttt{Mod}.  The first argument is a ring element; the second is
a modulus.  The result is the canonical representative of the equivalence
class of the first argument mod the second.  Use \texttt{lift} to lift
back to the containing ring.

\begin{verbatim}
? a=Mod(2,11);

? a
%1 = Mod(2, 11)

? lift(a)
%2 = 2

? lift(a^4)
%3 = 5

? lift(a^5)
%4 = 10

? lift(a^10)
%5 = 1

? lift(1/a)
%6 = 6

? lift(a^-6)
%7 = 5
\end{verbatim}

%% ----------------------------------------------------------------
\subsection{$\F_{p^n}$ in GP}

Specify the polynomial $r(x)$ in $\F_p[x]$ which will be used to define the
finite-field arithmetic.  Multiply by \texttt{Mod(1,p)} to apply the ring
homomorphism from $\Z[x]$ to $\F_p[x]$, or use \texttt{Mod} on each coefficient
to write the polynomial directly in $\F_p[x]$.  Then use \texttt{lift} to
remove clutter for printing.

\begin{verbatim}
? rpoly = (x^6 + x + 1) * Mod(1,2);
\\ Could also write: rpoly = Mod(1,2) * x^6 + Mod(1,2) * x + Mod(1,2)

? polisirreducible(rpoly)
%1 = 1

? rpoly
%2 = Mod(1, 2)*x^6 + Mod(1, 2)*x + Mod(1, 2)

? lift(rpoly)
%3 = x^6 + x + 1
\end{verbatim}

Next, create an element of the finite field as follows: use \texttt{Mod} again
to signify reduction mod $r$.  Use \texttt{lift} twice for printing:  once to
get past the polynomial mod, and again to lift the coefficients.  Then use
\texttt{subst} to convert to $u$ notation.  (This is not only due to personal
preference: it also makes the output much easier to read.)

\begin{verbatim}
? a = Mod(Mod(1,2)*x^3+x, rpoly)
%4 = Mod(Mod(1, 2)*x^3 + Mod(1, 2)*x, Mod(1, 2)*x^6 + Mod(1, 2)*x + Mod(1, 2))

? uprint(f) = subst(lift(lift(f)), x, u);

? uprint(a)
%5 = u^3 + u

? uprint(a^2)
%6 = u^2 + u + 1

? uprint(a^3)
%7 = u^5 + u^4 + u^2 + u

? uprint(1/a)
%8 = u^5 + u^4 + u^2

? uprint(a^63)
%9 = 1
\end{verbatim}

%% ----------------------------------------------------------------
\subsection{Multiple extensions in GP}

Note:  The presentation in this section uses the notation of section
\ref{sec:f26_gal_corresp} on page \pageref{sec:f26_gal_corresp}.

To review, we have the following sequence of rings and fields when
we construct a multiple extension:

\begin{itemize}
\item The integer ring $\Z$
\item The field $\F_p = \Z / \langle p \rangle$
\item The polynomial ring $\F_p[x]$
\item The field $\F_p[x]/\langle r_1(x) \rangle = \F_p(\alpha)$
	where $\alpha$ is a root of $r_1(x)$
\item The polynomial ring $\F_p(\alpha)[y]$
\item The field $\F_p(\alpha)[y] / \langle r_2(y) \rangle
	= \F_p(\alpha)(\beta)$ where $\beta$ is a root of $r_2(y)$
\end{itemize}

A mod operation is used each time we pass from a ring to a field, where the
modulus is irreducible (e.g. $p$, $r_1(x)$, $r_2(y)$).  Thus, for double
extensions there will be three mods.

Also note that GP (as of this writing, namely, version 2.2.6) does not
implement multivariate polynomials per se, of the form $F[x,y]$.  Rather, it
implements them in the form $F[x][y]$:  polynomials with coefficients in $y$,
whose coefficients are polynomials in $x$.  To tell GP which variable comes
first, type e.g. \texttt{x;y;}.  or \texttt{y;x;}.  (However, GP always
defines \texttt{x} as a variable at startup.)

\begin{verbatim}
d;a; \\ delta and alpha
e;b; \\ epsilon and beta
c;   \\ gamma

p  = 2;

\\ This is the F_{2^6} defined by gamma, with a generator.
rc = Mod(1, p) * (c^6 + c + 1);
gc = Mod(c, rc);

\\ This is the F_{2^6} defined by alpha and delta, with a generator.
ra = Mod(1, p) * (a^2 + a + 1);
rb = Mod(a, ra) * (d^3 + d^2 + a*d + a+1);
gd = Mod(d, rb);

\\ This is the F_{2^6} defined by beta and epsilon, with a generator.
rb = Mod(1, p) * (b^3 + b + 1);
re = Mod(b, rb) * (e^2 + b*e + b^2+b+1);
ge = Mod(e, re);

for (i=0,63,print(i, " ", lift(lift(lift(gc^i)))))
print("");
for (i=0,63,print(i, " ", lift(lift(lift(gd^i)))))
print("");
for (i=0,63,print(i, " ", lift(lift(lift(ge^i)))))
\end{verbatim}

Partial output:

\begin{verbatim}
0 1
1 c
2 c^2
3 c^3
...
61 c^5 + c^4 + 1
62 c^5 + 1
63 1

0 1
1 d
2 d^2
3 d^2 + a*d + (a + 1)
...
61 d^2 + (a + 1)*d
62 a*d^2 + a*d + (a + 1)
63 1

0 1
1 e
2 b*e + (b^2 + b + 1)
3 (b + 1)*e + (b^2 + 1)
...
61 (b^2 + b + 1)*e + 1
62 b^2*e + (b + 1)
63 1
\end{verbatim}

%% ================================================================
\newpage
\begin{thebibliography}{}

\bibitem[AES]{bib:aes}
J.~Daemen and V.~Rijmen.
\newblock {\em The Rijndael Block Cipher}.
\newblock \\ \texttt{csrc.nist.gov/CryptoToolkit/aes/rijndael}.

\bibitem[Ber]{bib:berl}
E.~Berlekamp.
\newblock {\em Algebraic Coding Theory} (revised 1984 edition).
\newblock Aegean Park Press, 1984.

\bibitem[DF]{bib:df}
D.S.~Dummit and R.M.~Foote.
\newblock {\em Abstract Algebra} (2nd ed.).
\newblock John Wiley and Sons, 1999.

\bibitem[GP]{bib:gp}
H.~Cohen, K.~Belebas et al.
\newblock PARI/GP.
\newblock \texttt{pari.math.u-bordeaux.fr}.

\bibitem[Knu1]{bib:knu1}
D.E.~Knuth.
\newblock {\em The Art of Computer Programming, Vol. 1: Fundamental Algorithms}
	(2nd ed.).
\newblock Addison-Wesley, 1973.

\bibitem[LN]{bib:ln}
R.~Lidl and H.~Niederreiter.
\newblock {\em Finite Fields}.
\newblock Cambridge University Press, 1997.

\bibitem[Mur]{bib:murphy}
T.~Murphy.
\newblock {\em Course 373, Finite Fields}.
\newblock \\\texttt{www.maths.tcd.ie/pub/Maths/Courseware/FiniteFields/FiniteFields.pdf}.

\bibitem[Odl]{bib:odlyzko}
A.~Odlyzko.
\newblock {\em Discrete logs: the past and the future}.
\newblock \\\texttt{www.dtc.umn.edu/{\textasciitilde}odlyzko/doc/discrete.logs.future.pdf}.


\bibitem[Sch]{bib:sch}
B.~Schneier
\newblock {\em Applied Cryptography}.
\newblock John Wiley and Sons, 1995.

\end{thebibliography}

%% ----------------------------------------------------------------

\end{document}

%% ================================================================

% xxx to do:

% ? R/C example to use x^4-1 not x^2-1

% ? xxx base-p ints w/ weird arith, plus ordering is lattice, not chain.

% ? zech logs

% char-2 S/W impl w/ XORs, shifts.  Explain e.g. some schn stuff; eth
% example.  bib:  crc32 for dummies.  *EMPH*:  this is a key purpose of
% this paper, to demystify those C snippets.

% LTs:  explain them fully.

%% ================================================================

%F_2      F_2^2             F_2^3             F_2^6
%---      -----             ------            ------
%0000010      1:0       .    1:0     .     .  1:00
%0000011      1:1       .    1:1     .     .  1:01
%0000111      1:2     1:3  1:1:1     .     .  1:3a 1:3b
%0001011  1:0:1:1       .    1:2   1:4   1:6  1:0e 1:17 1:19
%0001101  1:1:0:1       .    1:3   1:5   1:7  1:0f 1:16 1:18
%1000011  1:1:2:3 1:1:3:2  1:2:7 1:4:3 1:6:5  1:02 1:04 1:09 1:0c 1:10 1:13
%1001001  1:0:0:2 1:0:0:3  1:2:1 1:4:1 1:6:1  1:06 1:0b 1:14 1:1a 1:1c 1:1f
%1010111  1:0:2:1 1:0:3:1  1:2:4 1:4:6 1:6:2  1:03 1:05 1:08 1:0d 1:11 1:12
%1011011  1:1:1:2 1:1:1:3  1:2:2 1:4:4 1:6:6  1:07 1:0a 1:15 1:1b 1:1d 1:1e
%1100001  1:2:3:3 1:3:2:2  1:5:6 1:7:2 1:3:4  1:21 1:25 1:27 1:2e 1:31 1:3d
%1100111  1:2:3:2 1:3:2:3  1:5:2 1:7:4 1:3:6  1:20 1:24 1:26 1:2f 1:30 1:3c
%1101101  1:2:2:2 1:3:3:3  1:1:3 1:1:5 1:1:7  1:22 1:23 1:2c 1:2d 1:34 1:35
%1110011  1:2:1:3 1:3:1:2  1:7:5 1:3:7 1:5:3  1:29 1:2a 1:32 1:37 1:38 1:3f
%1110101  1:2:0:1 1:3:0:1  1:7:3 1:3:5 1:5:7  1:28 1:2b 1:33 1:36 1:39 1:3e


%% full equivalence:
%
%% --- -------- ------ -----
%%  1:      1:0    1:0    02
%%  2:    1:0:0    2:7    04
%%  3:    1:2:3    3:5    08
%%  4:    3:1:3    3:2    10
%%  5:    2:2:2    4:2    20
%%  6:      1:1    1:1    03
%%  7:    1:1:0    3:7    06
%%  8:      2:3    1:2    0c
%%  9:    2:3:0      7    18
%% 10:    1:3:1    7:0    30
%% 11:    2:3:3    5:3    23
%% 12:    1:0:1    2:6    05
%% 13:    1:3:3    2:5    0a
%% 14:    2:1:3    1:5    14
%% 15:    3:0:1    7:7    28
%% 16:    3:0:2    2:3    13
%% 17:    3:3:2    7:5    26
%% 18:      3:2      3    0f
%% 19:    3:2:0    3:0    1e
%% 20:    1:1:2    6:2    3c
%% 21:        3    5:4    3b
%% 22:      3:0    5:6    35
%% 23:    3:0:0    7:6    29
%% 24:    3:1:2    3:3    11
%% 25:    2:3:2    5:2    22
%% 26:    1:1:1    3:6    07
%% 27:      3:3      2    0e
%% 28:    3:3:0    2:0    1c
%% 29:      1:2    4:5    38
%% 30:    1:2:0    6:1    33
%% 31:    3:2:3    6:4    25
%% 32:    1:2:2    3:4    09
%% 33:    3:0:3    2:2    12
%% 34:    3:2:2    6:5    24
%% 35:    1:3:2    2:4    0b
%% 36:    2:0:3      5    16
%% 37:    2:0:1    5:0    2c
%% 38:    2:2:1    1:6    1b
%% 39:      2:1    4:7    36
%% 40:    2:1:0    4:1    2f
%% 41:    3:3:1    2:1    1d
%% 42:        2    5:5    3a
%% 43:      2:0    4:6    37
%% 44:    2:0:0    5:1    2d
%% 45:    2:3:1      6    19
%% 46:    1:2:1    6:0    32
%% 47:    3:3:3    7:4    27
%% 48:      2:2    1:3    0d
%% 49:    2:2:0    1:7    1a
%% 50:      3:1    5:7    34
%% 51:    3:1:0    6:6    2b
%% 52:    2:1:2    1:4    15
%% 53:    3:1:1    6:7    2a
%% 54:    2:0:2      4    17
%% 55:    2:1:1    4:0    2e
%% 56:    3:2:1    3:1    1f
%% 57:    1:0:2    7:2    3e
%% 58:    1:0:3    7:3    3f
%% 59:    1:1:3    6:3    3d
%% 60:      1:3    4:4    39
%% 61:    1:3:0    7:1    31
%% 62:    2:2:3    4:3    21
%% 63:        1      1    01

%%----------------------------------------------------------------

%% --:        0      0    00
%% 21:        3    5:4    3b
%% 42:        2    5:5    3a
%% 63:        1      1    01

%% --:        0      0    00
%%  9:    2:3:0      7    18
%% 18:      3:2      3    0f
%% 27:      3:3      2    0e
%% 36:    2:0:3      5    16
%% 45:    2:3:1      6    19
%% 54:    2:0:2      4    17
%% 63:        1      1    01


%% --:       00     000 000000
%% 21:       11 101:100 111011
%% 42:       10 101:101 111010
%% 63:       01     001 000001

%% --:       00     000 000000
%%  9: 10:11:00     111 011000
%% 18:    11:10     011 001111
%% 27:    11:11     010 001110
%% 36: 10:00:11     101 010110
%% 45: 10:11:01     110 011001
%% 54: 10:00:10     100 010111
%% 63:       01     001 000001

%%----------------------------------------------------------------


%% factor univ over f22
%
%%           1:0 --     1:0
%%           1:1 --     1:1
%%         1:1:1 --     1:2     1:3
%%       1:0:1:1 -- 1:0:1:1
%%       1:1:0:1 -- 1:1:0:1
%% 1:0:0:0:0:1:1 -- 1:1:2:3 1:1:3:2
%% 1:0:0:1:0:0:1 -- 1:0:0:2 1:0:0:3
%% 1:0:1:0:1:1:1 -- 1:0:2:1 1:0:3:1
%% 1:0:1:1:0:1:1 -- 1:1:1:2 1:1:1:3
%% 1:1:0:0:0:0:1 -- 1:2:3:3 1:3:2:2
%% 1:1:0:0:1:1:1 -- 1:2:3:2 1:3:2:3
%% 1:1:0:1:1:0:1 -- 1:2:2:2 1:3:3:3
%% 1:1:1:0:0:1:1 -- 1:2:1:3 1:3:1:2
%% 1:1:1:0:1:0:1 -- 1:2:0:1 1:3:0:1

%% then take roots
%
%%       01:00 -- 00  .  . |     0
%%       01:01 -- 01  .  . |     1
%%       01:3a -- 3a  .  . |     2
%%       01:3b -- 3b  .  . |     3
%% 01:00:01:01 -- 0e 17 19 |   3:3 2:0:2 2:3:1
%% 01:01:00:01 -- 0f 16 18 |   3:2 2:0:3 2:3:0
%% 01:01:3a:3b -- 02 10 13 |   1:0 3:1:3 3:0:2
%% 01:01:3b:3a -- 04 09 0c | 1:0:0 1:2:2   2:3
%% 01:00:00:3a -- 0b 14 1f | 1:3:2 2:1:3 3:2:1
%% 01:00:00:3b -- 06 1a 1c | 1:1:0 2:2:0 3:3:0
%% 01:00:3a:01 -- 05 08 0d | 1:0:1 1:2:3   2:2
%% 01:00:3b:01 -- 03 11 12 |   1:1 3:1:2 3:0:3
%% 01:01:01:3a -- 07 1b 1d | 1:1:1 2:2:1 3:3:1
%% 01:01:01:3b -- 0a 15 1e | 1:3:3 2:1:2 3:2:0
%% 01:3a:3b:3b -- 25 2e 31 | 3:2:3 2:1:1 1:3:0
%% 01:3b:3a:3a -- 21 27 3d | 2:2:3 3:3:3 1:1:3
%% 01:3a:3b:3a -- 20 26 3c | 2:2:2 3:3:2 1:1:2
%% 01:3b:3a:3b -- 24 2f 30 | 3:2:2 2:1:0 1:3:1
%% 01:3a:3a:3a -- 23 2d 34 | 2:3:3 2:0:0   3:1
%% 01:3b:3b:3b -- 22 2c 35 | 2:3:2 2:0:1   3:0
%% 01:3a:01:3b -- 32 37 3f | 1:2:1   2:0 1:0:3
%% 01:3b:01:3a -- 29 2a 38 | 3:0:0 3:1:1   1:2
%% 01:3a:00:01 -- 28 2b 39 | 3:0:1 3:1:0   1:3
%% 01:3b:00:01 -- 33 36 3e | 1:2:0   2:1 1:0:2

%% factor univ over f23
%
%%           1:0 --   1:0
%%           1:1 --   1:1
%%         1:1:1 -- 1:1:1
%%       1:0:1:1 --   1:2   1:4   1:6
%%       1:1:0:1 --   1:3   1:5   1:7
%% 1:0:0:0:0:1:1 -- 1:2:7 1:4:3 1:6:5
%% 1:0:0:1:0:0:1 -- 1:2:1 1:4:1 1:6:1
%% 1:0:1:0:1:1:1 -- 1:2:4 1:4:6 1:6:2
%% 1:0:1:1:0:1:1 -- 1:2:2 1:4:4 1:6:6
%% 1:1:0:0:0:0:1 -- 1:5:6 1:7:2 1:3:4
%% 1:1:0:0:1:1:1 -- 1:5:2 1:7:4 1:3:6
%% 1:1:0:1:1:0:1 -- 1:1:3 1:1:5 1:1:7
%% 1:1:1:0:0:1:1 -- 1:7:5 1:3:7 1:5:3
%% 1:1:1:0:1:0:1 -- 1:7:3 1:3:5 1:5:7

%% then take roots
%
%%    01:00 -- 00    |    0
%%    01:01 -- 01    |    1
%% 01:01:01 -- 3a 3b |  5:5  5:4
%%    01:0e -- 0e    |    2
%%    01:17 -- 17    |    4
%%    01:19 -- 19    |    6
%%    01:0f -- 0f    |    3
%%    01:16 -- 16    |    5
%%    01:18 -- 18    |    7
%% 01:0e:18 -- 02 0c | 1:0 1:2
%% 01:17:0f -- 04 13 | 2:7 2:3
%% 01:19:16 -- 09 10 | 3:4 3:2
%% 01:0e:01 -- 14 1a | 1:5 1:7
%% 01:17:01 -- 0b 1c | 2:4 2:0
%% 01:19:01 -- 06 1f | 3:7 3:1
%% 01:0e:17 -- 03 0d | 1:1 1:3
%% 01:17:19 -- 05 12 | 2:6 2:2
%% 01:19:0e -- 08 11 | 3:5 3:3
%% 01:0e:0e -- 15 1b | 1:4 1:6
%% 01:17:17 -- 0a 1d | 2:5 2:1
%% 01:19:19 -- 07 1e | 3:6 3:0
%% 01:16:19 -- 27 31 | 7:4 7:1
%% 01:18:0e -- 25 3d | 6:4 6:3
%% 01:0f:17 -- 21 2e | 4:1 4:0
%% 01:16:0e -- 26 30 | 7:5 7:0
%% 01:18:17 -- 24 3c | 6:5 6:2
%% 01:0f:19 -- 20 2f | 4:2 4:1
%% 01:01:0f -- 2c 2d | 5:0 5:1
%% 01:01:16 -- 22 23 | 5:2 5:3
%% 01:01:18 -- 34 35 | 5:7 5:6
%% 01:18:16 -- 2a 32 | 6:7 6:0
%% 01:0f:18 -- 37 38 | 4:6 4:5
%% 01:16:0f -- 29 3f | 7:6 7:3
%% 01:18:0f -- 2b 33 | 6:6 6:1
%% 01:0f:16 -- 36 39 | 4:7 4:4
%% 01:16:18 -- 28 3e | 7:7 7:2

%%                01:00 -- 00
%%                01:01 -- 01
%%             01:01:01 -- 3a 3b
%%          01:00:01:01 -- 0e 17 19
%%          01:01:00:01 -- 0f 16 18
%% 01:00:00:00:00:01:01 -- 02 04 09 0c 10 13
%% 01:00:00:01:00:00:01 -- 06 0b 14 1a 1c 1f
%% 01:00:01:00:01:01:01 -- 03 05 08 0d 11 12
%% 01:00:01:01:00:01:01 -- 07 0a 15 1b 1d 1e
%% 01:01:00:00:00:00:01 -- 21 25 27 2e 31 3d
%% 01:01:00:00:01:01:01 -- 20 24 26 2f 30 3c
%% 01:01:00:01:01:00:01 -- 22 23 2c 2d 34 35
%% 01:01:01:00:00:01:01 -- 29 2a 32 37 38 3f
%% 01:01:01:00:01:00:01 -- 28 2b 33 36 39 3e

%% ================================================================

%F_2      F_2^2             F_2^3             F_2^6
%---      -----             ------            ------
%0000010      1:0       .    1:0     .     .  1:00
%0000011      1:1       .    1:1     .     .  1:01
%0000111      1:2     1:3  1:1:1     .     .  1:3a 1:3b
%0001011  1:0:1:1       .    1:2   1:4   1:6  1:0e 1:17 1:19
%0001101  1:1:0:1       .    1:3   1:5   1:7  1:0f 1:16 1:18
%1000011  1:1:2:3 1:1:3:2  1:2:7 1:4:3 1:6:5  1:02 1:04 1:09 1:0c 1:10 1:13
%1001001  1:0:0:2 1:0:0:3  1:2:1 1:4:1 1:6:1  1:06 1:0b 1:14 1:1a 1:1c 1:1f
%1010111  1:0:2:1 1:0:3:1  1:2:4 1:4:6 1:6:2  1:03 1:05 1:08 1:0d 1:11 1:12
%1011011  1:1:1:2 1:1:1:3  1:2:2 1:4:4 1:6:6  1:07 1:0a 1:15 1:1b 1:1d 1:1e
%1100001  1:2:3:3 1:3:2:2  1:5:6 1:7:2 1:3:4  1:21 1:25 1:27 1:2e 1:31 1:3d
%1100111  1:2:3:2 1:3:2:3  1:5:2 1:7:4 1:3:6  1:20 1:24 1:26 1:2f 1:30 1:3c
%1101101  1:2:2:2 1:3:3:3  1:1:3 1:1:5 1:1:7  1:22 1:23 1:2c 1:2d 1:34 1:35
%1110011  1:2:1:3 1:3:1:2  1:7:5 1:3:7 1:5:3  1:29 1:2a 1:32 1:37 1:38 1:3f
%1110101  1:2:0:1 1:3:0:1  1:7:3 1:3:5 1:5:7  1:28 1:2b 1:33 1:36 1:39 1:3e

%% factor univ over f22      %% then take roots
%                            %
%%           1:0 --     1:0  |     0
%%           1:1 --     1:1  |     1
%%         1:1:1 --     1:2  |     2
%%                      1:3  |     3
%%       1:0:1:1 -- 1:0:1:1  |   3:3 2:0:2 2:3:1
%%       1:1:0:1 -- 1:1:0:1  |   3:2 2:0:3 2:3:0
%% 1:0:0:0:0:1:1 -- 1:1:2:3  |   1:0 3:1:3 3:0:2
%%                  1:1:3:2  | 1:0:0 1:2:2   2:3
%% 1:0:0:1:0:0:1 -- 1:0:0:2  | 1:3:2 2:1:3 3:2:1
%%                  1:0:0:3  | 1:1:0 2:2:0 3:3:0
%% 1:0:1:0:1:1:1 -- 1:0:2:1  | 1:0:1 1:2:3   2:2
%%                  1:0:3:1  |   1:1 3:1:2 3:0:3
%% 1:0:1:1:0:1:1 -- 1:1:1:2  | 1:1:1 2:2:1 3:3:1
%%                  1:1:1:3  | 1:3:3 2:1:2 3:2:0
%% 1:1:0:0:0:0:1 -- 1:2:3:3  | 3:2:3 2:1:1 1:3:0
%%                  1:3:2:2  | 2:2:3 3:3:3 1:1:3
%% 1:1:0:0:1:1:1 -- 1:2:3:2  | 2:2:2 3:3:2 1:1:2
%%                  1:3:2:3  | 3:2:2 2:1:0 1:3:1
%% 1:1:0:1:1:0:1 -- 1:2:2:2  | 2:3:3 2:0:0   3:1
%%                  1:3:3:3  | 2:3:2 2:0:1   3:0
%% 1:1:1:0:0:1:1 -- 1:2:1:3  | 1:2:1   2:0 1:0:3
%%                  1:3:1:2  | 3:0:0 3:1:1   1:2
%% 1:1:1:0:1:0:1 -- 1:2:0:1  | 3:0:1 3:1:0   1:3
%%                  1:3:0:1  | 1:2:0   2:1 1:0:2
%% factor univ over f23    %% then take roots
%                          %
%%           1:0 --   1:0  |    0
%%           1:1 --   1:1  |    1
%%         1:1:1 -- 1:1:1  |  5:5  5:4
%%       1:0:1:1 --   1:2  |    2
%%                    1:4  |    4
%%                    1:6  |    6
%%       1:1:0:1 --   1:3  |    3
%%                    1:5  |    5
%%                    1:7  |    7
%% 1:0:0:0:0:1:1 -- 1:2:7  | 1:0 1:2
%%                  1:4:3  | 2:7 2:3
%%                  1:6:5  | 3:4 3:2
%% 1:0:0:1:0:0:1 -- 1:2:1  | 1:5 1:7
%%                  1:4:1  | 2:4 2:0
%%                  1:6:1  | 3:7 3:1
%% 1:0:1:0:1:1:1 -- 1:2:4  | 1:1 1:3
%%                  1:4:6  | 2:6 2:2
%%                  1:6:2  | 3:5 3:3
%% 1:0:1:1:0:1:1 -- 1:2:2  | 1:4 1:6
%%                  1:4:4  | 2:5 2:1
%%                  1:6:6  | 3:6 3:0
%% 1:1:0:0:0:0:1 -- 1:5:6  | 7:4 7:1
%%                  1:7:2  | 6:4 6:3
%%                  1:3:4  | 4:1 4:0
%% 1:1:0:0:1:1:1 -- 1:5:2  | 7:5 7:0
%%                  1:7:4  | 6:5 6:2
%%                  1:3:6  | 4:2 4:1
%% 1:1:0:1:1:0:1 -- 1:1:3  | 5:0 5:1
%%                  1:1:5  | 5:2 5:3
%%                  1:1:7  | 5:7 5:6
%% 1:1:1:0:0:1:1 -- 1:7:5  | 6:7 6:0
%%                  1:3:7  | 4:6 4:5
%%                  1:5:3  | 7:6 7:3
%% 1:1:1:0:1:0:1 -- 1:7:3  | 6:6 6:1
%%                  1:3:5  | 4:7 4:4
%%                  1:5:7  | 7:7 7:2

%%                01:00 -- 00
%%                01:01 -- 01
%%             01:01:01 -- 3a
%%                         3b
%%          01:00:01:01 -- 0e
%%                         17
%%                         19
%%          01:01:00:01 -- 0f
%%                         16
%%                         18
%% 01:00:00:00:00:01:01 -- 02
%%                         04
%%                         09
%%                         0c
%%                         10
%%                         13
%% 01:00:00:01:00:00:01 -- 06
%%                         0b
%%                         14
%%                         1a
%%                         1c
%%                         1f
%% 01:00:01:00:01:01:01 -- 03
%%                         05
%%                         08
%%                         0d
%%                         11
%%                         12
%% 01:00:01:01:00:01:01 -- 07
%%                         0a
%%                         15
%%                         1b
%%                         1d
%%                         1e
%% 01:01:00:00:00:00:01 -- 21
%%                         25
%%                         27
%%                         2e
%%                         31
%%                         3d
%% 01:01:00:00:01:01:01 -- 20
%%                         24
%%                         26
%%                         2f
%%                         30
%%                         3c
%% 01:01:00:01:01:00:01 -- 22
%%                         23
%%                         2c
%%                         2d
%%                         34
%%                         35
%% 01:01:01:00:00:01:01 -- 29
%%                         2a
%%                         32
%%                         37
%%                         38
%%                         3f
%% 01:01:01:00:01:00:01 -- 28
%%                         2b
%%                         33
%%                         36
%%                         39
%%                         3e

%% ================================================================

%% factor univ over f22      %% then take roots
%                            %
%%           1:0 --     1:0  |     0
%%           1:1 --     1:1  |     1
%%         1:1:1 --     1:2  |     2
%%                      1:3  |     3
%%       1:0:1:1 -- 1:0:1:1  |   3:3 2:0:2 2:3:1
%%
%%
%%       1:1:0:1 -- 1:1:0:1  |   3:2 2:0:3 2:3:0
%%
%%
%% 1:0:0:0:0:1:1 -- 1:1:2:3  |   1:0 3:1:3 3:0:2
%%                  1:1:3:2  | 1:0:0 1:2:2   2:3
%%
%%
%%
%%
%% 1:0:0:1:0:0:1 -- 1:0:0:2  | 1:3:2 2:1:3 3:2:1
%%                  1:0:0:3  | 1:1:0 2:2:0 3:3:0
%%
%%
%%
%%
%% 1:0:1:0:1:1:1 -- 1:0:2:1  | 1:0:1 1:2:3   2:2
%%                  1:0:3:1  |   1:1 3:1:2 3:0:3
%%
%%
%%
%%
%% 1:0:1:1:0:1:1 -- 1:1:1:2  | 1:1:1 2:2:1 3:3:1
%%                  1:1:1:3  | 1:3:3 2:1:2 3:2:0
%%
%%
%%
%%
%% 1:1:0:0:0:0:1 -- 1:2:3:3  | 3:2:3 2:1:1 1:3:0
%%                  1:3:2:2  | 2:2:3 3:3:3 1:1:3
%%
%%
%%
%%
%% 1:1:0:0:1:1:1 -- 1:2:3:2  | 2:2:2 3:3:2 1:1:2
%%                  1:3:2:3  | 3:2:2 2:1:0 1:3:1
%%
%%
%%
%%
%% 1:1:0:1:1:0:1 -- 1:2:2:2  | 2:3:3 2:0:0   3:1
%%                  1:3:3:3  | 2:3:2 2:0:1   3:0
%%
%%
%%
%%
%% 1:1:1:0:0:1:1 -- 1:2:1:3  | 1:2:1   2:0 1:0:3
%%                  1:3:1:2  | 3:0:0 3:1:1   1:2
%%
%%
%%
%%
%% 1:1:1:0:1:0:1 -- 1:2:0:1  | 3:0:1 3:1:0   1:3
%%                  1:3:0:1  | 1:2:0   2:1 1:0:2
%%
%%
%%
%%

%% factor univ over f23    %% then take roots
%                          %
%%           1:0 --   1:0  |    0
%%           1:1 --   1:1  |    1
%%         1:1:1 -- 1:1:1  |  5:5  5:4
%%
%%       1:0:1:1 --   1:2  |    2
%%                    1:4  |    4
%%                    1:6  |    6
%%       1:1:0:1 --   1:3  |    3
%%                    1:5  |    5
%%                    1:7  |    7
%% 1:0:0:0:0:1:1 -- 1:2:7  | 1:0 1:2
%%                  1:4:3  | 2:7 2:3
%%                  1:6:5  | 3:4 3:2
%%
%%
%%
%% 1:0:0:1:0:0:1 -- 1:2:1  | 1:5 1:7
%%                  1:4:1  | 2:4 2:0
%%                  1:6:1  | 3:7 3:1
%%
%%
%%
%% 1:0:1:0:1:1:1 -- 1:2:4  | 1:1 1:3
%%                  1:4:6  | 2:6 2:2
%%                  1:6:2  | 3:5 3:3
%%
%%
%%
%% 1:0:1:1:0:1:1 -- 1:2:2  | 1:4 1:6
%%                  1:4:4  | 2:5 2:1
%%                  1:6:6  | 3:6 3:0
%%
%%
%%
%% 1:1:0:0:0:0:1 -- 1:5:6  | 7:4 7:1
%%                  1:7:2  | 6:4 6:3
%%                  1:3:4  | 4:1 4:0
%%
%%
%%
%% 1:1:0:0:1:1:1 -- 1:5:2  | 7:5 7:0
%%                  1:7:4  | 6:5 6:2
%%                  1:3:6  | 4:2 4:1
%%
%%
%%
%% 1:1:0:1:1:0:1 -- 1:1:3  | 5:0 5:1
%%                  1:1:5  | 5:2 5:3
%%                  1:1:7  | 5:7 5:6
%%
%%
%%
%% 1:1:1:0:0:1:1 -- 1:7:5  | 6:7 6:0
%%                  1:3:7  | 4:6 4:5
%%                  1:5:3  | 7:6 7:3
%%
%%
%%
%% 1:1:1:0:1:0:1 -- 1:7:3  | 6:6 6:1
%%                  1:3:5  | 4:7 4:4
%%                  1:5:7  | 7:7 7:2
%%
%%
%%

%%                01:00 -- 00
%%                01:01 -- 01
%%             01:01:01 -- 3a
%%                         3b
%%          01:00:01:01 -- 0e
%%                         17
%%                         19
%%          01:01:00:01 -- 0f
%%                         16
%%                         18
%% 01:00:00:00:00:01:01 -- 02
%%                         04
%%                         09
%%                         0c
%%                         10
%%                         13
%% 01:00:00:01:00:00:01 -- 06
%%                         0b
%%                         14
%%                         1a
%%                         1c
%%                         1f
%% 01:00:01:00:01:01:01 -- 03
%%                         05
%%                         08
%%                         0d
%%                         11
%%                         12
%% 01:00:01:01:00:01:01 -- 07
%%                         0a
%%                         15
%%                         1b
%%                         1d
%%                         1e
%% 01:01:00:00:00:00:01 -- 21
%%                         25
%%                         27
%%                         2e
%%                         31
%%                         3d
%% 01:01:00:00:01:01:01 -- 20
%%                         24
%%                         26
%%                         2f
%%                         30
%%                         3c
%% 01:01:00:01:01:00:01 -- 22
%%                         23
%%                         2c
%%                         2d
%%                         34
%%                         35
%% 01:01:01:00:00:01:01 -- 29
%%                         2a
%%                         32
%%                         37
%%                         38
%%                         3f
%% 01:01:01:00:01:00:01 -- 28
%%                         2b
%%                         33
%%                         36
%%                         39
%%                         3e


%% ================================================================

%%           1:0 |     1:0  -     0             |   1:0 -   0     | 00
%%           1:1 |     1:1  -     1             |   1:1 -   1     | 01
%%         1:1:1 |     1:2  -     2             | 1:1:1 - 5:5 5:4 | 3a
%%               |     1:3  -     3             |       -         | 3b
%%       1:0:1:1 | 1:0:1:1  -   3:3 2:0:2 2:3:1 |   1:2 -   2     | 0e
%%               |          -                   |   1:4 -   4     | 17
%%               |          -                   |   1:6 -   6     | 19
%%       1:1:0:1 | 1:1:0:1  -   3:2 2:0:3 2:3:0 |   1:3 -   3     | 0f
%%               |          -                   |   1:5 -   5     | 16
%%               |          -                   |   1:7 -   7     | 18
%% 1:0:0:0:0:1:1 | 1:1:2:3  -   1:0 3:1:3 3:0:2 | 1:2:7 - 1:0 1:2 | 02
%%               | 1:1:3:2  - 1:0:0 1:2:2   2:3 | 1:4:3 - 2:7 2:3 | 04
%%               |          -                   | 1:6:5 - 3:4 3:2 | 09
%%               |          -                   |       -         | 0c
%%               |          -                   |       -         | 10
%%               |          -                   |       -         | 13
%% 1:0:0:1:0:0:1 | 1:0:0:2  - 1:3:2 2:1:3 3:2:1 | 1:2:1 - 1:5 1:7 | 06
%%               | 1:0:0:3  - 1:1:0 2:2:0 3:3:0 | 1:4:1 - 2:4 2:0 | 0b
%%               |          -                   | 1:6:1 - 3:7 3:1 | 14
%%               |          -                   |       -         | 1a
%%               |          -                   |       -         | 1c
%%               |          -                   |       -         | 1f
%% 1:0:1:0:1:1:1 | 1:0:2:1  - 1:0:1 1:2:3   2:2 | 1:2:4 - 1:1 1:3 | 03
%%               | 1:0:3:1  -   1:1 3:1:2 3:0:3 | 1:4:6 - 2:6 2:2 | 05
%%               |          -                   | 1:6:2 - 3:5 3:3 | 08
%%               |          -                   |       -         | 0d
%%               |          -                   |       -         | 11
%%               |          -                   |       -         | 12
%% 1:0:1:1:0:1:1 | 1:1:1:2  - 1:1:1 2:2:1 3:3:1 | 1:2:2 - 1:4 1:6 | 07
%%               | 1:1:1:3  - 1:3:3 2:1:2 3:2:0 | 1:4:4 - 2:5 2:1 | 0a
%%               |          -                   | 1:6:6 - 3:6 3:0 | 15
%%               |          -                   |       -         | 1b
%%               |          -                   |       -         | 1d
%%               |          -                   |       -         | 1e
%% 1:1:0:0:0:0:1 | 1:2:3:3  - 3:2:3 2:1:1 1:3:0 | 1:5:6 - 7:4 7:1 | 21
%%               | 1:3:2:2  - 2:2:3 3:3:3 1:1:3 | 1:7:2 - 6:4 6:3 | 25
%%               |          -                   | 1:3:4 - 4:1 4:0 | 27
%%               |          -                   |       -         | 2e
%%               |          -                   |       -         | 31
%%               |          -                   |       -         | 3d
%% 1:1:0:0:1:1:1 | 1:2:3:2  - 2:2:2 3:3:2 1:1:2 | 1:5:2 - 7:5 7:0 | 20
%%               | 1:3:2:3  - 3:2:2 2:1:0 1:3:1 | 1:7:4 - 6:5 6:2 | 24
%%               |          -                   | 1:3:6 - 4:2 4:1 | 26
%%               |          -                   |       -         | 2f
%%               |          -                   |       -         | 30
%%               |          -                   |       -         | 3c
%% 1:1:0:1:1:0:1 | 1:2:2:2  - 2:3:3 2:0:0   3:1 | 1:1:3 - 5:0 5:1 | 22
%%               | 1:3:3:3  - 2:3:2 2:0:1   3:0 | 1:1:5 - 5:2 5:3 | 23
%%               |          -                   | 1:1:7 - 5:7 5:6 | 2c
%%               |          -                   |       -         | 2d
%%               |          -                   |       -         | 34
%%               |          -                   |       -         | 35
%% 1:1:1:0:0:1:1 | 1:2:1:3  - 1:2:1   2:0 1:0:3 | 1:7:5 - 6:7 6:0 | 29
%%               | 1:3:1:2  - 3:0:0 3:1:1   1:2 | 1:3:7 - 4:6 4:5 | 2a
%%               |          -                   | 1:5:3 - 7:6 7:3 | 32
%%               |          -                   |       -         | 37
%%               |          -                   |       -         | 38
%%               |          -                   |       -         | 3f
%% 1:1:1:0:1:0:1 | 1:2:0:1  - 3:0:1 3:1:0   1:3 | 1:7:3 - 6:6 6:1 | 28
%%               | 1:3:0:1  - 1:2:0   2:1 1:0:2 | 1:3:5 - 4:7 4:4 | 2b
%%               |          -                   | 1:5:7 - 7:7 7:2 | 33
%%               |          -                   |       -         | 36
%%               |          -                   |       -         | 39
%%               |                              |       -         | 3e

%% ================================================================

%%      10 |     1:0 -     0             |   1:0 -   0     | 00
%%      11 |     1:1 -     1             |   1:1 -   1     | 01
%
%%     111 |     1:2 -     2             | 1:1:1 - 5:5 5:4 | 3a
%%         |     1:3 -     3             |       -         | 3b
%
%%    1011 | 1:0:1:1 -   3:3 2:0:2 2:3:1 |   1:2 -   2     | 0e
%%         |         -                   |   1:4 -   4     | 17
%%         |         -                   |   1:6 -   6     | 19
%%    1101 | 1:1:0:1 -   3:2 2:0:3 2:3:0 |   1:3 -   3     | 0f
%%         |         -                   |   1:5 -   5     | 16
%%         |         -                   |   1:7 -   7     | 18
%
%% 1000011 | 1:1:2:3 -   1:0 3:1:3 3:0:2 | 1:2:7 - 1:0 1:2 | 02
%%         | 1:1:3:2 - 1:0:0 1:2:2   2:3 | 1:4:3 - 2:7 2:3 | 04
%%         |         -                   | 1:6:5 - 3:4 3:2 | 09
%%         |         -                   |       -         | 0c
%%         |         -                   |       -         | 10
%%         |         -                   |       -         | 13
%% 1001001 | 1:0:0:2 - 1:3:2 2:1:3 3:2:1 | 1:2:1 - 1:5 1:7 | 06
%%         | 1:0:0:3 - 1:1:0 2:2:0 3:3:0 | 1:4:1 - 2:4 2:0 | 0b
%%         |         -                   | 1:6:1 - 3:7 3:1 | 14
%%         |         -                   |       -         | 1a
%%         |         -                   |       -         | 1c
%%         |         -                   |       -         | 1f
%% 1010111 | 1:0:2:1 - 1:0:1 1:2:3   2:2 | 1:2:4 - 1:1 1:3 | 03
%%         | 1:0:3:1 -   1:1 3:1:2 3:0:3 | 1:4:6 - 2:6 2:2 | 05
%%         |         -                   | 1:6:2 - 3:5 3:3 | 08
%%         |         -                   |       -         | 0d
%%         |         -                   |       -         | 11
%%         |         -                   |       -         | 12
%% 1011011 | 1:1:1:2 - 1:1:1 2:2:1 3:3:1 | 1:2:2 - 1:4 1:6 | 07
%%         | 1:1:1:3 - 1:3:3 2:1:2 3:2:0 | 1:4:4 - 2:5 2:1 | 0a
%%         |         -                   | 1:6:6 - 3:6 3:0 | 15
%%         |         -                   |       -         | 1b
%%         |         -                   |       -         | 1d
%%         |         -                   |       -         | 1e
%% 1100001 | 1:2:3:3 - 3:2:3 2:1:1 1:3:0 | 1:5:6 - 7:4 7:1 | 21
%%         | 1:3:2:2 - 2:2:3 3:3:3 1:1:3 | 1:7:2 - 6:4 6:3 | 25
%%         |         -                   | 1:3:4 - 4:1 4:0 | 27
%%         |         -                   |       -         | 2e
%%         |         -                   |       -         | 31
%%         |         -                   |       -         | 3d
%% 1100111 | 1:2:3:2 - 2:2:2 3:3:2 1:1:2 | 1:5:2 - 7:5 7:0 | 20
%%         | 1:3:2:3 - 3:2:2 2:1:0 1:3:1 | 1:7:4 - 6:5 6:2 | 24
%%         |         -                   | 1:3:6 - 4:2 4:1 | 26
%%         |         -                   |       -         | 2f
%%         |         -                   |       -         | 30
%%         |         -                   |       -         | 3c
%% 1101101 | 1:2:2:2 - 2:3:3 2:0:0   3:1 | 1:1:3 - 5:0 5:1 | 22
%%         | 1:3:3:3 - 2:3:2 2:0:1   3:0 | 1:1:5 - 5:2 5:3 | 23
%%         |         -                   | 1:1:7 - 5:7 5:6 | 2c
%%         |         -                   |       -         | 2d
%%         |         -                   |       -         | 34
%%         |         -                   |       -         | 35
%% 1110011 | 1:2:1:3 - 1:2:1   2:0 1:0:3 | 1:7:5 - 6:7 6:0 | 29
%%         | 1:3:1:2 - 3:0:0 3:1:1   1:2 | 1:3:7 - 4:6 4:5 | 2a
%%         |         -                   | 1:5:3 - 7:6 7:3 | 32
%%         |         -                   |       -         | 37
%%         |         -                   |       -         | 38
%%         |         -                   |       -         | 3f
%% 1110101 | 1:2:0:1 - 3:0:1 3:1:0   1:3 | 1:7:3 - 6:6 6:1 | 28
%%         | 1:3:0:1 - 1:2:0   2:1 1:0:2 | 1:3:5 - 4:7 4:4 | 2b
%%         |         -                   | 1:5:7 - 7:7 7:2 | 33
%%         |         -                   |       -         | 36
%%         |         -                   |       -         | 3e

%% 63:        1      1    01

%% 42:        2    5:5    3a
%% 21:        3    5:4    3b

%% 27:      3:3      2    0e
%% 54:    2:0:2      4    17
%% 45:    2:3:1      6    19

%% 18:      3:2      3    0f
%% 36:    2:0:3      5    16
%%  9:    2:3:0      7    18

%%  1:      1:0    1:0    02
%%  2:    1:0:0    2:7    04
%% 32:    1:2:2    3:4    09
%%  8:      2:3    1:2    0c
%%  4:    3:1:3    3:2    10
%% 16:    3:0:2    2:3    13

%%  7:    1:1:0    3:7    06
%% 35:    1:3:2    2:4    0b
%% 14:    2:1:3    1:5    14
%% 49:    2:2:0    1:7    1a
%% 28:    3:3:0    2:0    1c
%% 56:    3:2:1    3:1    1f

%%  6:      1:1    1:1    03
%% 12:    1:0:1    2:6    05
%% 24:    3:1:2    3:3    11
%%  3:    1:2:3    3:5    08
%% 48:      2:2    1:3    0d
%% 33:    3:0:3    2:2    12

%% 26:    1:1:1    3:6    07
%% 13:    1:3:3    2:5    0a
%% 52:    2:1:2    1:4    15
%% 38:    2:2:1    1:6    1b
%% 41:    3:3:1    2:1    1d
%% 19:    3:2:0    3:0    1e

%% 62:    2:2:3    4:3    21
%% 31:    3:2:3    6:4    25
%% 47:    3:3:3    7:4    27
%% 55:    2:1:1    4:0    2e
%% 61:    1:3:0    7:1    31
%% 59:    1:1:3    6:3    3d

%%  5:    2:2:2    4:2    20
%% 34:    3:2:2    6:5    24
%% 17:    3:3:2    7:5    26
%% 40:    2:1:0    4:1    2f
%% 10:    1:3:1    7:0    30
%% 20:    1:1:2    6:2    3c

%% 25:    2:3:2    5:2    22
%% 11:    2:3:3    5:3    23
%% 37:    2:0:1    5:0    2c
%% 44:    2:0:0    5:1    2d
%% 50:      3:1    5:7    34
%% 22:      3:0    5:6    35

%% 23:    3:0:0    7:6    29
%% 53:    3:1:1    6:7    2a
%% 46:    1:2:1    6:0    32
%% 43:      2:0    4:6    37
%% 29:      1:2    4:5    38
%% 58:    1:0:3    7:3    3f

%% 15:    3:0:1    7:7    28
%% 51:    3:1:0    6:6    2b
%% 30:    1:2:0    6:1    33
%% 39:      2:1    4:7    36
%% 60:      1:3    4:4    39
%% 57:    1:0:2    7:2    3e


%% ----------------------------------------------------------------

%%  1:    01:00 001:000 000010
%%  2: 01:00:00 010:111 000100
%%  3: 01:10:11 011:101 001000
%%  4: 11:01:11 011:010 010000
%%  5: 10:10:10 100:010 100000
%%  6:    01:01 001:001 000011
%%  7: 01:01:00 011:111 000110
%%  8:    10:11 001:010 001100
%%  9: 10:11:00     111 011000
%% 10: 01:11:01 111:000 110000
%% 11: 10:11:11 101:011 100011
%% 12: 01:00:01 010:110 000101
%% 13: 01:11:11 010:101 001010
%% 14: 10:01:11 001:101 010100
%% 15: 11:00:01 111:111 101000
%% 16: 11:00:10 010:011 010011
%% 17: 11:11:10 111:101 100110
%% 18:    11:10     011 001111
%% 19: 11:10:00 011:000 011110
%% 20: 01:01:10 110:010 111100
%% 21:       11 101:100 111011
%% 22:    11:00 101:110 110101
%% 23: 11:00:00 111:110 101001
%% 24: 11:01:10 011:011 010001
%% 25: 10:11:10 101:010 100010
%% 26: 01:01:01 011:110 000111
%% 27:    11:11     010 001110
%% 28: 11:11:00 010:000 011100
%% 29:    01:10 100:101 111000
%% 30: 01:10:00 110:001 110011
%% 31: 11:10:11 110:100 100101
%% 32: 01:10:10 011:100 001001
%% 33: 11:00:11 010:010 010010
%% 34: 11:10:10 110:101 100100
%% 35: 01:11:10 010:100 001011
%% 36: 10:00:11     101 010110
%% 37: 10:00:01 101:000 101100
%% 38: 10:10:01 001:110 011011
%% 39:    10:01 100:111 110110
%% 40: 10:01:00 100:001 101111
%% 41: 11:11:01 010:001 011101
%% 42:       10 101:101 111010
%% 43:    10:00 100:110 110111
%% 44: 10:00:00 101:001 101101
%% 45: 10:11:01     110 011001
%% 46: 01:10:01 110:000 110010
%% 47: 11:11:11 111:100 100111
%% 48:    10:10 001:011 001101
%% 49: 10:10:00 001:111 011010
%% 50:    11:01 101:111 110100
%% 51: 11:01:00 110:110 101011
%% 52: 10:01:10 001:100 010101
%% 53: 11:01:01 110:111 101010
%% 54: 10:00:10     100 010111
%% 55: 10:01:01 100:000 101110
%% 56: 11:10:01 011:001 011111
%% 57: 01:00:10 111:010 111110
%% 58: 01:00:11 111:011 111111
%% 59: 01:01:11 110:011 111101
%% 60:    01:11 100:100 111001
%% 61: 01:11:00 111:001 110001
%% 62: 10:10:11 100:011 100001
%% 63:       01     001 000001

%%  1:    01:00 001:000 000010  33: 11:00:11 010:010 010010
%%  2: 01:00:00 010:111 000100  34: 11:10:10 110:101 100100
%%  3: 01:10:11 011:101 001000  35: 01:11:10 010:100 001011
%%  4: 11:01:11 011:010 010000  36: 10:00:11     101 010110
%%  5: 10:10:10 100:010 100000  37: 10:00:01 101:000 101100
%%  6:    01:01 001:001 000011  38: 10:10:01 001:110 011011
%%  7: 01:01:00 011:111 000110  39:    10:01 100:111 110110
%%  8:    10:11 001:010 001100  40: 10:01:00 100:001 101111
%%  9: 10:11:00     111 011000  41: 11:11:01 010:001 011101
%% 10: 01:11:01 111:000 110000  42:       10 101:101 111010
%% 11: 10:11:11 101:011 100011  43:    10:00 100:110 110111
%% 12: 01:00:01 010:110 000101  44: 10:00:00 101:001 101101
%% 13: 01:11:11 010:101 001010  45: 10:11:01     110 011001
%% 14: 10:01:11 001:101 010100  46: 01:10:01 110:000 110010
%% 15: 11:00:01 111:111 101000  47: 11:11:11 111:100 100111
%% 16: 11:00:10 010:011 010011  48:    10:10 001:011 001101
%% 17: 11:11:10 111:101 100110  49: 10:10:00 001:111 011010
%% 18:    11:10     011 001111  50:    11:01 101:111 110100
%% 19: 11:10:00 011:000 011110  51: 11:01:00 110:110 101011
%% 20: 01:01:10 110:010 111100  52: 10:01:10 001:100 010101
%% 21:       11 101:100 111011  53: 11:01:01 110:111 101010
%% 22:    11:00 101:110 110101  54: 10:00:10     100 010111
%% 23: 11:00:00 111:110 101001  55: 10:01:01 100:000 101110
%% 24: 11:01:10 011:011 010001  56: 11:10:01 011:001 011111
%% 25: 10:11:10 101:010 100010  57: 01:00:10 111:010 111110
%% 26: 01:01:01 011:110 000111  58: 01:00:11 111:011 111111
%% 27:    11:11     010 001110  59: 01:01:11 110:011 111101
%% 28: 11:11:00 010:000 011100  60:    01:11 100:100 111001
%% 29:    01:10 100:101 111000  61: 01:11:00 111:001 110001
%% 30: 01:10:00 110:001 110011  62: 10:10:11 100:011 100001
%% 31: 11:10:11 110:100 100101  63:       01     001 000001
%% 32: 01:10:10 011:100 001001                             

