Overview

One way of providing a pseudo random bit stream is to use a shift register in which the bits shifted in depend on the current contents of the shift register. There are two forms for such shift registers: Fibonacci form and Galois form. The Fibonacci form is a linear recurrence equation, in which a linear combination of some among the previous bits yeilds the next bit. The Galois form directly models taking the element x in the Galois field GF(2^n) to successive powers.

The correct feedback taps in the shift register are required in order to get a bit sequence that does not repeat to quickly. For a Fibonacci shift register, rather than the recurrence, one looks at the companion polynomial c(x), which is related to the recurrence, and more directly to the taps of the shift register, to determine cycle length. Maximum cycle length is achieved if this polynomial is primitive, and more generally, the order of x in the field F_2 mod c(x) must divide the cycle length. This note discusses that phenomena.

A previous note discussed this, but only for the Galois form. Those notes ostensively worked with a Fibonacci form, however the companion polynomial was of a particular form, having just three terms. When there are just three terms the Galois and Fibonacci forms are identical, the only difference being how the drawing is layed out, where to break the circular shift register into a linear shift with feedback. When starting from the Galois form there is an obvious argument, since the shifting is exactly multiplication by x, and the feedback simulates the mod c(x) reduction. In these notes we deal truely with Fibonacci forms.

Proof

A shift register in Fibonacci form is considered the rolling up of recurrence equation. Our example will be this shift register:

       +-------|\________
       |   +---|/        |
       |   |             |
     +---+---+---+---+   |
     |   |   |   |   | <-+
     +---+---+---+---+

      si = si-3 + si-4,

      S(x) = Sumi si xi.

If the period is N, S(x) can be writen as a repetition of a finite polynomial s'(x), of degree one less than the cycle length:

      S(x) = s'(x) ( 1 + xN + x2N + ... )

     c(x) S(x) = (1 + x3 + x4) S(x) = f(x)

The polynomial c(x) is called the companion polynomial, and can be gotten by inspection from the shift register.

The result then is:

      c(x) s'(x) ( 1 + xN + x2N + ... ) = 1

      c(x) s'(x) = 1 + xN

In the case c(x) is primitive, then by the definition of primitive the order of x is 2^k-1, where k is the degree of the companion polynomial. However, N cannot be larger than this since this number exhausts the internal states of the shift register. Therefore the order is exactly 2^k-1.

Example

Using the shift register with 4 cells, and taps at the two deepest cells, the recurrence is as noted above,

    si = si-3 + si-4. 

Begin by placing a 1 in the first cell of the first row, and repeat that value in the other rows, suitably shifted. Placing x's in the other rows helps align the values. Now continue by choosing a value for the next cell in the first row that makes the columnwise excluse or zero, and repeat that value in the corresponding (next empty) cell in each of the following rows.

In the following table, the blue cells are those that are actually the initial values in the shift register. Beginning with the yellow tinted cells, the values are determined by the recurrence and the previous 4 values. The next blue tinted cells mark where the pattern repeats.

References

• Viiveke Fak class notes
• Architectural consideration for cryptanalytic hardware, by Ian Goldberg and David Wagner. (PDF)
• Fibonacci and Galois Representations of Feedback with Carry Shift registers, Mark Goresky and Andrew Klapper. (PDF)
• My notes from a previous semester crypto course.