What does it mean to say that $f: \mathbb{F}_{2}^{d} \rightarrow \mathbb{F}_{2}^{d}$ is a linear feedback shift register? Let $\left(x_{n}\right)_{n \geqslant 0}$ be a stream produced by such a register. Show that there exist $N, M$ with $N+M \leqslant 2^{d}-1$ such that $x_{r+N}=x_{r}$ for all $r \geqslant M$.

Describe and justify the Berlekamp-Massey method for 'breaking' a cipher stream arising from a linear feedback register of unknown length.

Let $x_{n}, y_{n}, z_{n}$ be three streams produced by linear feedback registers. Set

$$\begin{aligned} &k_{n}=x_{n} \quad \text { if } y_{n}=z_{n} \\ &k_{n}=y_{n} \quad \text { if } y_{n} \neq z_{n} \end{aligned}$$

Show that $k_{n}$ is also a stream produced by a linear feedback register. Sketch proofs of any theorems you use.