# Linear Recurrence, keystreams, and periods

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
• 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. – cpast Feb 22 '15 at 20:29
• Mistype when I fixed my subscripts. That you for pointing it out. – 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...