Question

Consider the following linear recurrence over Z₂ of degree four:

Z_i+4 = (Z_i + Z_i+3) mod 2,

i ≥ 0. For each of the 16 possible initialization vectors (Z₀, Z₁, Z₂, Z₃) Ԑ (Z₂)⁴, determine the period of the resulting keystream.

Answer 1

ANS : All combinations of 0,1 of length 4. Interpret (0,1,0,1)(0,1,0,1) (as an example) as z0=0,z1=1,z2=0,z3=1z0=0,z1=1,z2=0,z3=1.

Then z4z4 is given by the sum of these 4, so z4=0z4=0 (as we work mod 2), so the sequence becomes (0,1,0,1,0)(0,1,0,1,0). Then z5=z4+z3+z2+z1=0z5=z4+z3+z2+z1=0 mod 2, again, so we have (0,1,0,1,0,0)(0,1,0,1,0,0), etc. You go on till you find that the last 4 sequence elements are (0,1,0,1)(0,1,0,1) again, and then you know the period (you're back where you started): the number of steps (i.e. new sequence elements computed) taken to get there.