\documentstyle[12pt]{report}
\pagestyle{myheadings}
\def\headlineaux{\sc Cryptography Seminar, Spring 1993
\hrulefill
}
\markboth{\headlineaux}{\headlineaux}

\newcommand{\naturals}{{\bf N}}
\newcommand{\reals}{{\bf R}}
\newtheorem{definition}{Definition}
\newtheorem{fact}{Fact}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newcommand{\set}[2]{\bigl\{\, #1 \,\big|\, #2 \,\bigr\}}
\newcommand{\implies}{\;\Rightarrow\;}
\newenvironment{proof}{\noindent{\sc Proof:~}}{\hfill$\Box$\par\medskip}
\newcommand{\infinity}{\infty}
\newcommand{\ZmodZ}[1]{{\bf Z}/#1{\bf Z}}
\newcommand{\GF}[1]{{{\it GF}\,(\,#1\,)}}
\newcommand{\Frob}[1]{{{\it Frob}_{#1}}}
\newcommand{\Fix}[2]{{{\it Fix}\,(\,#2\,)}}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burt Rosenberg}}
\end{centerline}\end{titlepage}

\section*{Notes on Galois Fields\hfill{\parbox{2in}
    {\small\sc\begin{flushright} Date: \today  \\
         Burt Rosenberg\end{flushright}}}}


For any prime $p$ and positive integer $f$,
the finite field on $p^f$ elements is
called a Galois Field, denoted $\GF{p^f}$.
The {\em Frobenius automorphism} on $G$, $\Frob{\GF{p^f}}$,
is defined as $x\mapsto x^p$.
Note that $(\Frob{\GF{p^f}})^f$, the $f$ iterate of the Frobenius automorphism,
is the identity on $\GF{p^f}$.
Given a field $G$ and an automorphism $\gamma$ of $G$, the
{\em fixed field} of $G$ by $\gamma$, $\Fix{G}{\gamma}$,
are those elements $g$ of $G$ such that $\gamma(g)=g$.
It is easy to verify that $\Fix{G}{\gamma}$ is a subfield of $G$.

\begin{lemma}
Let $G=\GF{p^f}$ and $e$ by a positive integer dividing $f$.
Then, 
\[ \Fix{G}{\Frob{G}^e} = \GF{p^e}. \]
\end{lemma}
\begin{proof}
It will be sufficient to show that the subfield 
$\Fix{G}{\Frob{G}^e}$ of $\GF{p^f}$ has $p^e$ elements.
We note that if $a$ divides $b$, then $X^a-1$ divides $X^b-1$.
Applying this twice,
\[ \bigl(\,X^{p^e-1}-1\,\bigr) \,\big |\, \bigl(\,X^{p^f-1}-1\,\bigr).\]
Hence we can write,
\[ X^{p^f-1}-1 = \bigl(\,X^{p^e-1}- 1\,\bigr)\, g(X), \]
where the degree of $g$ is $p^f - p^e$.
All the $p^f-1$ roots of the equation must appear in at least one of
the two factors, and by consideration of degrees, $p^e-1$ of them must
occur in $X^{p^e-1}-1$.
Hence the set of roots of $X^{p^e}-X$ in $G$ has size $p^e$.
This set is exactly the fixed field of $\Frob{G}^e$. 
\end{proof}

\begin{lemma}
Any subfield of $F$ of $\GF{p^f}$ must be of size $p^e$ with
$e$ dividing $f$.
\end{lemma}
\begin{proof}
The additive group $F$ is a subgroup of the additive group $\GF{p^f}$ 
and the multiplicative group $F^\times$ is a subgroup
of the multiplicative group $\GF{p^f}^\times$.
Therefore the size of $F$ divides $p^f$ and one less than its size divides $p^f-1$.
We therefore ask for conditions on $p^e-1 \,|\, p^f-1$, where $e\le f$.
Writing $p^e-1$ and $p^f-1$ in base $p$ and attempting the
long division demonstrates that the division will finish without
remainder only if $e\,|\,f$.
\end{proof}

\begin{lemma}
Let $G=\GF{p^f}$ and $e$ divide $f$.
The only subfield $F$ of $G$ of size $p^e$ is $\Fix{G}{\Frob{G}^e}$.
\end{lemma}
\begin{proof}
The subfield $F$ is isomorphic to $\GF{p^e}$ hence every
$x$ in $F$ satisfies $X^{p^e}-X$. Being an extension field of $F$, this
is also true in $G$.
Hence $F$ is inside the fixed field and is of equal size.
Therefore $F = \Fix{G}{\Frob{G}^e}$.
\end{proof}

\begin{theorem}
For a fixed prime $p$, the lattice of the Galois Fields
$\GF{p^i}$ ordered by inclusion
is isomorphic to the lattice of positive integers
ordered by divisibility.
\end{theorem}
\begin{proof}
We need not so much prove the theorem as clarify its statement.
Given any $\GF{p^f}$, we know there is exactly one $\GF{p^e}$ for each $e$
dividing $f$. Thus the 
map taking $i$ to $\GF{p^i}$ defines the lattice isomorphism.
If you want, the element $0$ maps to the algebraic closure of $\ZmodZ{p}$.
\end{proof}
It is thus natural to define the meet and join of Galois Fields as follows.

\begin{definition}
Given positive integers $i$ and $j$, let $k$ be their
greatest common divisor and $l$ their least common
multiple. Then,
\[ \GF{p^i}\wedge \GF{p^j} = \GF{p^k}, \]
and,
\[ \GF{p^i}\vee \GF{p^j} = \GF{p^l}. \]
\end{definition}

\begin{theorem}
For Galois Fields $\GF{p^f}$ and $\GF{p^e}$, $\GF{p^f}\wedge \GF{p^e}$
is the largest Galois Field contained in both
and $\GF{p^f}\vee \GF{p^e}$ is the smallest Galois Field which contains both.
Taking fixed fields result in joins: 
\[\Fix{}{\Frob{\GF{p^f}}^e} = \GF{p^f} \wedge \GF{p^e}.\]
Splitting $X^{p^e}-X$ in $\GF{p^f}$ results in a meet, $\GF{p^f}\vee\GF{p^e}$.
\end{theorem}
\begin{proof}
Exercise for the reader.
\end{proof}

\subsection*{Galois Theory}

We continue the discussion with some further clarification
of the role the Frobenius automorphism. 

\begin{theorem}
Let $\sigma$ be an automorphism of $\GF{p^f}$. Then
$\sigma = (\Frob{\GF{p^f}})^k$ for some $k$.
\end{theorem}
\begin{proof}
Let $g$ be a generator of $\GF{p^f}$, then for some $i$,
$\sigma(g)=g^i$, which implies that for all $x$ in the
field, $\sigma(x)=x^i$:
\[ \sigma(x) = \sigma(g^j) = \sigma(g)^j = g^{ij} = x^i.\]
It is left only to show that $i=p^k$ for some $k$.

Since $\sigma$ is an automorphism,
\[ (x+1)^i = x^i + 1. \]
So for $i>1$, $x^i+1$ has $-1$ as its only root with multiplicity $i$.
Thus it shares this root with its derivative, $i x^{i-1}$. So
$i=0$ in $\GF{p^f}$, that is $i = pi'$.
Because both $\sigma$ and $x\mapsto x^p$ are automorphisms, it
follows that so is $x\mapsto x^{i'}$. Therefore, $i'=pi''$.
Continuing, we have that $i = p^k$ for some $k$.
\end{proof}

\begin{corollary}
The group of automorphisms of $G=\GF{p^f}$ is isomorphic to
$\ZmodZ{f}$ via the map $i\mapsto \Frob{G}^i$.
\end{corollary}

\newcommand{\GFauto}[1]{{{\cal GF}\,(\,#1\,)}}

Galois theory continues with the exploration of the
connection of the lattice of subgroups of
$\GFauto{p^f}$, the group of automorphisms of $\GF{p^f}$,
and the lattice of subfields of $\GF{p^f}$, that is, the fields inside $\GF{p^f}$ fixed by some automorphism of $\GF{p^f}$.
We leave it to the reader to
show that this is an order-reversing isomorphism which
sends a subgroup of $\GFauto{p^f}$ to the field of elements fixed by
{\em all} automorphisms in the subgroup, the inverse sending
a subfield of $\GF{p^f}$ to the set of automorphisms that fix all elements in the subfield.

\end{document}
