# Linear Feedback Shift Registers

For a linear feedback shift register (LFSR) of length $L$, initial state $s_0, \ldots, s_{L-1} \in {\bf F}_{q}$, and connection polynomial $C(D) = 1 + c_1 D + c_2 D^2 + \ldots + c_L D^L$ (also over ${\bf F}_{q}$), the $j$’th element of the sequence is computed as $s_j = - \sum_{i=1}^L c_i s_{j-i}$ for $j \geq L$.

## `LFSRSequence(C, S, t): RngUPolElt, SeqEnum, RngIntElt -> SeqEnum`

Computes the first $t$ sequence elements of the LFSR with connection polynomial $C$ and initial state the sequence $S$ (thus, the length of the LFSR is assumed to be the length of $S$). $C$ must be at least degree 1, its coefficients must come from the same finite field as the universe of $S$, and its constant coefficient must be $1$. Also, the sequence $S$ must have at least as many terms as the degree of $C$.

## `LFSRStep(C, S): RngUPolElt, SeqEnum -> SeqEnum`

Computes the next state of the LFSR having connection polynomial $C$ and current state the sequence $S$ (thus, the length of the LFSR is assumed to be the length of $S$). $C$ must be at least degree 1, its coefficients must come from the same finite field as the universe of $S$, and its constant coefficient must be $1$. Also, the sequence $S$ must have at least as many terms as the degree of $C$.

## `BerlekampMassey(S): SeqEnum -> RngUPolElt, RngIntElt`

## `ConnectionPolynomial(S): SeqEnum -> RngUPolElt, RngIntElt`

## `CharacteristicPolynomial(S): SeqEnum -> RngUPolElt, RngIntElt`

Given a sequence S of elements from ${\bf F}_{q}$, return the connection polynomial $C(D)$ and the length $L$ of a LFSR that generates the sequence S.

Note that it is possible that the `BerlekampMassey` will return a singular LFSR (i.e. the degree of $C(D)$ is less than $L$), and therefore one must be sure to use the first $L$ elements of $S$ to regenerate the sequence.

## `Example: Reconstruct Sequence (ex-ad3ed3)`

We first create a sequence and then use `BerlekampMassey` to get the connection polynomial and its length:

```magma
> S:= [GF(2)| 1,1,0,1,0,1,1,1,0,0,1,0];
> C<D>, L := BerlekampMassey(S);
> C;
D^3 + D^2 + 1
> L;
5

```

Now create a new sequence $T$ containing the first $L$ elements of $S$, and reconstruct the sequence from $C(D)$ and $T$.

```magma
> T := S[1..L];
> LFSRSequence(C, T, #S);
[ 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0 ]

```

## `ShrinkingGenerator(C1, S1, C2, S2, t): RngUPolElt, SeqEnum, RngUPolElt, SeqEnum, RngIntElt -> SeqEnum`

Outputs a sequence of $t$ bits from the shrinking generator having connection polynomials $C_1$ and $C_2$ and initial states sequences $S_1$ and $S_2$ (thus, the lengths of the LFSRs are assumed to be the lengths of $S_1$ and $S_2$). Bits are represented as elements from ${\bf F}_{2}$. Polynomial coefficients and sequence elements must be from ${\bf F}_{2}$. The degrees of the connection polynomials must be at least $1$ and their trailing coefficients must be $1$. The number of elements in the initial states must be at least as large as the degrees of the corresponding connection polynomials.