Help with linear recurrence.

Question

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_0)^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?

Answer 1

The $16$ different choices for $(z_0, z_1, z_2, z_3)$ - which is what is meant by the "$16$ possible initialization vectors" - lead to four different outcomes; one of which is all zeros, and the other $3$ exhibit a period of length $5$:

$$\begin{array}{c|c} \text{Initial vector} & \text{Outcome} & \text{Period} \\ \hline (0,0,0,0) & (0) & 1 \\ (0,0,0,1) & (0,0,0,1,1) & 5 \\ (0,1,0,1) & (0,1,0,1,0) & 5 \\ (0,1,1,1) & (0,1,1,1,1) & 5 \\ \end{array}$$

All other initial choices for $(z_0, z_1, z_2, z_3)$ lead into one of these, as can be seen by examining the outcomes. For example, $(0,0,0,1,1)$ is also generated by $(1,1,0,0)$ (although shifted), since $(0,0,0,1,1,0,0,0,1,1)$ contains $(1,1,0,0)$.

---

Extra question: What would change if the recurrence was $z_{i+4} = (z_i+z_{i+3}) \bmod 2$ ?

That would have a single outcome (other than the zero case) as I define it above, with period 15: $(0,0,0,1,1,1,1,0,1,0,1,1,0,0,1)$

Answer 2

You're correct that the 16 initialization vectors would be (0,0,0,0), (0,0,0,1), (0,0,1,0), (0,0,1,1), etc. The initialization vector gives the values of $z_0, z_1, z_2$, and $z_3$, from which all other values $z_k$ are uniquely determined using the recurrence relation.

For example, given the initialization vector $(0,0,1,1)$, we have $z_0=0, z_1=0, z_2=1, z_3=1$, and therefore, substituting $i=0,1,2,\dots$ into the recurrence equation $z_{i+4}=z_{i+3}+z_{i+2}+z_{i+1}+z_i\pmod2$, we get \begin{align*} z_4 &\equiv (z_3+z_2+z_1+z_0) \equiv 1+1+0+0 \equiv 0 \pmod{2}\\ z_5 &\equiv (z_4+z_3+z_2+z_1) \equiv 0+1+1+0 \equiv 0 \pmod{2}\\ z_6 &\equiv (z_5+z_4+z_3+z_2) \equiv 0+0+1+1 \equiv 0 \pmod{2}\\ z_7 &\equiv (z_6+z_5+z_4+z_3) \equiv 0+0+0+1 \equiv 1 \pmod{2}\\ z_8 &\equiv (z_7+z_6+z_5+z_4) \equiv 1+0+0+0 \equiv 1 \pmod{2}\\ z_9 &\equiv (z_8+z_7+z_6+z_5) \equiv 1+1+0+0 \equiv 0 \pmod{2}\\ \dots \end{align*} From here on the pattern will repeat, so the period is 5 in this case.