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.
- 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..?
- How do I use these initialization vectors in the formula it gives
$\begingroup$
$\endgroup$
2
-
$\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$– cpastFeb 22, 2015 at 20:29
-
$\begingroup$ Mistype when I fixed my subscripts. That you for pointing it out. $\endgroup$– ConnorFeb 22, 2015 at 20:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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...
