%\input{t1}
%% ================================================================
\part{Linear feedback shift registers}
\label{part:LFSRs}

%% ================================================================
\chapter{Linear feedback shift registers}

Linear feedback shift registers are perhaps the single most important
application of finite fields.  They are used extensively in cryptography; many
(although not all) cryptosystems use them.  They are also used in coding
theory, e.g. in the computation of cyclic redundancy checks (CRCs) in
networking and disk-drive controllers.  As well, LFSRs are used in various
applications to generate pseudo-random sequences of bits.

The standard reference for LFSRs is Golomb \cite{bib:golomb} (although my
discussion of the linear theory differs from Golomb's in that I use abstract
and linear algebra, eschewing generating functions entirely).  Also see Lidl
and Niederreiter \cite{bib:ln}, Schneier \cite{bib:sch} and Berlekamp
\cite{bib:berl}.

%% ================================================================
\section{The physical setup}

%% ----------------------------------------------------------------
%\section{Registers}

% xxx xref to SW section

One often builds an electronic circuit (using discrete parts, or more often as
part of an integrated circuit) that looks as follows.  (Note that a similar
setup may easily be implemented in software.  For purposes of this discussion,
we don't much care about the specifics of the implementation, but rather about
the behavior of the system.) We have $n$ \bfidx{cells}, each containing a
single \bfidx{bit}:

\setlength{\unitlength}{1.0in}
\begin{picture}(6,0.6)
%\put(0.0,0.0){\framebox(6.0,0.6)}
\put(1.0,0.25){\framebox(0.5,0.2){$v_{n-1}$}}
\put(2.0,0.25){\framebox(0.5,0.2){$v_{n-2}$}}
\put(3.0,0.25){\framebox(0.5,0.2){$\ldots$}}
\put(4.0,0.25){\framebox(0.5,0.2){$v_1$}}
\put(5.0,0.25){\framebox(0.5,0.2){$v_0$}}
\end{picture}

Mathematically, we think of bits as being 0 or 1, i.e. elements of the finite
field $\F_2$.  In fact the analysis works fine when the cells contain elements
of $\F_q$ where $q$ is a prime power, but the most important $q$ is 2.

There is also a \bfidx{clock} or time step, such that at time step $t$ each
cell contains some value, then takes on a perhaps different value at time
$t+1$.  All $n$ cells, taken together, with the clocked updates, form a single
\bfidx{register}.

The contents of the register are a function of the previous contents.  Letting
$v$ be the $n$-tuple $(v_{n-1}, \ldots, v_0)$, we might write $v(t+1) =
f(v(t))$.  The cell contents at $t=0$ are called the \bfidx{initial
conditions} of the LFSR.  However, I prefer to make the time step implicit and
use $:=$ for assignment, e.g. $v := f(v)$.

One could analyze the set of all possible functions from $v$ to $v$.  However,
we restrict ourselves to a particular set of functions.  First, we have the
value of $v_i$ \bfidx{shift} to its neighbor $v_{i+1}$:

\setlength{\unitlength}{1.0in}
\begin{picture}(6,0.6)
%\put(0.0,0.0){\framebox(6.0,0.6)}
\put(1.0,0.25){\framebox(0.5,0.2){$v_{n-1}$}}
\put(2.0,0.25){\framebox(0.5,0.2){$v_{n-2}$}}
\put(3.0,0.25){\framebox(0.5,0.2){$\ldots$}}
\put(4.0,0.25){\framebox(0.5,0.2){$v_1$}}
\put(5.0,0.25){\framebox(0.5,0.2){$v_0$}}
\put(0.3,0.30){?}
\put(1.0,0.35){\vector(-1,0){0.5}}
\put(2.0,0.35){\vector(-1,0){0.5}}
\put(3.0,0.35){\vector(-1,0){0.5}}
\put(4.0,0.35){\vector(-1,0){0.5}}
\put(5.0,0.35){\vector(-1,0){0.5}}
\put(6.0,0.35){\vector(-1,0){0.5}}
\put(6.1,0.30){?}
\end{picture}

Clearly, this raises the question of boundary behaviors:  What do we do with
the bit that is shifted out at the left, and how do we fill the cell that was
emptied at the right?  All $n$ cells of the register are referred to as the
\bfidx{internal state} of the LFSR; the shifted-out bit is often to be the
\bfidx{output} of the LFSR.  Next is the \bfidx{feedback} part:  we fill in
the vacated cell at the right with some function of the current cell values.
In particular we focus on \bfidx{linear} functions, since (as we all know)
linear systems are so much easier to understand and control:

\setlength{\unitlength}{1.0in}
\begin{picture}(6.5,1.0)
%\put(0.0,0.0){\framebox(6.5,1.0)}
\put(1.0,0.25){\framebox(0.5,0.2){$v_{n-1}$}}
\put(2.0,0.25){\framebox(0.5,0.2){$v_{n-2}$}}
\put(3.0,0.25){\framebox(0.5,0.2){$\ldots$}}
\put(4.0,0.25){\framebox(0.5,0.2){$v_1$}}
\put(5.0,0.25){\framebox(0.5,0.2){$v_0$}}
\put(1.0,0.35){\vector(-1,0){0.5}}
\put(2.0,0.35){\vector(-1,0){0.5}}
\put(3.0,0.35){\vector(-1,0){0.5}}
\put(4.0,0.35){\vector(-1,0){0.5}}
\put(5.0,0.35){\vector(-1,0){0.5}}
\put(6.0,0.35){\vector(-1,0){0.5}}

\put(1.25,0.45){\vector(0,1){0.40}}
\put(2.25,0.45){\vector(0,1){0.40}}
\put(3.25,0.45){\vector(0,1){0.40}}
\put(4.25,0.45){\vector(0,1){0.40}}
\put(5.25,0.45){\vector(0,1){0.40}}

\put(1.25,0.85){\vector(1,0){4.25}}
\put(5.75,0.85){\line(1,0){0.25}}
\put(5.58,0.82){$f$}
\put(6.00,0.85){\line(0,-1){0.50}}
\end{picture}

%% ================================================================
\section{Non-autonomous LFSRs}

I should note at this point that there is also sometimes an external
\bfidx{input} to the LFSR:

\setlength{\unitlength}{1.0in}
\begin{picture}(6.5,1.0)
%\put(0.0,0.0){\framebox(6.5,1.0)}
\put(0.5,0.25){\framebox(0.5,0.2){$v_{n-1}$}}
\put(1.5,0.25){\framebox(0.5,0.2){$v_{n-2}$}}
\put(2.5,0.25){\framebox(0.5,0.2){$\ldots$}}
\put(3.5,0.25){\framebox(0.5,0.2){$v_1$}}
\put(4.5,0.25){\framebox(0.5,0.2){$v_0$}}
\put(0.5,0.35){\vector(-1,0){0.5}}
\put(1.5,0.35){\vector(-1,0){0.5}}
\put(2.5,0.35){\vector(-1,0){0.5}}
\put(3.5,0.35){\vector(-1,0){0.5}}
\put(4.5,0.35){\vector(-1,0){0.5}}
\put(5.4,0.35){\vector(-1,0){0.4}}

\put(0.75,0.45){\vector(0,1){0.40}}
\put(1.75,0.45){\vector(0,1){0.40}}
\put(2.75,0.45){\vector(0,1){0.40}}
\put(3.75,0.45){\vector(0,1){0.40}}
\put(4.75,0.45){\vector(0,1){0.40}}

\put(0.75,0.85){\vector(1,0){4.25}}
\put(5.25,0.85){\line(1,0){0.25}}
\put(5.08,0.82){$f$}
\put(5.50,0.85){\vector(0,-1){0.40}}

\put(5.89,0.31){$g$}
\put(5.85,0.35){\vector(-1,0){0.26}}
\put(5.44,0.31){$+$}
\end{picture}

For example, such a setup is used for computing CRCs:  The LFSR's initial
conditions are set up, and a data stream is clocked into the LFSR one bit at a
time.  The internal state of the LFSR at the end of the data stream is the
result of the computation.  There is an analogy with differential equations:
You can have a homogeneous system such as a simple harmonic oscillator.  You
supply it with initial conditions (e.g. give the pendulum a push) and then let
it run.  When an external forcing function is supplied, the behavior is
different.  Here too, an LFSR behaves differently with and without external
input.  For the present discussion I'll confine myself to input-free, or
\bfidx{autonomous}, systems.  Such are the physical systems we want to analyze.

%% ================================================================
\section{Fibonacci and Galois configurations}

For reasons not discussed in the current version of this document, LFSRs shown
in the previous section are said to be in a \bfidx{Fibonacci configuration}.
Namely, feedback goes out of all cells, back into a single cell.  Another setup
is called a \bfidx{Galois configuration}, where feedback goes out of a single
cell and into all of them:

\setlength{\unitlength}{1.0in}
\begin{picture}(6.5,1.0)
%\put(0.0,0.0){\framebox(6.5,1.0)}
\put(0.5,0.25){\framebox(0.5,0.2){$v_{n-1}$}}
\put(1.5,0.25){\framebox(0.5,0.2){$v_{n-2}$}}
\put(2.5,0.25){\framebox(0.5,0.2){$\ldots$}}
\put(3.5,0.25){\framebox(0.5,0.2){$v_1$}}
\put(4.5,0.25){\framebox(0.5,0.2){$v_0$}}

\put(0.5,0.35){\vector(-1,0){0.5}}
\put(1.5,0.35){\vector(-1,0){0.3}}
\put(2.5,0.35){\vector(-1,0){0.3}}
\put(3.5,0.35){\vector(-1,0){0.3}}
\put(4.5,0.35){\vector(-1,0){0.3}}
%\put(5.4,0.35){\vector(-1,0){0.3}}

\put(0.25,0.35){\vector(0,1){0.50}}
\put(1.10,0.85){\vector(0,-1){0.40}}
\put(2.10,0.85){\vector(0,-1){0.40}}
\put(3.10,0.85){\vector(0,-1){0.40}}
\put(4.10,0.85){\vector(0,-1){0.40}}
\put(5.10,0.85){\vector(0,-1){0.40}}

\put(1.04,0.31){$+$}
\put(2.04,0.31){$+$}
\put(3.04,0.31){$+$}
\put(4.04,0.31){$+$}
\put(5.04,0.31){$+$}

\put(0.25,0.85){\vector(1,0){0.25}}
\put(0.55,0.80){$f$}
\put(0.75,0.85){\vector(1,0){4.35}}
%\put(5.25,0.85){\line(1,0){0.25}}
%\put(5.50,0.85){\vector(0,-1){0.40}}

\put(5.49,0.31){$g$}
\put(5.45,0.35){\vector(-1,0){0.26}}
\end{picture}

The Galois configuration is used for the rest of this chapter.

%% ================================================================
\section{The transition graph}

Since there are $n$ cells, each containing an element of $\F_q$, there are
$q^n$ possible states for the LFSR.  The transition from one state to the next
is a function from a finite set to itself.  Given some initial conditions,
after at most $q^n$ transitions, there are no longer any new states to which to
transition, and the LFSRs must necessarily be in a state it has been in before.
Once in that state, it will proceed to the same successor as before.  Thus,
for given initial conditions, the sequence of states looks like this:

[picture goes here]

i.e. the sequence of states is \bfidx{eventually periodic}.  This looks like
the Greek letter $\rho$, with a \bfidx{tail} and a \bfidx{loop}.  The tail
may have length zero, in which case the LFSR returns to the initial state.  The
length of the loop is called the \bfidx{period}.  The period may be one, in
which we say that the final condition is a \bfidx{lock-up state}:  once in
such a state, the LFSR never leaves it.

Now suppose we label all $q^n$ states of the LFSR, and draw the transition
graph.  There might be lots of $\rho$'s, perhaps with hair:

[picture goes here]

where the hair indicates that two states may have the same successor.

I now declare that what is usually\footnote{At this point I must point out
that a maximal-period LFSR is not the only type of LFSR of interest.  For
example, the logic in the floppy-disk controller of your PC computes CRCs using
a 16-bit LFSR that has two lock-up states, namely all zeroes and all ones, and
two big loops, each with 32,767 states.} desired in engineering practice is
an LFSR whose transition graph has the biggest possible loop, i.e. the maximum
number of states reachable from any initial conditions.  Note that in a linear
feedback shift register, since the feedback function is linear, the all-zeroes
state must map to itself, i.e. the all-zeroes state is always a lock-up, so the
best that can be hoped for is the zero state, with a big loop of size $q^n-1$:

[picture goes here]

This is called a \bfidx{maximal-period LFSR}.  We ask, is it possible to
construct a maximal-period LFSR for any $q$ and $n$?  To avoid being coy, I'll
go ahead and say that the answer is yes.  To see how to do it is the subject of
the next section.

%% ================================================================
\section{The transition matrix}

Let's write down the LFSR transition function as a system of equations.
The system looks like this:

% Fibo config:
%\setlength{\unitlength}{1.0in}
%\begin{picture}(6.5,1.0)
%%\put(0.0,0.0){\framebox(6.5,1.0)}
%\put(1.0,0.25){\framebox(0.5,0.2){$v_{n-1}$}}
%\put(2.0,0.25){\framebox(0.5,0.2){$v_{n-2}$}}
%\put(3.0,0.25){\framebox(0.5,0.2){$\ldots$}}
%\put(4.0,0.25){\framebox(0.5,0.2){$v_1$}}
%\put(5.0,0.25){\framebox(0.5,0.2){$v_0$}}
%\put(2.0,0.35){\vector(-1,0){0.5}}
%\put(3.0,0.35){\vector(-1,0){0.5}}
%\put(4.0,0.35){\vector(-1,0){0.5}}
%\put(5.0,0.35){\vector(-1,0){0.5}}
%\put(6.0,0.35){\vector(-1,0){0.5}}
%
%\put(1.25,0.45){\vector(0,1){0.32}}
%\put(2.25,0.45){\vector(0,1){0.32}}
%\put(3.25,0.45){\vector(0,1){0.32}}
%\put(4.25,0.45){\vector(0,1){0.32}}
%\put(5.25,0.45){\vector(0,1){0.32}}
%
%\put(1.20,0.85){$c_{n-1}$}
%\put(2.20,0.85){$c_{n-2}$}
%%\put(3.20,0.85){$c_{n-1}$}
%\put(4.20,0.85){$c_1$}
%\put(5.20,0.85){$c_0$}
%
%\put(1.55,0.85){\vector(1,0){0.55}}
%\put(2.55,0.85){\vector(1,0){0.55}}
%\put(3.55,0.85){\vector(1,0){0.55}}
%\put(4.55,0.85){\vector(1,0){0.55}}
%\put(5.35,0.85){\vector(1,0){0.20}}
%\put(5.75,0.85){\line(1,0){0.25}}
%\put(5.58,0.82){$+$}
%\put(6.00,0.85){\line(0,-1){0.50}}
%\end{picture}

\setlength{\unitlength}{1.0in}
\begin{picture}(6.5,1.0)
%\put(0.0,0.0){\framebox(6.5,1.0)}
\put(0.5,0.25){\framebox(0.5,0.2){$v_{n-1}$}}
\put(1.5,0.25){\framebox(0.5,0.2){$v_{n-2}$}}
\put(2.5,0.25){\framebox(0.5,0.2){$\ldots$}}
\put(3.5,0.25){\framebox(0.5,0.2){$v_1$}}
\put(4.5,0.25){\framebox(0.5,0.2){$v_0$}}

\put(0.5,0.35){\vector(-1,0){0.5}}
\put(1.5,0.35){\vector(-1,0){0.3}}
\put(2.5,0.35){\vector(-1,0){0.3}}
\put(3.5,0.35){\vector(-1,0){0.3}}
\put(4.5,0.35){\vector(-1,0){0.3}}

\put(0.25,0.35){\vector(0,1){0.50}}
\put(1.10,0.85){\vector(0,-1){0.40}}
\put(2.10,0.85){\vector(0,-1){0.40}}
\put(3.10,0.85){\vector(0,-1){0.40}}
\put(4.10,0.85){\vector(0,-1){0.40}}
\put(5.10,0.85){\vector(0,-1){0.40}}

\put(1.04,0.31){$+$}
\put(2.04,0.31){$+$}
\put(3.04,0.31){$+$}
\put(4.04,0.31){$+$}
\put(5.04,0.31){$+$}

\put(1.24,0.60){$c_{n-1}$}
\put(2.24,0.60){$c_{n-2}$}
\put(4.24,0.60){$c_1$}
\put(5.24,0.60){$c_0$}

\put(0.25,0.85){\vector(1,0){4.85}}
\end{picture}

%Fibo config:
%Now, the linear feedback function has coefficients in $\F_q$, so we can write
%\begin{eqnarray*}
%	v_{n-1} &:=& v_{n-2} \\
%	v_{n-2} &:=& v_{n-3} \\
%	&\vdots& \\
%	v_1 &:=& v_0 \\
%	v_0 &:=& c_{n-1}v_{n-1} + \ldots + c_0 v_0
%\end{eqnarray*}
%Then we can write
%$$
%	T = \begin{pmatrix}
%	-c_{n-1} & -c_{n-2} & \cdots &  -c_1 & -c_0 \\
%	1        & 0       &        &      0  &    0 \\
%	0        & 1       & \ddots &  0    & 0    \\
%	\vdots   & &       &        &      \\
%	0        & 0       &        &      1  &    0 \\
%	\end{pmatrix}
%$$
%such that the LFSR transition may be written as
%$$ v := T(v) $$

The linear feedback function has coefficients in $\F_q$, so we can write
\begin{eqnarray*}
	v_0 &:=& c_0 v_{n-1} \\
	v_1 &:=& v_0 + c_1 v_{n-1} \\
	&\vdots& \\
	v_{n-2} &:=& v_{n-3} + c_{n-2} v_{n-1} \\
	v_{n-1} &:=& v_{n-2} + c_{n-1} v_{n-1}
\end{eqnarray*}
Then we have
$$
	\begin{pmatrix}
	v_0 \\
	v_1 \\
	\vdots \\
	v_{n-2} \\
	v_{n-1}
	\end{pmatrix}
	:=
	\begin{pmatrix}
	0        & 0       &        &      0  & c_0 \\
	1        & 0       &        &      0  & c_1 \\
	         & \ddots  &        &         & \vdots\\
	0        & 0       &        &      0  & c_{n-2} \\
	0        & 0       &        &      1  & c_{n-1} \\
	\end{pmatrix}
	\begin{pmatrix}
	v_0 \\
	v_1 \\
	\vdots \\
	v_{n-2} \\
	v_{n-1}
	\end{pmatrix}
$$
where
$$
	T =
	\begin{pmatrix}
	0        & 0       &        &      0  & c_0 \\
	1        & 0       &        &      0  & c_1 \\
	         & \ddots  &        &         & \vdots\\
	0        & 0       &        &      0  & c_{n-2} \\
	0        & 0       &        &      1  & c_{n-1} \\
	\end{pmatrix}
$$
such that the LFSR transition may be written as
$$ v := T(v) $$

Now, we might immediately ask, what is the characteristic polynomial of this
linear transformation?  Since the matrix is so sparse, it's easy to write it
out:  we have
$$ C(T) = \lambda - c_{n-1}\lambda^{n-1} - \ldots - c_1 \lambda - c_0 $$
It turns out that the behavior of the LFSR depends on properties of this
polynomial.  Thus, consideration of the physical problem (circuit diagram and
all) reduces to a strictly algebraic problem.

Now, there are $q^{n^2}$ possible $n\times n$ matrices over $\F_q$, but only
$q^n$ possible degree-$n$ characteristic polynomials over $\F_q$.  We can
further lump together characteristic polynomials into a few types, which I
think of as ``the good, the bad and the ugly'', in terms of their suitability
for applications.

%% ----------------------------------------------------------------
\section{Singular transformations}

In my examples we're considering $q=2$, so the coefficients are either 0 or 1:
either a connection, or a disconnection.  Physically, it is quite clear that if
the rightmost cell is disconnected, then the first time step will clear the
rightmost cell and nothing else will ever fill it:

[picture goes here]

From looking at the matrix, it's quite clear that if the rightmost cell is
disconnected, i.e. $c_0 = 0$, then the matrix is singular:  the topmost row is
all zeroes.  From looking at the characteristic polynomial, it is also clear
that if the rightmost cell is disconnected, the system has a zero eigenvalue.

Thus if $c_0 = 0$, the step transformation is singular, and contracts from the
initial $n$-dimensional state space to a smaller-dimensional state space.  This
means the transition graph will have hair:

[picture goes here]

%% ----------------------------------------------------------------
\section{Non-singular transformations}

From now on let's suppose the rightmost cell is connected:  that's one design
decision that's taken care of.  It remains to decide which additional cells to
connect.

From looking at the matrix, we can see that if the rightmost cell is connected,
i.e. $c_0 \ne 0$, then the matrix is non-singular:  you can column-reduce
easily to obtain the identity matrix.  Also, if the rightmost cell is
connected, then the system does not have a zero eigenvalue.  Thus the step
transformation is invertible.

Now, the map that sends $T^i$ to $T^{i+1}$ is a function from a finite set to
itself.  Therefore at some smallest exponent $l$ there must be a repetition
with a previous exponent $k$.  Thus $T^k = T^l$, i.e. $T^{k-l} = I$, since $T$
is invertible, with no smaller power being the identity.  Therefore we have a
\bfidx{cyclic subgroup} of the group of invertible $n \times n$ matrices on
$\F_q$, with order $k-l$.  Now, powers of $T$ act on the set $S$ of all
possible LFSR states.  From the basic theory of group actions, this means that
the powers of $T$ \bfidx{permute} the elements of $S$.  We know that
permutations have \bfidx{cycle decompositions}.  This means the transition
graph will have no hair and no tails, consisting instead only of loops.

% xxx faithful rep?

The remaining difference between bad and good LFSRs is in the number and size
of the loops, which will be revealed by further analysis of the characteristic
polynomial.

\bigskip

xxx Plan of attack:  discuss period (equals order of $T$ in
$\mathrm{GL}(n, \F_q)$), number of loops, and sizes of each loop in terms of the
structure of the characteristic polynomial of $T$.  Items:
\begin{itemize}
\item[(1)] Reducible with duplicates.
\item[(2)] Reducible without duplicates.
\item[(3)] Irreducible but imprimitive.
\item[(4)] Irreducible and primitive.
\end{itemize}

Questions/ideas:
\begin{itemize}
\item Degree of splitting field of $C(T)$ is the LCM of the degrees of
	the factors of $C(T)$ over $\F_q$.
\item $T$ is diagonalizable iff $C(T)$ splits (over the extension field
	of choice) and the multiplicities of the $\lambda_i$'s is equal to
	the dimensions of the kernels of the $(T-\lambda_iI)$'s.
\item In the diagonalizable case, any state is $$\vec{v} = \sum
	a_i \vec{v}_i$$ where the $\vec{v}_i$'s are ``complex'' (in the
	sense that they do not lie in $\F_q^n$).  Then
	$$
		T^k \vec v = \sum a_i T^k \vec{v}_i
		= \sum a_i \lambda_i^k \vec{v}_i
		= \sum a_i \vec{v}_i
	$$
	where $\lambda_i$ is a $k$th root of unity.  Relate order of $T$ to the
	order of the $\lambda_i$'s in the multiplicative group of the chosen
	extension field.
\item Show that in case (3) above, all loops are of the same size,
	equal to the order of the $\lambda_i$'s in $\F_{q^m}^\times$.  (It is easy
	to show that those orders are the same.)
\item Show that in case (4) above, there is a loop of order $q^n-1$.  This is
	the order of the $\lambda_i$'s in $\F_{q^m}^\times$.
\end{itemize}

%% ----------------------------------------------------------------
\section{Reducible LFSRs}

After the singular LFSRs, the next-best are those whose characteristic
polynomial is reducible.

%% ----------------------------------------------------------------
\section{Irreducible LFSRs}

Now suppose the characteristic polynomial is irreducible.

%% ----------------------------------------------------------------
\section{Primitive LFSRs}

The ideal LFSR is an irreducible one for which the eigenvalues have maximal
order in the multiplicative group.  Such polynomials are called
\bfidx{primitive} (in the sense of section xxx).

xxx Obtain primitives (feasible for small degree) by computing
		$q^n-1$'st cyclotomic polynomial, then factoring over $\F_q$.
Result is all primitives of degree $n$ over $\F_q$.

\begin{verbatim}
	gp: lift(lift(factorff(polcyclo(15), 2, u+1)))
	gp: lift(lift(factorff(polcyclo(15), 2, u^2+u+1)))
\end{verbatim}

%% ----------------------------------------------------------------
\section{Misc. note}

xxx work through some examples for good, bad and ugly.

xxx Draw Fibo but note u-RER

xxx Perhaps note recurring sequences (fibo)

xxx Talk about recurring sequences; u-RER also.

xxx Prove equiv of Fibo and u-RER; internal states differ but 1-bit output
is the same (with time delay)

%xxx coeffs in F2 are either connects or disconnects.  Design question is
%which connections to make.



%xor and and

%%% ================================================================
%\chapter{LFSRs and linear transformations}

%Linear feedback shift registers are perhaps the single most important
%application of finite fields.  In this chapter we'll see what they are, look at
%several different configurations, and discover that they are all special cases
%of a general situation.
%
%The standard reference for LFSRs is Golomb \cite{bib:golomb}.  Also see Lidl
%and Niederreiter \cite{bib:ln}, and in Schneier \cite{bib:sch}.  At the same
%time, this chapter serves to clarify some concepts as presented in
%Schneier \cite{bib:sch}.

%%% ----------------------------------------------------------------
%\section{Homogeneous linear recurrence relations}
%
%Anyone who has taken discrete mathematics is familiar with \emph{recurrence
%relations}.  Often, the first example presented is the \emph{Fibonacci
%sequence}, given by
%
%\begin{eqnarray*}
%	s_0 &=& 0 \\
%	s_1 &=& 1 \\
%	s_{k+2} &=& s_{k+1} + s_k,\; k=0,1,2,\ldots
%\end{eqnarray*}
%
%By applying these rules we get the sequence 0, 1, 1, 2, 3, 5, 8, etc.
%
%The idea is to define a sequence (of integers, reals, finite-field elements,
%etc.) in terms of previous elements.  Terminology:
%
%\begin{itemize}
%
%\item If the value of an element is a function of the $n$ values before it
%($n=2$ for the Fibonacci sequence), then we say we have an \bfidx{nth-order
%recurrence relation}.
%
%\item This function may be called the \bfidx{recurrence rule}, since it's the
%rule which tells us how to produce the next element of the sequence.
%
%\item For an $n$th-order recurrence relation, to avoid indexing into negative
%$k$ values where the sequence is undefined, we require $n$ \bfidx{initial
%conditions}, $s_0$ through $s_{n-1}$  --- in this example, $s_0=0$ and $s_1=1$.
%It's important to note that the initial conditions are part of what defines the
%sequence --- if you use the Fibonacci sequence's recurrence rule but use
%different initial conditions, that's not the Fibonnaci sequence.
%
%\item If the recurrence rule is a linear function (as is the case for the
%Fibonacci sequence; $s_k = s_{k-1}^2$ would be a non-linear 1st-order
%recurrence relation on the integers\footnote{Although it would be linear over
%$\F_2$, since $a^2=a$ for all $a$ in $\F_2$.}), then we say we have a
%\bfidx{linear recurrence relation}.
%
%\item If there is a constant term in the recurrence rule, e.g.  $s_k = s_{k-2}
%+ s_{k-1} + 3$, then we say we have an \bfidx{inhomogeneous linear recurrence
%relation}; otherwise we say we have a \bfidx{homogeneous linear recurrence
%relation}.
%
%\end{itemize}
%
%In this paper I'll confine myself to homogeneous linear recurrence relations.
%In general, we have
%\begin{eqnarray*}
%	s_{k+n} &=& c_{n-1} s_{k+n-1} + c_{n-2} s_{k+n-2} + \ldots
%		+ c_1 s_{k+1} + c_0 s_k \\
%	&=& \sum_{i=0}^{n-1} c_i s_{k+i}
%\end{eqnarray*}
%
%%% ----------------------------------------------------------------
%\section{Matrices for homogeneous linear recurrence relations}
%
%We can define recurrence relations over any ring, group, etc. --- any set of
%elements with at least one mathematical operation.  Here we'll look
%specifically at recurrence relations over the field $\F_q = \Fpn$.
%
%Here is an example, a 4th-order homogeneous linear recurrence relation, taken
%over $\F_2$: $$ s_{k+4} = s_{k-3} + s_{k-4} $$
%
%Now, thinking ahead to where I'm going, I can write a \bfidx{state vector} $$
%\mathbf{s}_k = (s_{k+3}, s_{k+2}, s_{k+1}, s_k)^t$$ with the obvious
%generalization to $n$th-order recurrence relations.  The $k$th state vector,
%$\mathbf{s}_k$, consists simply of the $n$ values needed to produce the next
%element of the sequence.  Given that, I can write the following matrix equation
%to get the next state vector:
%
%\begin{eqnarray*}
%	\left(\begin{array}{r}
%		s_{k+4} \\
%		s_{k+3} \\
%		s_{k+2} \\ 
%		s_{k+1} \\
%	\end{array}\right)
%	=
%	\left(\begin{array}{rrrr}
%		0 & 0 & 1 & 1 \\
%		1 & 0 & 0 & 0 \\ 
%		0 & 1 & 0 & 0 \\
%		0 & 0 & 1 & 0 \\
%	\end{array}\right)
%	\cdot
%	\left(\begin{array}{r}
%		s_{k+3} \\
%		s_{k+2} \\
%		s_{k+1} \\ 
%		s_{k} \\
%	\end{array}\right)
%\end{eqnarray*}
%
%If you write out the matrix multiplication, all this says is that $$ s_{k+4} =
%s_{k+1} + s_k $$ which is true, along with $$ s_{k+3} = s_{k+3},\; s_{k+2} =
%s_{k+2},\; s_{k+1} = s_{k+1} $$ which are undeniable.  Writing the above matrix
%as $T$, I have
%$$ \mathbf{s}_{k+1} = T \mathbf{s}_k $$
%
%As you can easily see, given an $n$th-order linear recurrence relation $$
%s_{k+n} = c_{n-1} s_{k+n-1} + c_{n-2} s_{k+n-2} + \ldots + c_1 s_{k+1} + c_0
%s_k $$ the $T$ matrix will be
%\begin{eqnarray*}
%	\left(\begin{array}{rrrrr}
%	c_{n-1} & c_{n-2} & \cdots & c_1 &  c_0 \\
%	1       & 0       &        & 0      & 0    \\
%	0       & 1       &        & 0      & 0    \\
%	\vdots  &         & \ddots &        &      \\
%	0       & 0       &        & 1      & 0    \\
%	\end{array}\right)
%\end{eqnarray*}
%
%Why would I write such a matrix equation?  Because we now have a \bfidx{linear
%transformation} from the \bfidx{n-dimensional vector space} $(\F_q)^n$ to
%itself.  And quite a bit is known about linear transformations.
%
%%% ----------------------------------------------------------------
%\section{Registers}
%
%When you're standing on the ground watching a train go by, of course the ground
%is motionless while the train whizzes past you.  But if you're on the train, it
%seems to stay still while the ground rushes past in the other direction.
%Looking at a recurrence relation is like watching a train:  we stand on the
%integers while the recurrence relation chugs out one sequence element after
%another.  Looking at the state vectors is like being on the train:  we keep the
%$n$ previous values next to us, and they burble and change while the subscripts
%rush along underneath.
%
%In electronic circuits, which is where this all started (see also
%\cite{bib:alf}), the cars in the train are called a \bfidx{register}.  Let's
%take another look at that matrix multiplication, which transforms a state
%vector at one time tick into the state vector at the next time tick.  Let $:=$
%stand for \bfidx{assignment}.  Letting the train stand still, I'll let $v_0$
%through $v_{n-1}$ stand for the values in the register at a given time step.
%
%We have
%\begin{eqnarray*}
%	v_3 &:=& v_1 + v_0 \\
%	v_2 &:=& v_3 \\
%	v_1 &:=& v_2 \\
%	v_0 &:=& v_1
%\end{eqnarray*}
%or (please pardon the corny ASCII graphics):
%\begin{verbatim}
%   o-------------o-(+)--o
%   |             |      |
%   |             ^      ^
%   v             |      |
%o------o------o--|---o--|---o
%|  v3 --> v2 --> v1 --> v0  | ---> output
%o------o------o------o------o
%\end{verbatim}
%
%The term \emph{linear feedback shift register} is very clear here: bits in the
%register are shifted one position to the right at each time step; the vacancy
%at the left is filled by values fed back into the register, using a linear
%function.
%
%The entire contents of the register (the state vector) is the \bfidx{internal
%state}, namely, all the $n$ history values needed for the recurrence relation,
%but only the shifted-out value is the \bfidx{output}.  Mathematically, the
%state is in $(\F_q)^n$ but the output is in $\F_q$.  In particular, for this
%example where $q=2$, we get only one output bit per time tick.  We'll discuss
%below what to do about this.
%
%%% ----------------------------------------------------------------
%\section{Periodicity of recurrence relations over $\F_q$}
%
%Suppose you have a function $f$ from a finite set $S$ to itself, then
%\bfidx{iterate} that function.  E.g. given $s$ in $S$, compute $f(s)$, then
%$f(f(s))$, etc.  Since there are only finitely many elements in the set, you
%can't keep getting different iterates\footnote{Computer scientists call this
%the \emph{pigeonhole principle}.}, so some $j$th iterate will be equal to some
%$i$th iterate.  At that point, the function will necessarily start to repeat.
%
%Now, the first few values don't ever have to appear again.  For example, square
%an odd integer mod 10.  Say you start with 3; its square mod 10 is 9, whose
%square is 1, and all subsequent squares are 1.  I.e. you get the sequence $3,
%9, 1, 1, 1, \ldots$.  The 3 and the 9 don't ever reappear, but the sequence is
%\bfidx{ultimately periodic} with period 1.  By analogy with the shape of the
%Greek letter $\rho$, we sometimes call the start-up phase (e.g. $3, 9$) the
%\bfidx{tail} and the periodic phase (e.g.  $1, 1, 1, \dots$) the \bfidx{loop}
%or the \bfidx{cycle}.
%
%Now, our linear transformations (the non-linear ones too, for that matter) are
%functions from the finite set $(\F_q)^n$ to itself, so \emph{LFSRs always
%repeat}.  In engineering practice, one typically wants:
%
%\begin{itemize}
%\item The longest possible period, or \bfidx{maximal period}, for a given
%	amount of history (i.e. $n$).
%\item The maximal number of states reachable from any other, i.e.
%	we should be able to run through as many of the possible states
%	as we can;
%\item The minimal number of \bfidx{lock-up} states, i.e. state vectors that
%	map to themselves.
%\end{itemize}
%
%We'll see below how easy these goals are to achieve, using some of the
%finite-field techniques from earlier in this paper.  (To avoid being coy, I'll
%say that the zero vector will be a lock-up state, but we'll always, for any $q$
%and $n$, be able to construct an LFSR of period $q^n-1$ which cycles through
%all of the $q^n-1$ non-zero states, regardless of initial state.) But first, I
%want to look at a slightly different LFSR.
%
%%% ----------------------------------------------------------------
%\section{Powers of $u$ revisited}
%
%Let's take another look at the RER method for multiplying by $u$, as described
%in section \ref{sec:RER}.  Suppose for the sake of example that we're working
%in $\F_{2^4}$, with an arbitrary finite-field element which is
%$$a_3u^3 + a_2u^2 + a_1u + a_0$$
%and suppose the polynomial $r(x)$ which we use to define our finite-field
%arithmetic is
%$$ x^4 + x + 1 $$
%When we multiply by $u$, we get
%$$a_3u^4 + a_2u^3 + a_1u^2 + a_0u$$
%But we want to reduce mod $r$.  Since $u^4 = -u - 1$, we get
%$$a_2u^3 + a_1u^2 + (a_0-a_3)u - a_3$$
%
%Graphically,
%
%\begin{tabular}{|r|r|r|r|r|l|}
%\hline & $a_3$ & $a_2$ & $a_1$ & $a_0$ & Input\\
%\hline $a_3$ & $a_2$ & $a_1$ & $a_0$ & $0$ & Multiplied by $u$ \\
%\hline  & $a_2$ & $a_1$ & $a_0-a_3$ & $-a_3$ & Reduced mod $r$, using RER \\
%\hline
%\end{tabular}
%
%That is, letting $b$'s represent the coefficients of $u \cdot a$,
%\begin{eqnarray*}
%	b_3 &=& a_2 \\
%	b_2 &=& a_1 \\
%	b_1 &=& a_0-a_3 \\
%	b_0 &=& -a_3
%\end{eqnarray*}
%
%Now, this can be represented by a matrix (as you might expect, since
%multiplication by $u$ is certainly a linear transformation on $\Fpn$).
%Recalling that plus is the same as minus when $p=2$, we have
%\begin{eqnarray*}
%	\left(\begin{array}{r}
%		b_3 \\
%		b_2 \\
%		b_1 \\ 
%		b_0 \\
%	\end{array}\right)
%	=
%	\left(\begin{array}{rrrr}
%		0 & 1 & 0 & 0 \\
%		0 & 0 & 1 & 0 \\ 
%		1 & 0 & 0 & 1 \\
%		1 & 0 & 0 & 0 \\
%	\end{array}\right)
%	\cdot
%	\left(\begin{array}{r}
%		a_3 \\
%		a_2 \\
%		a_1 \\ 
%		a_0 \\
%	\end{array}\right)
%\end{eqnarray*}
%
%In the general case, it's easy to see that if
%$$ r(x) = x^n + r_{n-1}x^{n-1} + r_{n-2}x^{n-2} + \ldots + r_1 x + r_0 $$
%then the multiply-by-$u$ matrix looks like
%\begin{eqnarray*}
%	\left(\begin{array}{llllll}
%	-r_{n-1} & 1 &      0 & & 0  & 0 \\
%	-r_{n-2} & 0 &      1 & & 0  & 0 \\
%	\vdots   & & \ddots & & & \\
%	-r_1     & 0 &      0 & & 0  & 1 \\
%	-r_0     & 0 &      0 & & 0  & 0 \\
%	\end{array}\right)
%\end{eqnarray*}
%
%We could implement an LFSR as follows:  Again let $v$'s stand for register
%values, and let
%\begin{eqnarray*}
%	v_3 &:=& v_2 \\
%	v_2 &:=& v_1 \\
%	v_1 &:=& v_0-v_3 \\
%	v_0 &:=& -v_3
%\end{eqnarray*}
%
%%\begin{verbatim}
%%   o-------------o-(+)--o
%%   |             |      |
%%   |             ^      ^
%%   v             |      |
%%o------o------o--|---o--|---o
%%|  v3 --> v2 --> v1 --> v0  | ---> output
%%o------o------o------o------o
%%\end{verbatim}
%
%It would look like this:
%\begin{verbatim}
%   o-------------o------o
%   |             |      |
%   ^             v      v
%   |             |      |
%o--|---o------o-(+)--o-(+)--o
%|  v3 <-- v2 <-- v1 <-- v0  |
%o------o------o------o------o
%\end{verbatim}
%That is, it looks just like the previous LFSR, \emph{except with the
%arrows reversed}.
%
%%% ----------------------------------------------------------------
%\section{LFSR configurations}
%
%Now we have two ways to form LFSRs.  In the first case, we started with a
%recurrence relation over $\F_q$, then created vectors over $(\F_q)^n$.  In the
%second case, we looked at arithmetic in $\F_{q^n}$, which we can view as a
%vector space $(\F_q)^n$ over $\F_q$.
%
%The first LFSR we looked at arose naturally from recurrence relations such as
%the Fibonacci sequence.  This LFSR is called a \bfidx{Fibonacci
%configuration}.  The second LFSR we looked at arose naturally from
%multiplication in a finite, or Galois, field.  This LFSR is called a
%\bfidx{Galois configuration}.  (To be quite picky, Galois-configuration LFSRs
%are typically presented as a left-to-right mirror image of what I've shown
%here, so I should say I'm using a \emph{reflected} Galois configuration.)
%
%% Ch polys of all of them = x^4 + x + 1, as can easily be computed.
%% "compan".
%
%%     recall u-RER
%%     mx thereof
%%     chpol thereof
%
%
%% xxx need to switch to sk4 + sk1 + sk0 = 0.  Negate all the ci's.
%
%xxx different functions, different internal state -- but same *output*?!?
%
%%% ----------------------------------------------------------------
%\section{Companion matrices}
%%     many-to-one mapping mx -> chpol; one-to-many chpol -> mx.
%%     quote 1344.
%
%xxx note that LFSRs can be defined over Fq, where (practically) q is a power of
%2.  mention TSRs just for fun ... ref to Tsaban and Vishne ``very readable
%paper''.
%
%xxx no crappy line breaks in ASCII art!
%
%%% ----------------------------------------------------------------
%%\section{The good, the bad and the ugly:  primitives and the rest}
%
%% The good, the bad and the ugly:
%% Hint at count of prims, irreds, c0 != 0, c0 = 0, multiplicity of
%%   zero eigenvalue.  Inv'ble iff c0 != 0.  <T> cyc sgr of GL(?,?) is
%%   acting on (Fp)^n.  orbits / trans gp action.  u-prim (old def)
%%   vs. T-prim (new def) via chpol.
%
%%% ----------------------------------------------------------------
%%   LTs
%%     More about chpols, factorization, etc. as I figure that out.
%
%% xxx max period; why want prims.
%
%% xxx two definitions of prim.
%
%%% ================================================================
%
%%\begin{verbatim}
%%    o------o----------------------o
%%    |      |                      |
%%    v      v                      ^
%%+------+------+------+------+     |
%%|  v3 --> v2 --> v1 --> v0  | -->-o--> output
%%+------+------+------+------+
%%\end{verbatim}
%
%
%
%% wider: (1) m indep, but not maximal pd; (2) q=2^m; (3) TSRs
%
%% immed xref to golomb
%
%% lfsrs here only with ICs, internal state & output -- no external input.
%% note CRCs; xref to CRC-explained.
%
%%% ----------------------------------------------------------------
%% eigensolver: lcm over degs of frs.
%% note about lcm/splitter in ffarith part
%
%% units in R^x
%% orders in R^x
%% cyclicity??
