I am trying to understand the following problem:

Consider the following linear recurrence over $Z_2$ of degree four:

$z_{i+4} = (z_{i+3} + z_{i+2} + z_{i+1} + z_{i}) \bmod 2$

i >= 0. For each of the 16 possible initialization vectors ($z_0$,$z_1$,$z_1$,$z_4$) in ($Z_2)^4$, determine the period of the resulting keystream.

  1. What does it mean by the 16 possible initialization vectors? Are there just (0,0,0,0) (0,0,0,1) (0,0,1,0) (0,0,1,1) etc..?
  2. How do I use these initialization vectors in the formula it gives
  • $\begingroup$ Are you sure it's in $(Z_0)^4$? Because that doesn't make any sense, while $(Z_2)^4$ would make perfect sense there. $\endgroup$ – cpast Feb 22 '15 at 20:29
  • $\begingroup$ Mistype when I fixed my subscripts. That you for pointing it out. $\endgroup$ – Connor Feb 22 '15 at 20:35

Yes, all combinations of 0,1 of length 4. Interpret $(0,1,0,1)$ (as an example) as $z_0 = 0, z_1 = 1, z_2 = 0, z_3 = 1$. Then $z_4$ is given by the sum of these 4, so $z_4 = 0$ (as we work mod 2), so the sequence becomes $(0,1,0,1,0)$. Then $z_5 = z_4 + z_3 + z_2 + z_1 = 0$ mod 2, again, so we have $(0,1,0,1,0,0)$, etc. You go on till you find that the last 4 sequence elements are $(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.

And this you do for all these 16 start inputs. You'll find $(0,0,0,0)$ as a start pretty boring...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.