Computer Security and Cryptography

8.6 LINEAR EQUIVALENCE

The output of an LFSR s₀(0), s₀(1), … may be generated by more than one characteristic polynomial and initial state.

Example 8.6

The LFSRs with characteristic polynomials and initial states

both generate the sequence s = (1, 1, 0, 1, 1, 0,…). Note that an LFSR to generate a given n-sequence of 0's and 1's σ = (σ(0), σ(1), …, σ(n−1)) always exists as σ could be used as the initial state of the n-stage LFSR with any coefficient vector

More relevant are the questions

Q1.	What is the minimum number of stages needed by an LFSR to generate σ?
Q2.	What is the minimal polynomial of σ, the characteristic polynomial of the minimal-length LFSR that generates σ?

The linear equivalence L(σ) of the n-sequence σ = (σ(0), σ(1), …, σ(n−1)) is the length of the shortest LFSR that generates σ.

The principal properties of linear equivalence are summarized in the next proposition.

        Proposition 8.7: [Beker and Piper, 1982, p. 200; Menezes et al., 1996, p. 198]¹ the n-sequence σ = (σ(0), σ(1), …, σ(n−1))

8.7a	If σ is of length n; then1
	(Note, in analogy with the convention for a summation or product with an empty index set, a 0-stage LFSR always outputs 0.)
8.7b	The linear equivalence of σ and v, possibly of different lengths, satisfies L(σ + v) ≤ L( ...