*Author: Burt Rosenberg*

*Created: 11 March 2009*

*Last Update: 11 March 2009*

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:

+-------|\________ | +---|/ | | | | +---+---+---+---+ | | | | | | <-+ +---+---+---+---+Normally these things are drawn with the shift moving bits to the right, but I have drawn it here with the shift moving bits to the left. This way it is easier to see that the recurrence equation is:

swith addition in F_2, that is, exclusive or of bits. Write the sequence s_i as a generating function:_{i}= s_{i-3}+ s_{i-4},

S(x) = SumThis is an infinite sum. Since the four bits in the register fix the future development of the series, after at most 16 steps, the sequence repeats. In general, it is seen that for a LFSR it must repeat. Since it is possible to solve for s_(i-4) in the recurrence, it can be run backwards. Therefore it will be purely periodic, without a preamble before the periodic part._{i}s_{i}x^{i}.

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 + xFrom the recurrence, we see that by adding shifts of S(x) with itself, we can annihilate the large degree terms. In this case, shifting by 3 and 4, and summming with the original gives s_i + s_(i-3) + s_(i-4) = 0, except for the lowest terms where the shifted S(x) do not overlap. The shift and sum is accomplished by multiplying by the appropriate plynomial, in this case 1 + x^3 + x^4,^{N}+ x^{2N}+ ... )

c(x) S(x) = (1 + xand the degree of f(x) is less than the degree of c(x). Actually, a careful setting of the initial terms in the sequence of s_i can make f(x)=1. An example of how this is done follows in the next section.^{3}+ x^{4}) 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 + xMultiplying both sides by 1+x^N,^{N}+ x^{2N}+ ... ) = 1

c(x) s'(x) = 1 + xNow take this mod c(x). The left hand side is zero, so the order of x in F_2 mod c(x) must divide N. Note that if we hadn't adjusted the leading s_i so that the right hand side is 1, we still would have to conclude that 1+x^N is zero mod c(x).^{N}

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,

sThe companion polynomial shifts the sequence so as to zero out the higher order terms. So we begin by having a table with three rows, one for each term in the sequence, having the sequence in the top row, the sequence shifted by 3 in the second row, and shifted by 4 in the third row._{i}= s_{i-3}+ s_{i-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.

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | ... |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | . | . | . | . | . |

x | x | x | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | . | . |

x | x | x | x | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | . |

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.