---
title: "Linear Feedback Shift Registers"
canonical: "https://docs.magma-maths.org/CodingTheory/PseudoRandomBitSequences/lfsr.html"
source: "https://docs.magma-maths.org/CodingTheory/PseudoRandomBitSequences/lfsr.md"
part: "Coding Theory"
chapter: "Pseudo-Random Bit Sequences"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "../../index.md"}
  - {"title": "Coding Theory", "source": "../index-coding-theory.md"}
  - {"title": "Pseudo-Random Bit Sequences", "source": "index-pseudo-random-bit-sequences.md"}
prev: {"title": "Introduction", "source": "introduction.md"}
next: {"title": "Correlation Functions", "source": "correlation.md"}
intrinsics:
  - {"name": "LFSRSequence", "signature": "LFSRSequence(C, S, t): RngUPolElt, SeqEnum, RngIntElt -> SeqEnum"}
  - {"name": "LFSRStep", "signature": "LFSRStep(C, S): RngUPolElt, SeqEnum -> SeqEnum"}
  - {"name": "BerlekampMassey", "signature": "BerlekampMassey(S): SeqEnum -> RngUPolElt, RngIntElt"}
  - {"name": "ConnectionPolynomial", "signature": "ConnectionPolynomial(S): SeqEnum -> RngUPolElt, RngIntElt"}
  - {"name": "CharacteristicPolynomial", "signature": "CharacteristicPolynomial(S): SeqEnum -> RngUPolElt, RngIntElt"}
  - {"name": "ShrinkingGenerator", "signature": "ShrinkingGenerator(C1, S1, C2, S2, t): RngUPolElt, SeqEnum, RngUPolElt, SeqEnum, RngIntElt -> SeqEnum"}
examples:
  - "ex-ad3ed3"
---

# 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$.

<a id="function-lfsrsequence-rngupolelt-seqenum-rngintelt"></a>
## `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$.

<a id="function-lfsrstep-rngupolelt-seqenum"></a>
## `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$.

<a id="function-berlekampmassey-seqenum"></a>
## `BerlekampMassey(S): SeqEnum -> RngUPolElt, RngIntElt`

<a id="function-connectionpolynomial-seqenum"></a>
## `ConnectionPolynomial(S): SeqEnum -> RngUPolElt, RngIntElt`

<a id="function-characteristicpolynomial-seqenum"></a>
## `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.

<a id="example-ex-ad3ed3"></a>
## `Example: Connection Polynomial via Berlekamp-Massey (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 ]
```

<a id="function-shrinkinggenerator-rngupolelt-seqenum-rngupolelt-seqenum-rngintelt"></a>
## `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.