Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 2 Solutions - Ex2.8

- 6 mins

Exercise 2.8

In this problem we will study LFSRs in somewhat more detail. LFSRs come in three flavors:

We will study examples in the following. Determine all sequences generated by

  1.  
  2.  
  3.  

Draw the corresponding LFSR for each of the three polynomials. Which of the polynomials is primitive, which is only irreducible, and which one is reducible? Note that the lengths of all sequences generated by each of the LFSRs should add up to .

Solution

I haven’t yet verified this solution independently. If you spot any mistakes, please leave a comment in the Disqus box at the bottom of the page.

1. This LFSR derived from can be represented as follows:

LFSR 1

Starting from , the LFSR will iterate through the following states:

The polynomial produces a single length sequence of internal states (containing all non-zero 4-bit binary numbers) before repeating and is therefore a primitive polynomial.

2. This LFSR derived from can be represented as follows:

LFSR 2

Starting from , and , the LFSR will iterate through the following states:

The polynomial produces three distinct sequences of internal states (together containing all non-zero 4-bit binary numbers) of varying lengths. It is therefore a reducible polynomial.

2. This LFSR derived from can be represented as follows:

LFSR 3

Starting from , and , the LFSR will iterate through the following states:

The polynomial produces three distinct sequences of internal states (together containing all non-zero 4-bit binary numbers) of the same length. It is therefore an ireducible (but not primitive) polynomial.


Thomas Busby

Thomas Busby

I write about computing stuff

comments powered by Disqus
rss facebook twitter github youtube mail spotify instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora