Introduction to Cryptography with Coding Theory, 3rd Edition

D.3 Computations for Chapter 5

LFSR

Consider the recurrence relation $x_{n+4}\equiv x_n+x_{n+1}+x_{n+3}$ mod 2, with initial values $1\text{,}0\text{,}0\text{,}0$. We need to use 0s and 1s, but we need to tell Sage that they are numbers mod 2. One way is to define “o” (that’s a lower-case “oh”) and “l” (that’s an “ell”) to be 0 and 1 mod 2:

F=GF(2) 
o=F(0); l=F(1)

We also could use F(0) every time we want to enter a 0, but the present method saves some typing. Now we specify the coefficients and initial values of the recurrence relation, along with how many terms we want. In the following, we ask for 20 terms:

s=lfsr_sequence([l,l,o,l],[l,o,o,o],20);s

This evaluates to

[1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0]

Suppose we are given these terms of a sequence ...