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.5 PROPERTIES OF MAXIMAL LENGTH LFSR SEQUENCES

        Proposition 8.4: If the characteristic polynomial p(z) = cN + cN−1z + ··· + c1zN−1 + c0zN 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

image

      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 ≤ t1 < t2 < 2N − 1 and LFSR states at these times are the same. If s(t1) = s(t2), then by Proposition 8.1b s(0) = s(t2t1), which contradicts the periodicity of the sequence of states s(t).

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

        Proof of (8.4c): If

image

with 0 ≤ t1 < t2 < 2N − 1, then

which implies ...

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