%% ================================================================
\part{Algorithms}

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

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

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

%% ----------------------------------------------------------------
\section{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 chapter \ref{appx:berlekamp}.

%% ----------------------------------------------------------------
\section{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
\chapter{How to find primitive polynomials in $\F_p[x]$}
\label{appx:prims_in_Fpx}

In chapter \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 chapter \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
\chapter{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 Lidl and Niederreiter \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))$.

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

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

%% ----------------------------------------------------------------
\section{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
\chapter{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 chapter \ref{appx:irreds_in_Fp} for
irreducibility testing) with which to define arithmetic for an $\F_{p^n}$, use
Berlekamp's algorithm (chapter \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.
