Compute the first 50 terms of the recurrence

The initial values are $0\text{,}1\text{,}0\text{,}0\text{,}0$.

SOLUTION

The vector of coefficients is $\{1\text{,}0\text{,}1\text{,}0\text{,}0\}$ and the initial values are given by the vector $\{0\text{,}1\text{,}0\text{,}0\text{,}0\}$. Type

In[1]:= lfsr[{1, 0, 1, 0, 0}, {0, 1, 0, 0, 0}, 50]

Out[1]= {0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1}

Suppose the first 20 terms of an LFSR sequence are 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1. Find a recurrence that generates this sequence.

SOLUTION

First, we find the length of the recurrence. The command lfsrlength[v, n] calculates the determinants mod 2 of the first $n$ matrices that appear in the procedure in Section 5.2:

In[2]:=

lfsrlength[{1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1}, 10]
     {1, 1}
     {2, 1}
     {3, 0}
     {4, 1}
     {5, 0}
     {6, 1}
     {7, 0}
     {8, 0}
     {9, 0}
     {10, 0}

The last nonzero determinant is the sixth one, so we guess that the recurrence has length 6. To find the coefficients:

In[3]:= lfsrsolve[{1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1}, 6]

Out[3]= {1, 0, 1, 1, 1, 0}

This gives the recurrence as

The ciphertext 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0 was produced by adding the output of a LFSR onto the plaintext mod 2 (i.e., XOR the plaintext with the LFSR output). Suppose you know that the plaintext starts 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0. Find the rest of the plaintext.

SOLUTION

XOR the ciphertext with the known part of the plaintext to obtain the beginning of the LFSR output:

In[4]:= Mod[{1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0} + {0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1}, 2]

Out[4]= {1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1}

This is the beginning of the LFSR output. Now let’s find the length of the recurrence:

In[5]:= lfsrlength[%, 8]

{1, 1}
{2, 0}
{3, 1}
{4, 0}
{5, 1}
{6, 0}
{7, 0}
{8, 0}

We guess the length is 5. To find the coefficients of the recurrence:

In[6]:= lfsrsolve[%%, 5]

Out[6]= {1, 1, 0, 0, 1}

Now we can generate the full output of the LFSR using the coefficients we just found plus the first five terms of the LFSR output:

In[7]:= lfsr[{1, 1, 0, 0, 1}, {1, 0, 0, 1, 0}, 40]

Out[7]={1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0}

When we XOR the LFSR output with the ciphertext, we get back the plaintext:

In[8]:= Mod[% + {0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0}, 2]

Out[8]= {1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0}

This is the plaintext.