Editing Linear-feedback shift register (section)

== Matrix forms ==
Binary LFSRs of both Fibonacci and Galois configurations can be expressed as linear functions using matrices in <math>\mathbb{F}_2</math> (see [[GF(2)]]).<ref>{{Cite book|title=Stream Ciphers|chapter=Linear Feedback Shift Registers|last=Klein|first=A.|year=2013|pages=17–18|publisher=Springer|location=London|doi=10.1007/978-1-4471-5079-4_2|isbn=978-1-4471-5079-4}}</ref> Using the [[companion matrix]] of the characteristic polynomial of the LFSR and denoting the seed as a column vector <math>(a_0, a_1, \dots, a_{n-1})^\mathrm{T}</math>, the state of the register in Fibonacci configuration after <math>k</math> steps is given by

:<math>\begin{pmatrix} a_{k} \\ a_{k+1} \\ a_{k+2} \\ \vdots \\ a_{k+n-1} \end{pmatrix} =
\begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & 0\\ 0 & 0 & \cdots & 0& 1\\ c_{0} & c_{1} & \cdots & \cdots & c_{n-1} \end{pmatrix}
\begin{pmatrix} a_{k-1} \\ a_{k} \\ a_{k+1} \\ \vdots \\ a_{k+n-2} \end{pmatrix} =
\begin{pmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & 0\\ 0 & 0 & \cdots & 0& 1\\ c_{0} & c_{1} & \cdots & \cdots & c_{n-1} \end{pmatrix}^k
\begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{n-1} \end{pmatrix}</math>

Matrix for the corresponding Galois form is :
:<math>
\begin{pmatrix} c_0 & 1 & 0 & \cdots & 0 \\ c_1 & 0 & 1 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & 0\\ c_{n-2} & 0 & \cdots & 0& 1\\ c_{n-1} & 0 & \cdots & \cdots & 0 \end{pmatrix}</math>
For a suitable initialisation, 
:<math>a'_i=\sum_{i=0}^ja_{i-j}c_{n-j},\ 0\leq i < n</math>
the top coefficient of the column vector :
:<math>
\begin{pmatrix} c_0 & 1 & 0 & \cdots & 0 \\ c_1 & 0 & 1 & \ddots & \vdots \\ \vdots & \vdots & \ddots & \ddots & 0\\ c_{n-2} & 0 & \cdots & 0& 1\\ c_{n-1} & 0 & \cdots & \cdots & 0 \end{pmatrix}^k
\begin{pmatrix} a'_0 \\ a'_1 \\ a'_2 \\ \vdots \\ a'_{n-1} \end{pmatrix}</math>
gives the term {{math|''a''<sub>''k''</sub>}} of the original sequence.

These forms generalize naturally to arbitrary fields.