Computer Security and Cryptography

8.8 MATRIX REPRESENTATION OF THE LFSR

In addition to the Berlekamp–Massey algorithm, there is another approach that will be useful to calculate the minimal polynomial p(z) = c_N + c_N−1z + ··· + c₁z^{N − n} + c₀z^N of an LFSR output sequence s₀(0), s₀(1), … when the length N of the LFSR is known. The forward recursion provides a relationship between consecutive N-blocks of LFSR output values:

        Proposition 8.8: If the LFSR has linear equivalence N, then

8.8a	The row of the N × N matrix S(t, t + N − 1) are linearly independent, and
8.8b	The 2N consecutive outputs s0(t), s0(t + 1), …, s0(t + 2n − 1) determine the characteristic polynomial of the LFSR.

        Proof of (8.8a): If on the contrary, the rows of S are linearly dependent, there exists a vector d ≠ (0)_N such that

This implies

Assuming without loss of generality that d_N−1 = 1, we have

which contradicts the assumed linear equivalence.

        Proof of (8.8b): Gaussian elimination and its application in cribbing Hill ...