%% ================================================================
\part{Galois theory}
\newpage

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

%% ----------------------------------------------------------------
\section{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 chapter
\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}

%% ----------------------------------------------------------------
\section{$\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 \bfidx{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*}

%% ----------------------------------------------------------------
\section{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
chapter \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
\chapter{Basic Galois theory for $\F_{p^n}$}
\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.

\section{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 \bfidx{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 \bfidx{embedded} (i.e. mapped with a 1-1 homomorphism) into the $x^4+x+1$
field $\F_{2^4}$.

%% ----------------------------------------------------------------
\section{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 \bfidx{Frobenius automorphism}.
For the additive homomorphism property, use the \bfidx{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$.

%% ----------------------------------------------------------------
\section{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 \bfidx{orbit} of $a$ under the
\bfidx{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}$.

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

The \bfidx{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 \bfidx{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}

%% ----------------------------------------------------------------
\section{Conjugates}

Two elements of the field are said to be \bfidx{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$.

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

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

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

%% ----------------------------------------------------------------
\section{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}

%% ----------------------------------------------------------------
\section{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}

%% ----------------------------------------------------------------
\section{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. chapter
	\ref{appx:root_chart_how_to}, or use a factorization algorithm, e.g.
	chapter \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}

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

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

%% ================================================================
\chapter{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 \emph{single extension} and \emph{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 \emph{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)$.

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

%% ----------------------------------------------------------------
\section{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 \bfidx{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}

%% ----------------------------------------------------------------
\section{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. chapter
\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*}

