Past exam of the mathematics course of the University of Cambridge / 2005 / ii / Paper 2 / 12J (Coding and Cryptography)

A linear-feedback shift register of length $d$ has binary state $(x_r,\dots ,x_{r+d-1})$ and updateIts output obeys $x_{r+d}={\sum }_{j=0}^{d-1}{a}_j{x}_{r+j}$ over ${\mathbb{F}}_2$. Since the state space is finite, its trajectory consists of a transient of length $M$ followed by a cycle of length $N\ge 1$, and the output satisfies $x_{r+N}=x_r$ for $r\ge M$.

If the trajectory never reaches zero, all its $M+N$ distinct transient and cyclic states are nonzero; hence $M+N\le 2^d-1$. If it reaches zero, let $M$ be its first zero-state time. The vectors $v,fv,\dots ,f^{M-1}v$ are linearly independent: in a dependence, apply $f^{M-1-j}$ where $j$ is the smallest index with a nonzero coefficient; every later term vanishes and the remaining term is $f^{M-1}v\ne 0$. Therefore $M\le d$. The zero cycle has $N=1$, and $d+1\le 2^d-1$ for $d\ge 2$. This proves the requested bound for all $d\ge 2$, and for every invertible register.

The unrestricted printed assertion has one exception: at $d=1$, the zero-feedback register with initial state one outputs $1,0,0,\dots$. It requires $M\ge 1,N\ge 1$, so $M+N\ge 2>2^1-1$. The universally valid finite-state bound is $M+N\le 2^d$. A register with feedback from its oldest bit is invertible, in which case a nonzero state never reaches zero and the sharper bound holds already with $M=0$.

To recover an unknown register from a known plaintext/ciphertext keystream, the Berlekamp-Massey algorithm finds a shortest linear recurrence consistent with the observed bits. Use a connection polynomial $C(z)=1+{\sum }_{j=1}^L{C}_j{z}^j$, so the recurrence discrepancy at index $r$ is $\delta =x_r+{\sum }_{j=1}^L{C}_j{x}_{r-j}$. Initialize $C=B=1,L=0,b=1,m=1$. Process the bits in order. If $\delta =0$, increment $m$. If $\delta \ne 0$, save $T=C$ and replaceIf $2L\le r$, also replace $L$ by $r+1-L$, set $B=T,b=\delta ,m=1$; otherwise retain $L,B,b$ and increment $m$. Arithmetic is binary, so every nonzero discrepancy equals one. The stored polynomial $B$ last failed at an earlier index with discrepancy $b$; its shifted contribution cancels the new failure without changing previous successful discrepancies.

Here is the minimum recurrence length after a new discrepancy argument behind the update, not just its name. Suppose a span-$L$ recurrence $C$ succeeds through index $r-1$ but fails at $r$. If another polynomial $D$ of span $L^{\prime }$ succeeded through $r$ and $L+L^{\prime }\le r$, compute the convolution $(CD)x$ at $r$ in two ways. Applying $D$ first gives zero, since all indices $r-j$ used by $C$ lie at least at $L^{\prime }$. Applying $C$ first gives its nonzero discrepancy at $r$, since its earlier discrepancies used by $D$ vanish and $D_0=1$. This contradiction proves $L^{\prime }\ge r+1-L$. The shifted-polynomial update attains the larger of the existing minimum length and this new lower bound; induction therefore gives the shortest recurrence for every prefix. Once at least twice the true linear complexity has been observed, this recurrence determines the whole stream: the difference from a true degree-$d$ recurrent stream satisfies a recurrence of degree at most $d+L$, and a prefix of that many zeros forces every later value to be zero. Without any bound on complexity, a finite observed prefix cannot exclude a longer register that diverges later; the breaking claim uses the finite-register hypothesis and adequate known data.

Finally each of the three input streams is eventually periodic. Let $M$ be the maximum of their transient lengths and $N$ a common multiple of their periods. Their joint triple, and hence the bit chosen by the specified rule, repeats after $N$ once $r\ge M$. ThereforeThis itself is a linear recurrence of length $M+N$, so it constructs a linear-feedback shift register producing the selected stream from its first $M+N$ bits. No closure theorem is being assumed: eventual periodicity and this explicit recurrence prove the combined stream is also an LFSR stream, even though the combining rule is nonlinear in its three inputs.