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

\documentclass[10pt]{article}
\parindent=0pt \parskip=8pt

\usepackage{verbatim}
\usepackage{fullpage}

\usepackage{amssymb,amsmath,amsthm}
\usepackage[mathscr]{eucal}

\usepackage{makeidx}
%\numberwithin{equation}{subsection}
\numberwithin{equation}{section}
\input{isomath}
\input{mathenv}
\input{syms}
\usepackage{graphicx}
\usepackage{psfrag}

\makeindex

\usepackage{hyperref}
%\usepackage{ifpdf}

%\ifpdf
%\pdfinfo{
%/Author (John Kerl)
%/Title  (The Berlekamp algorithm)
%}
%\fi

%--------------------------------------------------------------------
\begin{document}
\title{The Berlekamp algorithm}
\author{John Kerl \\
University of Arizona Department of Mathematics \\
2009 Integration Workshop}
\date{\today}

\maketitle
\begin{abstract}
Integer factorization is a Hard Problem.  Some cryptosystems, such as RSA, are
in fact designed around the difficulty of integer factorization.  For
polynomials with coefficients in the finite field $\Fq$, on the other hand, we
can use the Berlekamp algorithm to factor polynomials of high degree in
reasonable amounts of time.

In this project, you will see how the algorithm works, prove its correctness,
and analyze its computational complexity.  This project is aimed toward those
with interests in computational algebra, finite fields, and/or linear algebra.
\end{abstract}

\addcontentsline{toc}{section}{Contents}
\tableofcontents

%% ================================================================
%\newpage
\section{Theory}

%See also section \ref{sec:example_31} for a worked example.

%% ----------------------------------------------------------------
\subsection{Definitions}

\begin{defn}
Let $f \in \Fq[x]$ have degree $n$.  Suppose
$$
	f = e_1 \cdots e_k
$$
be the \emphidx{prime factorization} of $f$, for $e_i \in \Fq[x]$ with degrees
$d_i = \deg(e_i) \ge 1$.  Suppose $f$ is \emphidx{monic} and that all the
$e_i$'s are as well.  Assume that $f$ is \emphidx{squarefree}, i.e. that all
the $e_i$'s are distinct.  (See section \ref{sec:sqfree} to see why this
restriction is not a difficulty.) Of course, we don't yet know what the $e_i$'s
are, nor what $k$ is; that is the purpose of a factorization algorithm.
\end{defn}

\begin{defn}
Let
$$
	A_f = \Fq[x] / \pig f.
$$
This is a vector space over $\Fq$, of degree $n$.  In fact it is an
\emphidx{algebra}: a vector space wherein you can also multiply the vectors.
\end{defn}

\begin{defn}
Let
$$
	B_f = \{h \in A_f : h^q \equiv h \pmod f\}.
$$
This is the \emphidx{Berlekamp subalgebra} of $A_f$.  (You will prove below
that this is actually a subalgebra.)
\end{defn}

\begin{defn}
Define
$$
	Q_f: A_f \to A_f
$$
by $a(x) \mapsto a(x)^q$ for each $a \in A_f$.
\end{defn}

\begin{prop}
This is an $\Fq$-linear map from $A_f$ to itself.
\begin{proof}
Prove this.  (Hint:  use the \emphidx{freshman's dream}.)
\end{proof}
\end{prop}

\begin{prop}
$B_f = \ker(Q_f-I)$.
\begin{proof}
Prove this.  (Hint:  you will need the \emphidx{Frobenius automorphism} from
finite-field theory.)
\end{proof}
\end{prop}

\begin{prop}
$B_f$ is a subalgebra of $A_f$.
\begin{proof}
Prove this.  (Hint:  You can check subspace axioms, or you can use the
fact that $B_f$ is the kernel of a linear map.)
\end{proof}
\end{prop}

\begin{rem}
By the \plainidx{Chinese Remainder Theorem},
$$
	A_f \isom \Fq[x]/\pig{e_1} \times \cdots \times \Fq[x]/\pig{e_k}.
$$
(Since each of the $e_i$'s is irreducible, each factor is a finite field.)
\end{rem}

%% ----------------------------------------------------------------
\subsection{Linear algebra}

We can find a basis for the vector subspace $B_f$ of $A_f$ using linear
algebra.  (See section \ref{sec:example_31} for a worked example.) The set
$\{x^{n-1}, x^{n-2}, \ldots, x, 1\}$ (where $n=\deg f$) is a basis for $A_f$.
The map $Q_f$, defined above, is defined by its action on this standard basis.
Let the $M$ be the matrix of $Q_f$, with respect to the standard basis for
$A_f$.

%Using both the polynomial point of view and the vector-space point of view,
%here we figure out how to write down the matrix for $Q$.  Let
%$$
%	h(x) = c_{n-1}x^{n-1} + c_{n-2}x^{n-2} + \ldots + c_1 x + c_0.
%$$
%The $q$th power of $h$ would be a multinomial mess, were it not for
%the freshman's dream.  We have:
%$$
%	h(x)^q = c_{n-1}x^{(n-1)q} + c_{n-2}x^{(n-2)q} + \ldots + c_1 x^q + c_0.
%$$
%When each monomial $x^{jq}$ is reduced mod $f$, the result is a polynomial of
%degree at most $n-1$:
%$$
%	x^{jq} \equiv s^{(j)}_{n-1} x^{n-1} + s^{(j)}_{n-2} x^{n-2} + \ldots +
%	s^{(j)}_{1} x^ + s^{(j)}_{0} \pmod f.
%$$
%Now think of $h$, not as a polynomial, but as a vector $\mathbf{h}$
%in $A_f$.  We have
%$$
%	(Q_f\mathbf{h}) = M \mathbf{h}.
%$$
%
%\textbf{Question:} Write down an explicit expression for $M_{ij}$ in terms of
%the above information.

\textbf{Question:} Using both the polynomial point of view and the vector-space
point of view, figure out how to write down the matrix for $Q$.  Write $h(x)$
as a vector with respect to the standard basis; do the same for $Qh = h^q$,
where the latter is reduced mod $f$.  (Hint:  reduction mod $f$ is a ring
homomorphism, so it moves through terms.)

%$$
%	h(x) = c_{n-1}x^{n-1} + c_{n-2}x^{n-2} + \ldots + c_1 x + c_0.
%$$
%The $q$th power of $h$ would be a multinomial mess, were it not for
%the freshman's dream.  We have:
%$$
%	h(x)^q = c_{n-1}x^{(n-1)q} + c_{n-2}x^{(n-2)q} + \ldots + c_1 x^q + c_0.
%$$
%When each monomial $x^{jq}$ is reduced mod $f$, the result is a polynomial of
%degree at most $n-1$:
%$$
%	x^{jq} \equiv s^{(j)}_{n-1} x^{n-1} + s^{(j)}_{n-2} x^{n-2} + \ldots +
%	s^{(j)}_{1} x^ + s^{(j)}_{0} \pmod f.
%$$
%Now think of $h$, not as a polynomial, but as a vector $\mathbf{h}$
%in $A_f$.  We have
%$$
%	(Q_f\mathbf{h}) = M \mathbf{h}.
%$$
%
%\textbf{Question:} Write down an explicit expression for $M_{ij}$ in terms of
%the above information.

Using row reduction, we can compute a basis for $B_f = \ker(Q_f-I)$ using row
reduction on the matrix $M-I$.  This is an important part of the factorization
algorithm, for the following reason.

\begin{prop}
The nullity of $Q_f-I$ is the number of irreducible factors of $f(x)$.
\begin{proof}
Please flesh out the details in the following sketch.

We have, by hypothesis,
$$
	f = e_1 \cdots e_k.
$$
By the Chinese Remainder Theorem (mapping how, precisely?),
$$
	A_f = \Fq[x]/\pig{e_1} \times \cdots \times \Fq[x]/\pig{e_k}.
$$
Now let $h \in B_f$.  The CRT map sends $h$ to $(r_1, \ldots, r_k)$.  Since $h
\in B_f$,
\begin{align*}
	0 &= h^q - h = (r_1^q-r_1, \ldots, r_k^q-r_k).
\end{align*}
This means $r_i^q=r_i$ for each $i$, so therefore each $r_i$ is in $\F_q$.

We may conclude that $B_f \isom (\F_q)^k$.  (How does this relate to the
rank and nullity of $Q_f-I$?)
\end{proof}
\end{prop}

This means that we can already test for irreducibility, just by checking the
nullity of $Q_f-I$.  Going ahead and finding a non-trivial factor of $f(x)$
takes a little more work.

%% ----------------------------------------------------------------
\subsection{GCDs}

\begin{prop}
For each $h \in B_f$,
$$
	f(x) = \prod_{c \in \Fq} \gcd(f, h-c).
$$
\begin{proof}
Prove this.  (Hint:  Show that the left-hand side divides the right-hand
side, and vice versa.)
\end{proof}
\end{prop}

\begin{cor}
For each $h \in B_f$, if $0 < \deg h$, there exists some $c \in \Fq$ such that
$g = \gcd(f, h-c) \ne 1$.  Such a $g$ is a non-trivial factor of $f$.
\begin{proof}
Prove this.
\end{proof}
\end{cor}

% xxx gcd business ... .

% f = 157fd5 = 13 1f 19 7 b d

% hc             factors            GCDs w/ f    factors
% ----------     --------------   ---------   ---------------------
% h0 =     1  =  1                        1 =  1
% h1 =     0  =  0                   157fd5 =  7  b  d 13 19 1f
%
% h0 = a0522  =  2 3^3 b d 19 3d        477 =  b  d 19
% h1 = a0523  =  7^3 13 1f 29           537 =  7 13 1f
% h0 = d1764  =  2^2 3 13 1f 187        1d1 = 13 1f
% h1 = d1765  =  7^2 b d 19 3b         1d45 =  7  b  d 19
% h0 = b9768  =  2^3 7 d 19 d3          30b =  7  d 19
% h1 = b9769  =  3^2 b 13 1f 73         cfb =  b 13 1f
% h0 = 79350  =  2^4 d 13 a7             c7 =  d 13
% h1 = 79351  =  3 7 b 19^2 1f         3287 =  7  b 19 1f
% h0 = b6980  =  2^7 3 7 1f 3d           5d =  7 1f
% h1 = b6981  =  b d 13 19 29          4be9 =  b  d 13 19

% ----------------------------------------------------------------
% p=5 r = 103443113332 = 102 103 1223 13004
% dimker = 4
% 
% 	h0 =           1 gcd =            1 =    1
% 	h1 =           0 gcd = 103443113332 =  102   103 1223 13004
% 	h2 =           4 gcd =            4 =    1     4
% 	h3 =           3 gcd =            3 =    1     3
% 	h4 =           2 gcd =            2 =    1     2
% 
% 	h0 =    14421440 gcd =            1 =    1
% 	h1 =    14421444 gcd =            4 =    1     4
% 	h2 =    14421443 gcd =         1223 = 1223
% 	h3 =    14421442 gcd =        10001 =  102   103
% 	h4 =    14421441 gcd =        34002 =    3 13004
% 
% 	h0 =  1403320320 gcd =            1 =    1
% 	h1 =  1403320324 gcd =            4 =    1     4
% 	h2 =  1403320323 gcd =        30003 =    3   102  103
% 	h3 =  1403320322 gcd =         3114 =    3  1223
% 	h4 =  1403320321 gcd =        34002 =    3 13004
% 
% 	h0 = 10402420040 gcd =          402 =    4   103
% 	h1 = 10402420044 gcd =            4 =    1     4
% 	h2 = 10402420043 gcd =        34002 =    3 13004
% 	h3 = 10402420042 gcd =            3 =    1     3
% 	h4 = 10402420041 gcd =       124241 =  102  1223
% 
% ----------------------------------------------------------------
% p=5 r = 10343332 = 1223 13004
% dimker = 2
% 
%   h0 = 1  gcd = 1
%   h1 = 0  gcd = 10343332
%   h2 = 4  gcd = 4
%   h3 = 3  gcd = 3
%   h4 = 2  gcd = 2
% 
%   h0 = 1422440  gcd = 1
%   h1 = 1422444  gcd = 2441    = 2441:  2 1223
%   h2 = 1422443  gcd = 4
%   h3 = 1422442  gcd = 3
%   h4 = 1422441  gcd = 13004     13004:  13004

%% ----------------------------------------------------------------
\subsection{Squarefree preparation}
\label{sec:sqfree}

This section is optional.

Berlekamp's algorithm requires squarefree input --- yet, given an input
polynomial $f$, how do you know if it's squarefree?  Isn't this the kind of
thing you want a factorization algorithm to do for you?

It turns out there is a trick.  Given $f$, let $f'$ be the formal derivative
of $f$ with respect to $x$.  Then let
$$
	g = \gcd(f,f').
$$
Case 1: If $g$ has degree 0, then the input $f$ is squarefree, and is ready for
Berlekamp.

\textbf{Question:}  Prove why this is true.

Case 2: If $f' = 0$:  the input is a perfect $p$th power, where $p$ is the
characteristic of $\Fq$.  You can find out what this is just by looking at $f$.

\textbf{Question:} Use the freshman's dream to find out why.  (Hint:  make up a
few polynomials over $\F_2$ and square them; make up a few polynomials over
$\F_3$ and cube them.  What do they look like?  Looking at only the $p$th
powers, is it easy to guess what they are the $p$th powers of?)

(Now, if $f$ is a $p$th power, its $p$th root might also be a $p$th power: e.g.
if $f(x) = x^4+1$ over $\F_2$.  So, you need to recursively run the $p$th root
of $f$ through the squarefree-preparation routine.)

Case 3: Else --- i.e. if $g$ has degree $\ge 1$, and if $f' \ne 0$, then
recursively apply the squarefree-preparation algorithm to $g$ and $f/g$.

%% ================================================================
%\newpage
\section{Practicalities}

%% ----------------------------------------------------------------
\subsection{Pseudocode}

\textbf{Question:}  Use the pieces of theory from the above sections to write
out a pseudocode description of Berlekamp's algorithm.  (You may assume the
input is squarefree, or you may incorporate the information in section
\ref{sec:sqfree} and describe how non-squarefree input is handled.)  The
algorithm should take an input polynomial, and describe how to factor it into
distinct irreducible factors.  Your description should include what can happen
when there are three or more factors.  You need not describe row reduction in
detail:  you may treat this as a black-box step of the algorithm.  However, you
should be explicit about how each of the basis vectors are handled.

\textbf{Extra question:} What do you choose to do if the input polynomial is
non-monic?

%% ----------------------------------------------------------------
\subsection{Worked example}
\label{sec:example_31}

Given squarefree $f(x)$, we want to find polynomials $h(x)$ such that $h^q
\equiv h \pmod f$.  Take $f = x^5+x^4+1 = 110001 = 111 \cdot 1011$.  The degree
of $f$ is 5.  By explicit search, we can find the following polynomials $h$ of
degree $< 5$ such that $h^2 \equiv h \pmod f$: $0$, $1$, $11100$, $11101$.

To avoid having to do a search, we use linear algebra instead.
\begin{align*}
	f &= x^5+x^4+1 = 110001 \\
	x^0 &\equiv 00001 \pmod f \\
	x^2 &\equiv 00100 \pmod f \\
	x^4 &\equiv 10000 \pmod f \\
	x^6 &\equiv 10011 \pmod f \\
	x^8 &\equiv 11111 \pmod f.
\end{align*}
\begin{align*}
h   &= a_4 x^4 + a_3 x^3 + a_2 x^2 + a_1 x   + a_0 \\
h^2 &= a_4 x^8 + a_3 x^6 + a_2 x^4 + a_1 x^2 + a_0 \\
    &= a_4(x^4+x^3+x^2+x+1) + a_3(x^4+x+1) + a_2(x^4) + a_1(x^2) + a_0(1) \\
%
%
\bcmatrix{
	a_4 \\
	a_3 \\
	a_2 \\
	a_1 \\
	a_0 \\
}
&=
\bcmatrix{
1 & 1 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 \\
1 & 1 & 0 & 0 & 1 \\
}
\cdot
\bcmatrix{
	a_4 \\
	a_3 \\
	a_2 \\
	a_1 \\
	a_0 \\
} \\
%
\bcmatrix{
	0 \\
	0 \\
	0 \\
	0 \\
	0 \\
}
&=
\bcmatrix{
0 & 1 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 & 0 \\
1 & 1 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 \\
}
\cdot
\bcmatrix{
	a_4 \\
	a_3 \\
	a_2 \\
	a_1 \\
	a_0 \\
}.
\end{align*}
Call the matrix $M$.  Its $(n-1-j)$th column is $x^{jq} \pmod f$.  Put $M-I$ in
row-echelon form to obtain
\begin{align*}
\bcmatrix{
	1 & 0 & 1 & 0 & 0 \\
	0 & 1 & 1 & 0 & 0 \\
	0 & 0 & 0 & 1 & 0 \\
	0 & 0 & 0 & 0 & 0 \\
	0 & 0 & 0 & 0 & 0 \\
	}
\end{align*}
with kernel basis
\begin{align*}
	(1,1,1,0,0), \qquad (0,0,0,0,1).
\end{align*}
These are $h_1 = 11100$ and $h_2 = 1$, respectively.  Compute $\gcd(f, h_1) =
111$ and $\gcd(f, h_1+1) = 1011$ to obtain non-trivial factors of $f$.

%% ----------------------------------------------------------------
\subsection{Complexity analysis}

\textbf{Question:} Describe the number of $\Fq$ arithmetic operations needed to
perform one step of Berlekamp's algorithm, i.e. to find one non-trivial factor
of an input polynomial $f(x)$.  (For row reduction, you can count operations.
For the GCD step, describe the complexity of a single GCD, since the number of
GCDs that need to be computed may vary.)

%% ================================================================
\appendix
\newpage
\section{Background:  integers}

I assume you're familiar with integer arithmetic, but perhaps not so much with
polynomials over $\Fq$.  Moreover, even if you have had exposure to finite
fields, my experience is that many instructors teach the subject very
abstractly.  So, you might have been taught existence and uniqueness of finite
fields, but you might never have been taught how to actually do explicit
computations with them.

Here we remind ourselves of some facts about the familiar integers, in order to
facilitate comparison with perhaps-less-familiar polynomials over finite
fields, below.

%% ----------------------------------------------------------------
\subsection{Integer factorization and complexity}

How do you factor an integer $n$ into primes?  You don't need to find all prime
factors at once.  It suffices to find any non-trivial factor $a$.  If there is
no such, then $n$ is prime.  Otherwise you get $b=n/a$.  Then, using a
divide-and-conquer strategy, you can apply whatever algorithm you used for $n$
to the integers $a$ and $b$.

So, how do we find a non-trivial factor of a given $n$?  One way is to
trial-divide $n$ by all $2 \le a < n$.  If the remainder is zero for any such
$a$, then $a \mid n$.  What is the computational complexity?  This takes $n-2$
divisions; we say that this algorithm is $O(n)$ in the number of divisions.
(Note of course that division itself takes longer when $n$ is bigger; you would
get a different order of complexity if you were to count not number of
divisions, but say, digit operations.)

This is clearly non-optimal, though.  If $a \mid n$, then $b=n/a \mid n$ as
well, and we can take $a \le b$.  That is, if $n$ has one factor greater than
or equal to $\sqrt n$, then it has another factor less than or equal to $\sqrt
n$.  Given $n=101$, once you've gotten past $a=10$ you can stop.  Thus, a
second algorithm for finding a non-trivial factor of $n$ is to trial-divide by
all $2 \le a \le \sqrt n$.  This takes $O(\sqrt n)$ trial divisions.

This is also non-optimal.  Once you've found that $2 \nmid n$, it's silly to
divide $n$ by 4, 6, or any other even number.  Likewise, once you know $3 \nmid
n$, you needn't trial-divide $n$ by any other multiple of 3.  So, a third
algorithm would be to trial-divide $n$ by all $2 \le p \le \sqrt n$ only for
primes $p$.  (Of course, you can only do this if you have a big enough table of
primes.)  What's the complexity?  By the prime number theorem, the number of
primes less than or equal to $\sqrt n$ is approximately $\sqrt n / \ln(\sqrt
n)$, so the number of trial divisions is $O(\sqrt n / \ln(\sqrt n))$.

There are lots of integer-factorization algorithms, some easy and some hard,
and also there are quite nice primality-testing algorithms which don't produce
a factorization but which tell you if you should bother.  I won't describe them
further; the above examples suffice to demonstrate that (a) there are different
ways of doing things, and (b) one can quantify the amount of time they take.

%% ----------------------------------------------------------------
\subsection{Modular arithmetic with integers}

Given any $n \ge 2$, we can compute in the residue ring $\Z/n\Z = \Z/\pig{n}$.
(I happily write this $\Z_n$, although number theorists balk at this notation
since it means something else to them.)  The method is to reduce mod $n$ and
take remainders.  E.g. if $n=10$ and $a = 27$, we reduce $27$ mod $10$ to
obtain the canonical representative $7$ for the equivalence class containing
$7$.  Specifically, we divide 27 by 10 and take the remainder, 7.

Given equivalence-class representatives $a$ and $b$, we can add, subtract, or
multiply them in $\Z$, then reduce mod $n$.  This is because reduction mod $n$
is a ring homomorphism from $\Z$ to $\Z_n$.

If $n$ is prime (call it $p$), then $\Z_p$ is a field.  This is how we
construct finite fields of prime order $p$.  Otherwise, $\Z_n$ is a ring with
zero-divisors.

%% ================================================================
%\newpage
\section{Background:  polynomial and modular polynomial arithmetic over $\F_2$}

This project studies factorizations of polynomials in $\Fq[x]$.  Since this may
be less familiar than working with integers, we give some computational
examples and some notation.

%% ----------------------------------------------------------------
\subsection{Polynomial arithmetic}

Take $q=2$.  Then $x^4 + 1$ is a fourth-degree polynomial with coefficients 0
or 1, with coefficient arithmetic done mod 2.  This factors as $(x^2+1)^2$,
which in turn factors as $(x+1)^4$.  So, $x^4+1$ is \emphidx{reducible}.

By contrast, $f(x) = x^4+x+1$ has no non-trivial factors; we say that it is
\emphidx{irreducible}.  How can I be so sure of that statement?  Well, since
degree four is small, we can do an explicit search.  If $f$ has a non-trivial
factor, i.e. a factor with degree greater than or equal to one, one factor must
have degree 1, 2, or 3.  There are two degree-one polynomials over $\F_2$:  $x$
and $x+1$.  There are four degree-two polynomials: $x^2$, $x^2+1$, $x^2+x$, and
$x^2+x+1$.  There are eight degree-three polynomials, $x^3$ through
$x^3+x^2+x+1$.  So, all we need to do is use long division, dividing $x^4+x+1$
by each of these fourteen possible divisors.  If none of them goes into
$x^4+x+1$ with a zero remainder, then $x^4+x+1$ is irreducible.

This is similar to the most naive trial division for integers.  As with integer
division, where we need to trial-divide up to $\sqrt n$, here too we can stop
trial-dividing by polynomials with degree up to $n/2$ where $n=\deg f$.  For
larger degree, the number of trial divisors gets large.

\textbf{Question:}  What is the number of trial divisors using the above
method?  You can write it as a function of $n$ and $q$.

Elwyn Berlekamp's algorithm (1967) is a powerful way to factor polynomials over
$\Fq$.  Note that we don't have such a powerful algorithm for polynomials with
coefficients in $\Q$, or for integers.

For shorthand, we'll often write polynomials with their coefficients only, in
descending order of degrees of terms.  For example, $x^4+1 = 10001 = 101^2 =
11^4$ and $x^4+x+1=10011$.

%Here are all the fourth-degree polynomials over $\F_2$ along
%with their factorizations (which you can check by multiplying them back out):
%\begin{align*}
%	10000 &= 10^2   & 10100 &= 11^2\cdot 10^2   & 11000 &= 11\cdot 10^3   & 11100 &= 111 \cdot 10^2   \\
%	10001 &= 11^2   & 10101 &= xxx   & 11001 &= xxx   & 11101 &= xxx   \\
%	10010 &= xxx   & 10110 &= xxx   & 11010 &= xxx   & 11110 &= xxx   \\
%	10011 &= xxx   & 10111 &= xxx   & 11011 &= xxx   & 11111 &= 11111   \\
%\end{align*}

You can check that
$$
	110001 = 111 \cdot 1011
$$
and
$$
	111100001110 = 10 \cdot 11 \cdot 111 \cdot 1011 \cdot 1101
$$
Likewise you can check that each of these factors is in fact irreducible.  (The
ring $F[x]$, for any field $F$, is a unique factorization domain so
irreducibility and primality are equivalent.  Nonetheless, the convention is to
use the words ``prime'' and ``composite'' for integers, and the words
``irreducible'' and ``reducible'' for polynomials.)

%% ----------------------------------------------------------------
\subsection{Modular polynomial arithmetic}

Once we know how to add, subtract, and multiply polynomials in $\Fq[x]$, it's
not much harder to do arithmetic in the residue ring $\Fq[x] / \pig{f}$.  Just
as with modular arithmetic of integers, given a polynomial $a(x)$, we divide it
by the modulus $f(x)$ and take the remainder.  This means in particular that
$\deg a < \deg f$, where $a$ here refers to the canonical representative.

\textbf{Question:}  Given $f(x) \in \Fq[x]$, with $\deg f = n$, how many
elements are there in $\Fq[x]/\pig{f}$?

Given two polynomials $a(x)$ and $b(x)$, we can add, subtract, or multiply
them, then reduce the result mod $f(x)$.  For example, if $f(x) = 10011 \in
\F_2[x]$, $a(x) = 1111$, and $b(x) = 101$, then $a(x) b(x)$ can be found using
high-school multiplication (with coefficients mod 2, i.e. you can just forget
to carry):
\begin{verbatim}
  1111
*  101
------
  1111
1111
------
110011
\end{verbatim}
Now to reduce mod $f(x)$, you can do long division and keep the remainder.
But, since \emph{all} you need is the remainder and not the quotient,
it's even easier.  Just keep subtracting off multiples of $f(x)$ until
the result has degree less than the degree of $f(x)$:
\begin{verbatim}
  110011
- 10011
  ------
   10101
 - 10011
  ------
     110
\end{verbatim}
So, just as $27 \cdot 36 \equiv 2 \pmod{10}$ in the integers, we have $1111
\cdot 101 \equiv 110 \pmod{10011}$ in $\F_2[x]$.

If $f(x)$ is irreducible in $\Fq[x]$, then $\Fq[x]/f(x)$ is a field --- a
finite field of size $q^n$ where $n=\deg(f)$.  Otherwise, it's a ring
with zero-divisors.

%% ================================================================
%\newpage
\section*{}
\addcontentsline{toc}{section}{References}

\begin{thebibliography}{}

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

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

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

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

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

\end{thebibliography}


%% ================================================================
%\newpage
%\section*{}
%\addcontentsline{toc}{section}{Index}
%\printindex

\end{document}
