Consider the following random bit generator $($a LFSR of a sort slightly more

general than the ones we have seen in class.$)$

Take an array of $32$ cells, each holding one bit. The state of this generator

consists of the contents of this array, i$.$e$.$ it consists of $32$ bits. Define the following

operations on states of this generator:

$o+$ is the bitwise XOR operation i$.$e$.$ the $i^{th}$ bit of $x_{0}cdots{x}_{31}o+w_{0}cdots{w}_{31}$ is

$x_{i}o+w_i$

$$ is the left shift so e$.$g$.x_{0}cdots{x}_{31}2=x_{2}cdots{x}_{31}00$;

$$ is the right shift so e$.$g$.x_{0}cdots{x}_{31}3=000x_{0}cdots{x}_{28}.$

The generator is initialized by loading some choice of $32$ bits into the state.

At each time step: we output the first bit $x_0,$ then replace the state $x=x_{0}cdots{x}_{31}$

$($where $x_i$ is the bit in cell $i)$ with $f(x)$ where

$y=xo+(x13)$

$z=yo+(y17)$

$f(x)=zo+(z5).$

e$.$g$.$ starting with the state $(0,$dots,$0,1),$ the output is $0$ and the next state has

$x_{13},x_{18},x_{26},x_{31}=1($and all other bits $0).$ At the next step, the output is $0$ and

the next state has $x_5,x_{12},x_{21},x_{22},x_{31}=1($and all other bits $0).$

$($a$)$ Find $32-$by$-32$ matrices $Y,Z,$ and $F($with entries in $\frac{Z}{2}Z)$ such that $y=Yx,$

$z=Zy,$ and $f(x)=Fx($where all matrix operations are done mod$2,$ and we

write the state as a column vector$).$

$($b$)$ Assume the first rows of the matrix powers $F^0=$I,$F^1,$dots,$F^{31}$ are linearly

independent. Use this to show how to completely determine the state of this

generator $($and hence all of its future output$)$ from $32$ known consecutive output

bits.