## 8.4 THE CHARACTERISTIC POLYNOMIAL OF A LINEAR FEEDBACK SHIFT REGISTER

The *characteristic polynomial* of the *N*-stage LFSR with recursion

and feedback coefficients {*c _{i}*} is

We will always assume *c*_{0} = *c _{N}* = 1.

*Example 8.3*

The LFSR with characteristic polynomial *p*(*z*) = 1 + *z* + *z*^{2} + *z*^{3} is shown in Figure 8.3. As *p*(*z*) does not divide 1 + *z ^{k}* for

*k*= 1, 2, 3 and (1 +

*z*)

*p*(

*z*) = 1 +

*z*

^{4}, the exponent of

*p*(

*z*) is 4. Table 8.5 gives the output and states of this LFSR for three different initial states. Table 8.5 illustrates that the period of the sequence

*s*

_{0}(0),

*s*

_{0}(1),

*s*

_{0}(2), … depends on the initial state

*s*(0):

*s*(0) = (0, 0, 1) produces a sequence of period 3,*s*(0) = (1, 0, 1) produces a sequence of period 2, and*s*(0) = (1, 1, 1) produces a sequence of period 1.

**Proposition 8.3:** [Beker and Piper, 1982, pp. 192–193] If *p*(*z*) = *c _{N}* +

*c*

_{N−1}

*z*+ ··· +

*c*

_{1}

*z*

^{N−l}+

*c*

_{0}

*z*is the characteristic polynomial of the LFSR, then

^{N}8.3a |
The period of the output sequence s_{0}(0), s_{0}(1), s_{0}(2), … is a divisor of the exponent of p(z), and |

8.3b |
If the initial state s(0) ≠ (0)_{N}, the period of the output sequence s_{0}(0), s_{0}(1), s_{0}(2), … is 2^{N} − 1 if and only if p(z) is primitive. |

*Example 8.4*

The LFSR with characteristic polynomial *p*(*z*) = 1 + *z* + *z*^{3} is shown in Figure 8.4. The exponent of *p*(*z*) was shown to be ...

Get *Computer Security and Cryptography* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.