Linear Feedback Shift Registers

For a linear feedback shift register (LFSR) of length L, initial state s0, ..., sL - 1 ∈GF(q), and connection polynomial C(D) = 1 + c1 D + c2 D2 + ... + cL DL (also over GF(q)), the j'th element of the sequence is computed as sj = - ∑i=1L ci sj - i for j ≥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 GF(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 PseudoRandom_reconstruct-sequence (H168E1)

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
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 ]
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 C1 and C2 and initial states sequences S1 and S2 (thus, the lengths of the LFSRs are assumed to be the lengths of S1 and S2). Bits are represented as elements from GF(2). Polynomial coefficients and sequence elements must be from GF(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.
V2.28, 13 July 2023