%% ================================================================
\part{Appendices}
\appendix

%% ================================================================
\newpage
\chapter{Tables}

%% ----------------------------------------------------------------
\section{Tables of some irreducible polynomials in $\F_p[x]$}
\label{appx:tables_of_irreds_in_Fp}

Primitive polynomials are marked with an asterisk.  Please see Lidl and
Niederreiter \cite{bib:ln} for much more extensive tables.

\begin{tabular}{|rr|rr|rr|rr|rr|rr|}
\hline $\F_{2^2}$ && $\F_{2^3}$ && $\F_{2^4}$ && $\F_{2^5}$ && $\F_{2^6}$ &\\
\hline
111  &*    &1011 &*    &10011 &*    &100101 &*    &1000011 &* \\
     &     &1101 &*    &11001 &*    &101001 &*    &1001001 &  \\
     &     &     &     &11111 &     &101111 &*    &1010111 &  \\
     &     &     &     &      &     &110111 &*    &1011011 &* \\
     &     &     &     &      &     &111011 &*    &1100001 &* \\
     &     &     &     &      &     &111101 &*    &1100111 &* \\
     &     &     &     &      &     &       &     &1101101 &* \\
     &     &     &     &      &     &       &     &1110011 &* \\
     &     &     &     &      &     &       &     &1110101 &  \\
\hline
\end{tabular}

\begin{tabular}{|rr|rr|}
\hline $\F_{3^2}$ && $\F_{3^3}$ & \\
\hline
101  &     &  1021  & * \\
112  &*    &  1022  &   \\
122  &*    &  1102  &   \\
     &     &  1112  &   \\
     &     &  1121  & * \\
     &     &  1201  & * \\
     &     &  1211  & * \\
     &     &  1222  &   \\
\hline
\end{tabular}

%% ----------------------------------------------------------------
\section{Some primitive irreducible polynomials in $\F_{2^n}$}
\label{appx:F2_prims}

%% xxx make a nice table, and incl. tap points (bit numbers)
%% \begin{verbatim}
%%  n         r in hex      tap bits
%%  -         --------      --------
%%  1                3             0          
%%  2                7           1 0        
%%  3                b           1 0        
%%  4               13           1 0        
%%  5               25           2 0        
%%  6               43           1 0        
%%  7               83           1 0        
%%  8              11d       4 3 2 0    
%%  9              211           4 0        
%% 10              409           3 0        
%% 11              805           2 0        
%% 12             1053       6 4 1 0    
%% 13             201b       4 3 1 0    
%% 14             402b       5 3 1 0    
%% 15             8003           1 0        
%% 16            1002d       5 3 2 0    
%% 17            20009           3 0        
%% 18            40027       5 2 1 0    
%% 19            80027       5 2 1 0    
%% 20           100009           3 0        
%% 21           200005           2 0        
%% 22           400003           1 0        
%% 23           800021           5 0        
%% 24          100001b       4 3 1 0    
%% 25          2000009           3 0        
%% 26          4000047       6 2 1 0    
%% 27          8000027       5 2 1 0    
%% 28         10000009           3 0        
%% 29         20000005           2 0        
%% 30         40000053       6 4 1 0    
%% 31         80000009           3 0        
%% 32        1000000af   7 5 3 2 1 0
%% 33        200000053       6 4 1 0    
%% 34        40000001b       4 3 1 0    
%% 35        800000005           2 0        
%% 36       100000003f   5 4 3 2 1 0
%% 37       200000003f   5 4 3 2 1 0
%% 38       4000000063       6 5 1 0    
%% 39       8000000011           4 0        
%% 40      10000000039       5 4 3 0    
%% 41      20000000009           3 0        
%% 42      40000000027       5 2 1 0    
%% 43      80000000059       6 4 3 0    
%% 44     100000000021           5 0        
%% 45     20000000001b       4 3 1 0    
%% 46     400000000003           1 0        
%% 47     800000000021           5 0        
%% 48    100000000002d       5 3 2 0    
%% 49    2000000000071       6 5 4 0    
%% 50    400000000001d       4 3 2 0    
%% 51    800000000004b       6 3 1 0    
%% 52   10000000000009           3 0        
%% 53   20000000000047       6 2 1 0    
%% 54   4000000000007d   6 5 4 3 2 0
%% 55   80000000000047       6 2 1 0    
%% 56  100000000000095       7 4 2 0    
%% 57  200000000000011           4 0        
%% 58  400000000000063       6 5 1 0    
%% 59  80000000000007b   6 5 4 3 1 0
%% 60 1000000000000003           1 0        
%% 61 2000000000000027       5 2 1 0    
%% 62 4000000000000069       6 5 3 0    
%% 63 8000000000000003           1 0        

\begin{tabular}{|r|r|r||r|r|r|}
\hline
$n$ & $r$ in hex & Tap bits & $n$ & $r$ in hex & Tap bits \\
\hline
\hline 1&               3&            0&  33&       200000053&      6 4 1 0\\
\hline 2&               7&          1 0&  34&       40000001b&      4 3 1 0\\
\hline 3&               b&          1 0&  35&       800000005&          2 0\\
\hline 4&              13&          1 0&  36&      100000003f&  5 4 3 2 1 0\\
\hline 5&              25&          2 0&  37&      200000003f&  5 4 3 2 1 0\\
\hline 6&              43&          1 0&  38&      4000000063&      6 5 1 0\\
\hline 7&              83&          1 0&  39&      8000000011&          4 0\\
\hline 8&             11d&      4 3 2 0&  40&     10000000039&      5 4 3 0\\
\hline 9&             211&          4 0&  41&     20000000009&          3 0\\
\hline 10&             409&          3 0&  42&     40000000027&      5 2 1 0\\
\hline 11&             805&          2 0&  43&     80000000059&      6 4 3 0\\
\hline 12&            1053&      6 4 1 0&  44&    100000000021&          5 0\\
\hline 13&            201b&      4 3 1 0&  45&    20000000001b&      4 3 1 0\\
\hline 14&            402b&      5 3 1 0&  46&    400000000003&          1 0\\
\hline 15&            8003&          1 0&  47&    800000000021&          5 0\\
\hline 16&           1002d&      5 3 2 0&  48&   100000000002d&      5 3 2 0\\
\hline 17&           20009&          3 0&  49&   2000000000071&      6 5 4 0\\
\hline 18&           40027&      5 2 1 0&  50&   400000000001d&      4 3 2 0\\
\hline 19&           80027&      5 2 1 0&  51&   800000000004b&      6 3 1 0\\
\hline 20&          100009&          3 0&  52&  10000000000009&          3 0\\
\hline 21&          200005&          2 0&  53&  20000000000047&      6 2 1 0\\
\hline 22&          400003&          1 0&  54&  4000000000007d&  6 5 4 3 2 0\\
\hline 23&          800021&          5 0&  55&  80000000000047&      6 2 1 0\\
\hline 24&         100001b&      4 3 1 0&  56& 100000000000095&      7 4 2 0\\
\hline 25&         2000009&          3 0&  57& 200000000000011&          4 0\\
\hline 26&         4000047&      6 2 1 0&  58& 400000000000063&      6 5 1 0\\
\hline 27&         8000027&      5 2 1 0&  59& 80000000000007b&  6 5 4 3 1 0\\
\hline 28&        10000009&          3 0&  60&1000000000000003&          1 0\\
\hline 29&        20000005&          2 0&  61&2000000000000027&      5 2 1 0\\
\hline 30&        40000053&      6 4 1 0&  62&4000000000000069&      6 5 3 0\\
\hline 31&        80000009&          3 0&  63&8000000000000003&          1 0\\
\hline 32&       1000000af&  7 5 3 2 1 0&  64&1000000000000001b&     4 3 1 0\\
\hline
\end{tabular}

%% ----------------------------------------------------------------
\section{Some logarithm tables for $\Fpn$}
\label{appx:Fp_log_tables}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=111$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 3 &01 &1 \\
\hline 1 &10 &3 \\
\hline 2 &11 &3 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=111$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 1 &10 &3 \\
\hline 2 &11 &3 \\
\hline 3 &01 &1 \\
\hline
\end{tabular}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=1011$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 7 &001 &1 \\
\hline 1 &010 &7 \\
\hline 3 &011 &7 \\
\hline 2 &100 &7 \\
\hline 6 &101 &7 \\
\hline 4 &110 &7 \\
\hline 5 &111 &7 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=1011$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 1 &010 &7 \\
\hline 2 &100 &7 \\
\hline 3 &011 &7 \\
\hline 4 &110 &7 \\
\hline 5 &111 &7 \\
\hline 6 &101 &7 \\
\hline 7 &001 &1 \\
\hline
\end{tabular}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=1101$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 7 &001 &1 \\
\hline 1 &010 &7 \\
\hline 5 &011 &7 \\
\hline 2 &100 &7 \\
\hline 3 &101 &7 \\
\hline 6 &110 &7 \\
\hline 4 &111 &7 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=1101$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 1 &010 &7 \\
\hline 2 &100 &7 \\
\hline 3 &101 &7 \\
\hline 4 &111 &7 \\
\hline 5 &011 &7 \\
\hline 6 &110 &7 \\
\hline 7 &001 &1 \\
\hline
\end{tabular}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=10011$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 15 & 0001 &  1 \\
\hline  1 & 0010 & 15 \\
\hline  4 & 0011 & 15 \\
\hline  2 & 0100 & 15 \\
\hline  8 & 0101 & 15 \\
\hline  5 & 0110 &  3 \\
\hline 10 & 0111 &  3 \\
\hline  3 & 1000 &  5 \\
\hline 14 & 1001 & 15 \\
\hline  9 & 1010 &  5 \\
\hline  7 & 1011 & 15 \\
\hline  6 & 1100 &  5 \\
\hline 13 & 1101 & 15 \\
\hline 11 & 1110 & 15 \\
\hline 12 & 1111 &  5 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=10011$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline  1 & 0010 & 15 \\
\hline  2 & 0100 & 15 \\
\hline  3 & 1000 &  5 \\
\hline  4 & 0011 & 15 \\
\hline  5 & 0110 &  3 \\
\hline  6 & 1100 &  5 \\
\hline  7 & 1011 & 15 \\
\hline  8 & 0101 & 15 \\
\hline  9 & 1010 &  5 \\
\hline 10 & 0111 &  3 \\
\hline 11 & 1110 & 15 \\
\hline 12 & 1111 &  5 \\
\hline 13 & 1101 & 15 \\
\hline 14 & 1001 & 15 \\
\hline 15 & 0001 &  1 \\
\hline
\end{tabular}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=11001$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 15 & 0001 &  1 \\
\hline  1 & 0010 & 15 \\
\hline 12 & 0011 &  5 \\
\hline  2 & 0100 & 15 \\
\hline  9 & 0101 &  5 \\
\hline 13 & 0110 & 15 \\
\hline  7 & 0111 & 15 \\
\hline  3 & 1000 &  5 \\
\hline  4 & 1001 & 15 \\
\hline 10 & 1010 &  3 \\
\hline  5 & 1011 &  3 \\
\hline 14 & 1100 & 15 \\
\hline 11 & 1101 & 15 \\
\hline  8 & 1110 & 15 \\
\hline  6 & 1111 &  5 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=11001$, $g=10$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline  1 & 0010 & 15 \\
\hline  2 & 0100 & 15 \\
\hline  3 & 1000 &  5 \\
\hline  4 & 1001 & 15 \\
\hline  5 & 1011 &  3 \\
\hline  6 & 1111 &  5 \\
\hline  7 & 0111 & 15 \\
\hline  8 & 1110 & 15 \\
\hline  9 & 0101 &  5 \\
\hline 10 & 1010 &  3 \\
\hline 11 & 1101 & 15 \\
\hline 12 & 0011 &  5 \\
\hline 13 & 0110 & 15 \\
\hline 14 & 1100 & 15 \\
\hline 15 & 0001 &  1 \\
\hline
\end{tabular}

\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Log} \\
\multicolumn{3}{c}{$p=2$, $r=11111$, $g=11$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline 15 & 0001 &  1 \\
\hline 12 & 0010 &  5 \\
\hline  1 & 0011 & 15 \\
\hline  9 & 0100 &  5 \\
\hline  2 & 0101 & 15 \\
\hline 13 & 0110 & 15 \\
\hline  7 & 0111 & 15 \\
\hline  6 & 1000 &  5 \\
\hline  8 & 1001 & 15 \\
\hline 14 & 1010 & 15 \\
\hline 11 & 1011 & 15 \\
\hline 10 & 1100 &  3 \\
\hline  5 & 1101 &  3 \\
\hline  4 & 1110 & 15 \\
\hline  3 & 1111 &  5 \\
\hline
\end{tabular}
\begin{tabular}{|r|r|r|}
\multicolumn{3}{c}{Antilog} \\
\multicolumn{3}{c}{$p=2$, $r=11111$, $g=11$} \\
\hline $k$ & $g^k$ & order\\
\hline
\hline  1 & 0011 & 15 \\
\hline  2 & 0101 & 15 \\
\hline  3 & 1111 &  5 \\
\hline  4 & 1110 & 15 \\
\hline  5 & 1101 &  3 \\
\hline  6 & 1000 &  5 \\
\hline  7 & 0111 & 15 \\
\hline  8 & 1001 & 15 \\
\hline  9 & 0100 &  5 \\
\hline 10 & 1100 &  3 \\
\hline 11 & 1011 & 15 \\
\hline 12 & 0010 &  5 \\
\hline 13 & 0110 & 15 \\
\hline 14 & 1010 & 15 \\
\hline 15 & 0001 &  1 \\
\hline
\end{tabular}

%% ================================================================
\newpage
\chapter{Storage representations}

We've already seen a few different ways to represent elements of finite fields,
using the canonical embodiment $\F_p[x]/\langle r(x) \rangle$:

\begin{itemize}
\item As equivalence classes of remainders mod $r$, e.g.
	$x^2 + x + \langle x^4 + x + 1 \rangle$.
\item As $\F_p[u] \cong \F_p[x] / \langle r(x) \rangle$, with $u$ a root
	of $r(x)$, e.g. $u^2 + u$.
\item As an array or $n$-tuple of coefficients, e.g. $[0,1,1,0]$ or $(0,1,1,0)$
	but usually written just $0110$.
\end{itemize}

There are some other notations that are also encountered in the literature:

\begin{itemize}
\item As logarithms, as discussed above.  This is sometimes referred to as the
	\bfidx{log domain}.  It leaves you with the question of how to write 0,
	which doesn't have a log.
\item We can treat an $n$-tuple of coefficients as a base-$p$ integer, then
	convert bases from $p$ to 10.  E.g. elements of $\F_{2^4}$ would then
	convert from $0000$, $0001$, $0010$, \ldots, $1111$ to 0, 1, 2, \ldots,
	15.  Since this is decimal, it looks confusingly like arithmetic mod
	$p^n$ but of course, unless $n=1$, it's not (which is one reason I
	don't like this notation).
\item For base $p=2$, engineers often use base-16 or \bfidx{hexadecimal}
	notation.  For digits, use 0-9 for 0-9 and a-f (or A-F, depending on
	personal preference) for 11-15; prefix with 0x to distinguish from
	decimal.  E.g. $1010$ is 10 in decimal, which is 0xa in hex.  Likewise,
	$10101110$ is 0xae in hex.  The three monic irreducibles in $\F_{2^4}$
	are written 0x13, 0x19 and 0x1f; 0x104c11db7 is a degree-32
	irreducible, primitive polynomial in $\F_2[x]$ (which incidentally is
	used for error detection in Ethernet networking); the AES polynomial
	\cite{bib:aes} is 0x11b.
\end{itemize}
