O'Reilly logo

Computer Security and Cryptography by Alan G. Konheim

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

8.4 THE CHARACTERISTIC POLYNOMIAL OF A LINEAR FEEDBACK SHIFT REGISTER

The characteristic polynomial of the N-stage LFSR with recursion

image

and feedback coefficients {ci} is

image

We will always assume c0 = cN = 1.

Example 8.3

The LFSR with characteristic polynomial p(z) = 1 + z + z2 + z3 is shown in Figure 8.3. As p(z) does not divide 1 + zk for k = 1, 2, 3 and (1 + z)p(z) = 1 + z4, 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 s0(0), s0(1), s0(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) = cN + cN−1z + ··· + c1zN−l + c0zN is the characteristic polynomial of the LFSR, then

8.3a The period of the output sequence s0(0), s0(1), s0(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 s0(0), s0(1), s0(2), … is 2N − 1 if and only if p(z) is primitive.

Example 8.4

The LFSR with characteristic polynomial p(z) = 1 + z + z3 is shown in Figure 8.4. The exponent of p(z) was shown to be ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required