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

%% ================================================================
\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 \textbf{nth-order
recurrence relation}.

\item This function may be called the \textbf{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$ \textbf{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
\textbf{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 \textbf{inhomogeneous linear recurrence
relation}; otherwise we say we have a \textbf{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 \textbf{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 \textbf{linear
transformation} from the \textbf{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 \textbf{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 \textbf{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 \textbf{internal
state}, namely, all the $n$ history values needed for the recurrence relation,
but only the shifted-out value is the \textbf{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
\textbf{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
\textbf{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
\textbf{tail} and the periodic phase (e.g.  $1, 1, 1, \dots$) the \textbf{loop}
or the \textbf{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 \textbf{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 \textbf{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 \textbf{Fibonacci
configuration}.  The second LFSR we looked at arose naturally from
multiplication in a finite, or Galois, field.  This LFSR is called a
\textbf{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.
