Computer Security and Cryptography

8.5 PROPERTIES OF MAXIMAL LENGTH LFSR SEQUENCES

        Proposition 8.4: If the characteristic polynomial p(z) = c_N + c_N−1z + ··· + c₁z^N−1 + c₀z^N of an N-stage LFSR is primitive and the initial state is not null s(0) ≠ (0)_N, then

8.4a	The sequence of states s(0), s(1), … are distinct and periodic with period 2N − 1,
8.4b	Every N-tuple v = (v0, v1, …, vN−1) ≠ (0)N is a state s(t) of the LFSR for some t with 0 ≤ t < 2N − 1,
8.4c	The sum of two states s(t1) and s(t2) of the LFSR with 0 ≤ t1 < t2 < 2N − 1 is another state of the LFSR, and
8.4d	If 0 < τ < 2N − 1, the sequence of sums of states

      is a translate of the state sequence s(0), s(1), …, that is s(t + s) = s(t) + s(t + τ) for some s.

        Proof of (8.4a): Suppose on the contrary that 0 ≤ t₁ < t₂ < 2^N − 1 and LFSR states at these times are the same. If s(t₁) = s(t₂), then by Proposition 8.1b s(0) = s(t₂ − t₁), which contradicts the periodicity of the sequence of states s(t).

        Proof of (8.4b): If the 2^N-states s(0), s(1), …, s(2^N − 1) are distinct and s(t) ≠ (0)_N, then every N-tuple other than (0)_N must be a state of the LFSR.

        Proof of (8.4c): If

with 0 ≤ t₁ < t₂ < 2^N − 1, then

which implies ...