%% ================================================================
\part{Software implementation}

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

\chapter{Computing with finite fields in GP}
\label{appx:gp_in_Fpx}

If you haven't guessed by now, even though all the methods presented in this
paper can be done by hand, it quickly gets tedious even with the assistance of
tables.  It can become more entertaining, however, if you let a machine do the
repetitive work (but only after you also know how to do it yourself, with the
machine turned off!).  The computational algebraic number theory package GP
\cite{bib:gp} can be used to compute in finite fields.  Also, of course, you
can use Mathematica, Maple, GAP and probably several other packages.  Here I'll
talk about GP.  In chapter \ref{chap:C} I'll discuss implementation of $p=2$ in
software, since that is an important special case.

Going the other way, if you're looking at an implementation of a finite-field
algorithm written by someone else --- whether in C or assembler (software),
Verilog or VHDL (hardware), etc. --- the implemenation may look not at all
familiar.  Chapter \ref{chap:C} will explain some of those snippets of C code.

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

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

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

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

? a
%1 = Mod(2, 11)

? lift(a)
%2 = 2

? lift(a^4)
%3 = 5

? lift(a^5)
%4 = 10

? lift(a^10)
%5 = 1

? lift(1/a)
%6 = 6

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

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

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

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

? polisirreducible(rpoly)
%1 = 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

p  = 2;

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

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

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

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

Partial output:

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

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

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

%% ================================================================
\chapter{$p=2$ in C}
\label{chap:C}

A main purpose of this paper is to connect mathematical theory of finite fields
with engineering practice.  Sometimes we use software to automate tasks which
we find repetitive.  Computer algebra systems, such as GP, do well at this for
general $\Fpn$.  However, we can do further optimizations in the $p=2$ case,
since operations may be done in binary and may take advantage of some hardware
parallelism (as we'll see below).  For this reason, the $p=2$ case is the most
important in applications (e.g. cryptography and error correction).

Finite-field algorithms can implemented in software (say in C or assembler) or
in electronic circuitry (e.g. in Verilog, VHDL or Handel-C).  It can be
disconcerting to see these low-level bit operations and not have any idea of
how it relates to the mathematical theory.  This section is a little different
from the GP section:  when I discussed GP, I talked about what \emph{you} can
do to implement finite-field arithmetic.  For this section, I want to talk not
only about how you can implement finite-field arithmetic, but also about how
\emph{other people} implement it.  In particular, I want explain some commonly
encountered paradigms, in order to shed some light on some of those mysterious
circuit diagrams and snippets of C code you see in the literature or on the
job.

Of course, syntaxes and applications vary between programming languages, but
regardless of the implementation, you will see the same kinds of XOR and shift
operations.  I'll choose to give my examples in C: C is a common implementation
language, it is (mostly) processor independent, and (unlike hardware design
languages) it is easy to experiment with, without needing special hardware or
tools.  I'll assume you are able to compile and run a hello-world program in C,
that you can use the basic I/O facilities of the \texttt{stdio} library, that
you can write and call a function, etc.  However, I won't assume you're a C
guru, and in particular I will not assume knowledge of machine arithmetic.

%% ----------------------------------------------------------------
\section{Hexadecimal notation}

First of all, we need to get familiar with \textbf{hexadecimal notation}.  The
Verilog and VHDL languages let you type your values in binary, if you wish.  C
does not, so you need to know hex to be able to \emph{write} C code.  Also,
hexadecimal is the notation of choice (even outside of C), so you need to know
hex to be able to \emph{read} the C code as well.

Hexadecimal notation is simply base-16 arithmetic.  The first 10 digits are
0-9; the remaining 6 (corresponding to 10-15) are a-f\footnote{Or, A-F
depending on personal preference.  C compilers accept both.}.  We use the 0x
prefix\footnote{This is the convention in C.  In some assemblers, and in much
literature from the Intel corporation, you'll see e.g.  23h in place of 0x23.
Some other assemblers use a dollar sign, e.g. \$23.  } to indicate hexadecimal
values, e.g. 0x13 in hex is 19 in decimal.

The nice thing about base 16 is that every hex digit (or \emph{nybble})
corresponds to 4 bits\footnote{\emph{Octal}, or base 8, was common up through
the 1970s or so.  Each octal digit, 0-7, represents 3 bits.  A word size of 36
bits was common on older IBM mainframes, and 3 goes evenly into 36.  Today,
processor word sizes are always a power of two, e.g. 8, 16, 32 or 64 bits, and
bytes are always 8 bits, so base 16 is more natural.}.  Thus it is easy to
translate back and forth between binary and hex.  Furthermore, this enables a
compact notation which makes numbers easier to remember\footnote{Also enabling
engineers to  invent creative test patterns for software and hardware designs,
e.g.  0xdeadbeef, 0xbadd1dea, 0xdeaddadd8badf00d, etc. etc.}.  For example, is
it easier to remember this: $$\mathrm{100000100110000010001110110110111}$$ or
this: $$\mathrm{0x104c11db7?}$$ Personally, I'd choose the latter.

Here is a table.  If you're going to be implementing bit-manipulation
algorithms, it would be best to know it by heart.

\begin{tabular}{|rrr|}
\hline
Hex & Decimal & Binary \\
\hline
0 & 0 &0000 \\
1 & 1 &0001 \\
2 & 2 &0010 \\
3 & 3 &0011 \\
\hline
4 & 4 &0100 \\
5 & 5 &0101 \\
6 & 6 &0110 \\
7 & 7 &0111 \\
\hline
8 & 8 &1000 \\
9 & 9 &1001 \\
a &10 &1010 \\
b &11 &1011 \\
\hline
c &12 &1100 \\
d &13 &1101 \\
e &14 &1110 \\
f &15 &1111 \\
\hline
\end{tabular}

When you see multi-digit hexadecimal numbers, simply translate them one nybble
at a time.  E.g. 0x14e becomes 0001 0100 1110.  Likewise, convert from binary
to hex four bits at a time, but be sure to group into foursomes \emph{starting
from the right}.  E.g. 0101101 is 010 1101 which is 0x2d.

(To convert back and forth between binary and decimal, or between hex and
decimal, is not as straightforward.  Use a pencil and paper, use a scientific
calculator, or do it in your head.  For this document, we won't need to convert
between hex and decimal notation so it's a non-issue.)

%% ----------------------------------------------------------------
\section{I/O}

When you type in a \emph{literal} in your C code, you must prefix it with
0x so the compiler can distinguish it from decimal.  For example:
\begin{verbatim}
        unsigned x = 0x13;
\end{verbatim}

When you read in a string or a file, you can omit the 0x prefix if your code is
expecting hexadecimal input:  the \texttt{scanf} (scan standard input),
\texttt{sscanf} (scan a string) and \texttt{fscanf} (scan from a file stream)
functions use \texttt{\%x} to specify hex input.  For example:
\begin{verbatim}
        char * string = "13";
        unsigned x;
        ...
        if (sscanf(string, "%x", &x) != 1)
                printf("Couldn't scan input \"%s\" as hex.\n", string);
\end{verbatim}

When you print a hex value, again use \texttt{\%x}.  Additionally, use a
preceding digit to indicate field width (e.g. if you are printing columnar data
which you want to align nicely), and optionally precede that with a zero to
indicate zero fill.  For example:
\begin{verbatim}
        unsigned a = 0x2, r = 0x13;
        printf("<<%x>> <<%x>>\n", a, r);       Results in <<2>> <<13>>
        printf("<<%4x>> <<%4x>>\n", a, r);     Results in <<   2>> <<  13>>
        printf("<<%04x>> <<%04x>>\n", a, r);   Results in <<0002>> <<0013>>
\end{verbatim}

%% ----------------------------------------------------------------
\section{Word sizes}

Back in the day when C was invented, it was considered important that the size
of C's integral types not need to be the same everywhere, but rather match a
given processor's word size.  Decades later, that opinion is not always held.
Nonetheless, while the ANSI C specification says that a \texttt{char} shall be
one byte (always), for the rest it only requires that \texttt{sizeof(short)}
$\le$ \texttt{sizeof(int)} $\le$ \texttt{sizeof(long)}.

Having said that, I can also say that the following is true:

\begin{itemize}

\item For every machine I've worked on in the last decade, a \texttt{short} is
2 bytes and an \texttt{int} is 4.

\item For Windows 3.1 and earlier, an \texttt{int} was 2 bytes.  But Windows
3.1 is fast becoming history.  For Windows 9x and above, an \texttt{int} is 4
bytes.

\item For any 32-bit Unix or Linux system, an \texttt{int} is 4 bytes.

\item A \texttt{long} is usually 4 bytes, with the exception of some 64-bit
systems where it may be 8 bytes.

\item The \texttt{long long} type is not standard, but is very common and is
typically implemented by the GNU C compiler (GCC).  When present, it is always
(in my experience) 8 bytes.

\item The \texttt{sizeof} operator will always tell you the sizes of the
various data types for your system.

\end{itemize}

What this means is that in most of the previous decade, and in the current
decade, on everyday PC and workstation hardware (which nowadays typically have
32-bit processors), an \texttt{int} is 4 bytes.  I tell you this not to
encourage sloppiness, but rather to clue you to some of the assumptions you
will see other people make.

If you are writing code on a system for which you know the data sizes used by
your compiler, you may wish to simply use \texttt{unsigned} for your
polynomials.  (This is shorthand for \texttt{unsigned int}; signed vs.
unsigned will be explained below).  If you wish to write portable code (e.g.
something your peers can safely use on their Alphas or Sparc 64's, something
which you can safely re-use on your next project 5 years from now, something
which won't break when you port it from your 32-bit PC test environment to the
8-bit embedded processor on your production system, etc.), your best bet is to
make a header file something like the following:

\begin{verbatim}
// This file is named mytypes.h
#ifndef MYTYPES_H
#define MYTYPES_H // Protect against multiple inclusions
typedef unsigned char      int8u;
typedef          char      int8s;
typedef unsigned short     int16u;
typedef          short     int16s;
typedef unsigned int       int32u;
typedef          int       int32s;
typedef unsigned long long int64u;
typedef          long long int64s;
#endif // MYTYPES_H
\end{verbatim}

Then, (a) include this header file in all your sources, using \texttt{\#include
"mytypes.h"}; (b) always use \texttt{int32u} etc. instead of plain C types; (c)
when you port your code to some other environment, you'll only need to change
that one header file.

In this document, I'll always use \texttt{unsigned}.

A final note about the longer and shorter data sizes:  compilers \emph{do} take
care of them for you.  A common misconception among hardware folks is that
processors can only load and store in multiples of their word size, where the
word size is defined to be the number of bits in CPU registers.  This is simply
not true.  A 32-bit general-purpose processor has 8-bit, 16-bit and 32-bit load
and store operations.  A 16-bit processor has 8-bit and 16-bit load and store
operations.  A 64-bit processor has 8-, 16-, 32- and 64-bit load and store
operations.  For data types larger than the processor's word size, the compiler
will issue as many load/store operations as necessary.  E.g. if you have a
32-bit processor, you can use 64-bit \texttt{long long} values and rest assured
that the compiler will generate a pair of 32-bit load operations to read one of
these variables from memory, and a pair of 32-bit store operations to write
them to memory.  Likewise, the compiler will take care of the carry-ins and
carry-outs across machine words needed to add, subtract, multiply and divide
data types longer than the CPU word size (e.g. 32-bit \texttt{long} on a 16-bit
processor, or 64-bit \texttt{long long} on a 32-bit processor).

%% ----------------------------------------------------------------
\section{Signed vs. unsigned}

Unlike Java and Fortran, the C language provides signed and unsigned versions
of integer types.  Addition and subtraction produce the same results, bit for
bit, regardless of signedness.  The key differences in arithmetic are (1)
integer division and (2) right-shift operations.  The details of both, and
twos' complement arithmetic in general, are simple enough but are beyond the
scope of this paper (see e.g.  the excellent treatment in chapter 4 of Hennessy
and Patterson \cite{bib:hp}).  For the current discussion, in which we will do
mainly bitwise operations and left shifts, the difference is not too important.
Nonetheless, I'll use unsigned arithmetic.

%% ----------------------------------------------------------------
\section{Representation of integers}

As mentioned above, the C language provides several integral types.  For the
sake of discussion, I'll assume 32-bit words and use type \texttt{unsigned}.
The zero integer is represented with all bits zero, i.e. 0x00000000.  The value
1 is 0x00000001, where the right-hand side\footnote{We write it this way
regardless of the CPU's byte endianness, i.e. byte order within larger integral
types.  Nothing being discussed in this paper is endianness-dependent.} is the
\textbf{least significant bit}.  The left-hand side is the \textbf{most
significant bit}.  We count in the obvious way in base two.

Notice that 32-bit unsigned integers thus have a range from 0 to $2^{32}-1 =
4,294,967,295$; 16-bit unsigned integers range from 0 to $2^{16}-1 = 65,535$;
8-bit unsigned integers range from 0 to $2^{8}-1 = 255$.

%% ----------------------------------------------------------------
\section{Integer arithmetic}

There's a lot to say about computer integer arithmetic, most of it not relevant
to us (again, see chapter 4 of Hennessey and Patterson \cite{bib:hp} for
complete information).  However, I do want to point out, for use below, what
addition looks like.  Suppose you want to add 13 and 14.  In binary, these are
1101 and 1110.  The addition looks like:

\begin{verbatim}
  1101
+ 1110
------
 11011
\end{verbatim}

which is 27 in decimal and checks out.  Note in particular how you do this:
just as in elementary school (but now with base 2, not base 10), add columns
from right to left, carrying out and carrying in if necessary.  Note in
particular that a given bit in the output can depend on \emph{all} the input
bits above and to the right.

I won't discuss machine arithmetic for subtraction, multiplication and
division, although you can probably guess that they can be implemented using
elementary-school methods.  However, I will point out the following properties
of integer arithmetic in C, some of which often come as a surprise to
engineers, and at least one of which is distasteful to mathematicians:

\begin{itemize}

\item All arithmetic is performed modulo $2^n$ where $n$ is the number of bits
of the data type being operated on\footnote{I won't discuss mixing data types,
e.g. what happens when you multiply a \texttt{short} times a \texttt{long} and
storing the result in an \texttt{int}.}, i.e. 8, 16, 32 or 64.

For addition, this may not be too much of a surprise.  However, when you
multiply two $n$-bit integers, the full product can be as much as $2n$ bits.
Moreover, some CPU architectures (e.g. MIPS) provide an instruction which takes
two 32-bit operands and produces a 64-bit product.  This is accessible from
MIPS assembler, but not directly from C.  Hardware people are often surprised
by this discarding of data.

Most importantly, C provides absolutely no automatic exception handling for
overflow cases (although CPUs generally do raise an exception at the hardware
level when a divide by zero is attempted).  If you are concerned about integer
overflow, you must check for it\footnote{Note that IEEE floating-point
arithmetic is completely different in this regard: \texttt{Inf} is used for
overflow situations, \texttt{NaN} for $0/0$ and other oddities.}.

\item Division of two integers produces another integer, not a rational or a
float.  Using Euclid's algorithm, given $a$ and $b$ we write $a = qb+r$.  The C
statement \texttt{q = a / b} produces precisely that quotient; the C statement
\texttt{r = a \% b} produces the remainder.  (C does not provide rational
arithmetic, although you can easily implement your own rational data structure
and corresponding functions.  And if you want a floating-point quotient, unlike
in Perl, you must first cast to \texttt{float} or \texttt{double}.)

For example, in C, $7/2$ is $3$.

\item Using Euclid's division algorithm, we generally take $0 \le r < b$.
However, C's mod operator does not do this.  If $a < 0$, then $r < 0$.  This is
mathematically repugnant, but someone felt it important enough to design it
into the language.  For example, we think of 8 mod 5 as being 3, just as $-12$
mod 5 is 3.  But in C, the former is 3 and the latter is -2.

To produce a mathematically correct mod, use C's mod, then add $b$ if
the result is negative.  For example:
\begin{verbatim}
static __inline__ int posmod(int a, int b)
{
        int r = a % b;
        if (r < 0)
                r += b;
        return r;
}
\end{verbatim}

\end{itemize}

%% ----------------------------------------------------------------
\section{Bit numbering in C}

In C, the least significant bit is numbered 0; the most significant bit is
numbered $n-1$ for $n$-bit integers\footnote{This has absolutely nothing to
with hardware bit ordering at the schematic level (PowerPC calls the MSB the 0
bit), which is invisible to software.}.  The following idioms are often seen:

\begin{verbatim}
        unsigned x = 1 << 5;
\end{verbatim}

This results in 0x20, which is $2^5$.  In general, \texttt{1<<n} is $2^n$
although please remember that we are working with fixed word sizes\footnote{
GP, along with most computer algebra systems, implements arbitrary precision
arithmetic.  In this section, though, I'm focusing on low-level implementations
such as are encountered in the engineering world, where fixed word sizes are
the norm.}, so don't expect \texttt{1<<397} to be $2^{397}$.

Here is a partial table:

\begin{tabular}{|r|rrrrrrrr|}
\hline    \texttt{n} &    0 &    1 &    2 &    3 &    4 &    5 &    6 &    7 \\
\hline \texttt{1<<n} & 0x01 & 0x02 & 0x04 & 0x08 & 0x10 & 0x20 & 0x40 & 0x80 \\
\hline
\end{tabular}

%% ----------------------------------------------------------------
\section{Representation of polynomials}

Remember that we are working with $p=2$, so all polynomial coefficients are 0
or 1.  A polynomial $\sum_{i=0}^n a_i x^i$ is represented by setting the $i$th
bit to $a_i$.  For example, $$x^4 + x + 1 = 10011 = 0x13$$

Finite-field elements are represented no differently.  As with the compact
notation introduced in section \ref{sec:computation_in_fp_x} (which was really
me writing in binary), the $x$ or the $u$ disappears and is inferred by
context.  So $u^2+u$ would be 0110, or 0x06.

%% ----------------------------------------------------------------
\section{Addition using XOR}

Addition in $\F_2$ is simply addition mod 2.  Here is an addition table:

\begin{tabular}{|c||c|c|}
\hline $+$ & 0 & 1 \\
\hline
\hline 0   & 0 & 1 \\
\hline 1   & 1 & 0 \\
\hline
\end{tabular}

The logic people (see also \cite{bib:hh}) have another name for this function
from $\F_2 \times \F_2$ to $\F_2$:  the \textbf{exclusive OR}.  If we put on
our logic hats and think of 0 as corresponding to \textbf{false} and 1 as
corresponding to \textbf{true}, then the result (the sum) of two inputs is true
if one \emph{or} the other is true, but not both (hence the \emph{exclusive}
part).

What about addition of polynomials?  Just as before, we add componentwise, with
no carries.  For example, suppose we want to compute the sum of $x^3+x^2+1$ and
$x^3+x^2+x$.  In binary, these are 1101 and 1110.  The addition looks like:

\begin{verbatim}
  1101
+ 1110
------
  0011
\end{verbatim}

which is $x+1$ and checks out.  Note that this is like integer addition, but
\emph{without the carries}.  In particular, a given bit in the output depends
\emph{only} on the input bits above it.  Thus, XORing an integer is a
\textbf{bitwise operation}:  each bit in the output depends only on the
corresponding bits in the input.

All processors implement XOR instructions.  This is a single instruction, which
completes in a single clock cycle or so\footnote{Non-pipelined systems
notwithstanding.}, and is very fast, as compared to, say, integer
multiplication or division.  At the hardware level, it requires very simple
circuitry --- again, in contrast to integer multiplication or division.  In
particular, note that for an $n$-bit processor we get $n$ bit additions all at
the same time.  This is why finite-field arithmetic with $p=2$ is so efficient.
In a hardware design, one is not limited to 32-bit or 64-bit words, etc.:  One
can declare very wide bit arrays and have all those XORs going on in parallel.

In C, this is spelled very simply.  The XOR operator is a single caret.  For
example, let's compute the sum of $x^3+x^2+1$ and $x^3+x^2+x$.  In hex, these
are 0xd and 0xe.  The addition looks like:

\begin{verbatim}
        unsigned a = 0xd;
        unsigned b = 0xe;
        unsigned c = a ^ b;
\end{verbatim}

%% ----------------------------------------------------------------
\section{Scalar multiplication using AND}

Multiplication in $\F_2$ is simply multiplication mod 2.  Here is a
multiplication table:

\begin{tabular}{|c||c|c|}
\hline $\cdot$ & 0 & 1 \\
\hline
\hline 0       & 0 & 0 \\
\hline 1       & 0 & 1 \\
\hline
\end{tabular}

The logic people have another name for this function from $\F_2 \times \F_2$ to
$\F_2$:  the \textbf{AND}.  Again thinking of 0 as false and 1 as true, then
the result (the product) of two inputs is true if one is true \emph{and} the
other is true.

%% ----------------------------------------------------------------
\section{Bit-manipulation paradigms}

C has several bitwise operators:  AND, OR, XOR, NOT, LEFT-SHIFT and
RIGHT-SHIFT.  They all have standard uses which you will encounter.

\begin{itemize}

\item XOR:  We've seen this already for polynomial addition.  Also, it can
	be used to \emph{toggle} one or more bits.  For example:
\begin{verbatim}
        int i;
        unsigned x = 0xee;
        for (i = 0; i < 10; i++)
                x ^= 0x02;
\end{verbatim}
	This will repeatedly toggle bit 1 (remember bit numbers start at
	0 on the right) of the given value, resulting in the sequence
	0xee, 0xec, 0xee, 0xec, \ldots.

\item OR:  This \textbf{binary operator} (i.e. it takes two inputs) produces
	output 1 if either one input is 1, \emph{or} the other input is 1.
	Unlike XOR for $+$ and AND for $\cdot$, it doesn't have as clear
	a mathematical meaning.  However it pops up a lot in the \textbf{bit
	set} idiom:
\begin{verbatim}
        unsigned x = 0xa0;
        x |= 1;
\end{verbatim}
	This \textbf{sets} bits 0, whether it was set or not.  If bit 0
	is already known to be a 0, then this is equivalent to adding 1.

\item NOT:  This \textbf{unary operator} (i.e. it takes one input)
	\textbf{negates} its input, i.e. turns 1 bits to 0 bits and vice
	versa.  It is spelt with a tilde, as follows:
\begin{verbatim}
        unsigned a =  0xa0;
        unsigned b = ~a;
\end{verbatim}
	This is often used in conjunction with the AND operator, as we will
	see.

\item AND:  We've seen this already for scalar multiplication.  It crops up
	much more often, though, in two idioms:

	The \textbf{bit test} operation sees if certain bits are set.
	For example:
\begin{verbatim}
        if (x & 0x10)
                x ^= 0x13;
\end{verbatim}
	Here, if \texttt{x} has bit 4 set, then bits 4, 1 and 0 are
	toggled.

	The \textbf{bit clear} idiom uses AND and NOT.  For example:
\begin{verbatim}
        x &= ~0x20;
\end{verbatim}
	This means, clear bit 5.

\item LEFT-SHIFT and RIGHT-SHIFT:  For left shift, each bit is moved
	one position to the left.  The old most significant bit is shifted off;
	a zero bit moves in to fill the empty spot in the least significant
	bit.  For right shift, the least significant bit is shifted off the
	right; if the input is unsigned, a zero bit moves in to fill the
	vacancy on the left\footnote{For signed integers, \emph{sign extension}
	is used on right shift, i.e.  the new MSB takes the value of the old
	MSB.  This is perfectly appropriate from an integer-arithmetic point of
	view, since a right shift corresponds to integer division by 2 and we
	want, say, $-12/2$ to be $-6$.  However, for our purposes here, doing
	polynomial rather than integer arithmetic, we always want unsigned
	arithmetic.  In fact this is the only point at which signed vs.
	unsigned matters for us.}.

	For example:
\begin{verbatim}
        int i;
        unsigned x = 1;

        for (i = 0; i < 4; i++) {
                printf(" %02x", x);
                x <<= 1;
        }
        for (i = 0; i < 4; i++) {
                printf(" %02x", x);
                x >>= 1;
        }
        printf("\n");
\end{verbatim}
	This prints out 0x01, 0x02, 0x04, 0x08, 0x10, 0x08, 0x04, 0x02.

\end{itemize}

%% ----------------------------------------------------------------
\section{Field multiplication using shifts and XORs}

Field multiplication is as described in section \ref{sec:RAR_and_RER}.  We just
need to remember that we are getting a no-brained piece of silicon to do our
work for us, so we need to spell out some things that you and I would take for
granted.  For example, what's the degree of a polynomial?  You know just at a
glance.  For a particular application, of course your polynomial degree is
probably known ahead of time.  But for general-purpose use, the following will
do\footnote{There are several obvious ways to optimize this as well, but the
current implementation is preferred for clarity.}:
\begin{verbatim}
unsigned polydeg(unsigned r)
{
        int d = 0;
        if (r == 0) {
                return 0;
                // Or, treat this as an error condition, depending on
                // how you want to handle the degree of the zero polynomial.
                // For my purposes, it suffices to assign it degree zero, just
                // like all the other constant polynomials.
        }
        while (r >>= 1)
                d++;
        return d;
}
\end{verbatim}

Given that, the following will suffice to perform multiplications.  Again, for
a given implementation you'll probably know your degree so you won't have to
search for it, and the loops could be unrolled etc.

\begin{verbatim}
unsigned ffmul(unsigned a, unsigned b, unsigned r)
{
        int degb = polydeg(b);
        int degr = polydeg(r);
        unsigned bit_at_deg = 1 << degr;
        unsigned prod = 0;
        unsigned temp;
        int i, power;

        for (i = 0; i <= degb; i++) {
                // Test if this bit position is set.
                if (!(b & (1 << i)))
                        continue;

                // Now multiply a by the power of x on the current term
                // of b, reducing mod r en route.
                temp = a;
                for (power = 1; power <= i; power++) {
                        temp <<= 1;
                        if (temp & bit_at_deg)  // If x^n appears,
                                temp ^= r;      // then subtract r(x).
                }
                // Add in this partial product.
                prod ^= temp;
        }

        return prod;
}
\end{verbatim}

Note the use of several bit-manipulation paradigms.

%% ----------------------------------------------------------------
\section{Repeated squaring}

Repeated squaring is easy to implement in software, since it matches up with
binary arithmetic.  For example:

\begin{verbatim}
unsigned ffpower(
        unsigned  a,
        int power, // This handles positive powers only.
        unsigned  r)
{
        unsigned a2 = a;
        unsigned out = 1;

        while (power != 0) {
                if (power & 1) // Test current bit
                        out = ffmul(out, a2, r);
                power = (unsigned)power >> 1; // Prepare to test next bit
                a2 = ffmul(a2, a2, r);
        }
        return out;
}
\end{verbatim}

As described in section \ref{sec:repeated_squaring}, we form $a$, $a^2$, etc.
(in the \texttt{a2} variable), but include in our result (\texttt{out}) only
the correct ones.

%% ----------------------------------------------------------------
\section{Reciprocation and division}

Given repeated squaring, it's easy to recriprocate.  Using Lagrange's theorem
as described in section \ref{sec:pn2_recip}, we can reciprocate by raising to
the $p^n-2$ power:
\begin{verbatim}
unsigned ffrecip(unsigned b, unsigned r)
{
        int n = polydeg(r);
        int pn2 = (1 << n) - 2; // Incorrect if n == 0.
        if (b == 0) {
                ... Handle the divide-by-zero error as you wish.
        }
        return ffpower(b, pn2, r);
}
\end{verbatim}

Then, $a/b$ is $a \cdot (b^{-1})$:
\begin{verbatim}
unsigned ffdiv(unsigned a, unsigned b, unsigned r)
{
        unsigned binv;
        binv = ffrecip(b, r);
        return ffmul(a, binv, r);
}
\end{verbatim}

%% ----------------------------------------------------------------
\section{Arithmetic with implicit leading one}

xxx add is the same

xxx hard-code polydeg calls

xxx re-write mul

%% ----------------------------------------------------------------
\section{Polynomial basis vs. log domain}

%% ----------------------------------------------------------------
\section{Table lookups}


xxx lexical ordering

xxx dissect the schneier examples, and attribute them.

xxx more about why Gal cfg is easier in C

% CRC-explained ref

% heroes: golomb, berlekamp, shanks, ... ?

% bib & cites to # style
% HP Ch. 4 ref
