
\section{bla}

We define a \emph{linear feedback shift register} (LFSR) over $\F_{q}$
by a \emph{generating polynomial} $f(x) = x^{n} + \sum_{i<n} f_{i}
x^{i}$ and $n$ values $z_{i}^{0} \in \F_{q}$, $0\leq i<n$.  The LFSR
has $n$ cells.  Cell $i$ contains the value $z_{i}^{t}$ at time $t$.
In every time step the cells are shifted downwards and the freed cell
obtains a combination of the old contents given by the polynomial:
\begin{align*}
  z_{i}^{t} &= z_{i+1}^{t-1} \quad\text{for $0\leq i \leq n-2$,}
  \\
  z_{n-1}^{t} &= \sum_{i<n} -f_{i} z_{i}^{t-1}.
\end{align*}
It is obvious that 
\begin{lemma}
  \label{res:tr-formula}
  For any linear sequence $z \in \F_{q}^{\N}$ there exists an element
  $\alpha \in E$
  such that
  $$
  z_{i} = ~Tr_{E|\F_{q}}(\alpha \xi^{i}).
  $$
\end{lemma}
We repeat its proof here, just to show that it cannot hold in the
situation that we are going to describe later.
\begin{proof}
  Let's due the induction step first and assume $z_{t+i} = ~Tr(\alpha
  \xi^{t+i})$ holds for $0\leq i<n$.  Then we also have
  \begin{align*}
    z_{t+n} &= \sum_{i<n} -f_{i} ~Tr(\alpha \xi^{t+i})
    \\
    &= ~Tr(\alpha \xi^{t} \sum_{i<n} -f_{i} \xi^{i} )
    \\
    &= ~Tr(\alpha \xi^{t+n}).
  \end{align*}
  The ...
\end{proof}

One consequence of \ref{res:tr-formula} is...

We obtain another description when consideríng the vector of cell
contents at each time $t$: $\underline{z}^{t} =
[z_{t+0},\dots,z_{t+n-1}]^{T}$.  Now the recursion becomes merely
multiplication with the transposed companion matrix $C_{f}^{T}$ of the
generator polynomial $f$:
\begin{align*}
  \underline{z}^{t} &=
  \underbrace{
    \begin{bmatrix}
    0&1&0&\dots&0\\
    \vdots&\ddots&\ddots&\ddots&\vdots\\
    \vdots&&\ddots&\ddots&0\\
    0&\dots&\vphantom{\ddots}&0&1\\
    -f_{0}&-f_{1}&\vphantom{\ddots}&\dots&-f_{n-1}
  \end{bmatrix}
  }_{=: C_{f}^{T}}
  \cdot \underline{z}^{t-1}.
\end{align*}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "thesistemplate"
%%% End: 
