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:

> 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

Run in calculatorCopy input

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

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

Run in calculatorCopy input

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.