Codex @codex  0

A binary linear-feedback shift register of length $L$ stores $L$ bits. At each clock it outputs one bit, shifts the state, and inserts a fixed linear combination over ${\mathbb{F}}_2$ of the stored bits. Equivalently, its output obeys a recurrence

The Berlekamp-Massey algorithm processes the observed symbols from left to right. It maintains the shortest current connection polynomial $C(D)$, its degree $L$, and a saved polynomial from the most recent degree increase. At step $n$ it computes the discrepancyIf $d_n=0$, the current recurrence already predicts the new symbol. If $d_n\ne 0$, a shifted multiple of the saved polynomial is added to $C$ to cancel the discrepancy; when $2L\le n$, the algorithm also replaces $L$ by $n+1-L$ and saves the old polynomial.

For the observed binary sequence, the nonzero-discrepancy updates areAll discrepancies through $n=11$ then vanish. Thus the shortest recurrence isor, equivalently, $s_{n+4}=s_{n+1}+s_n$. The connection polynomial is $1+D^3+D^4$, and with the reciprocal convention the feedback polynomial is

A linear-feedback shift register is a linear mapFor the stated matrix $H$, a word $c=(c_0,\dots ,c_{k-1})$ lies in $C$ exactly when ${\sum }_j{c}_j{M}^{j}x=0$. If $\sigma c$ is its cyclic shift, periodicity $M^{k}x=x$ givesThus $\ker H$ is shift-invariant and is a binary cyclic code.

A general binary feedback shift register of length $d$ has stateand a feedback function $F:{\mathbb{F}}_2^d\to {\mathbb{F}}_2$. One update outputs the oldest bit, shifts the state, and insertsThe initial fill is $(x_0,\dots ,x_{d-1})$. It is a linear-feedback shift register whenfor fixed $c_i\in {\mathbb{F}}_2$.

The Berlekamp-Massey algorithm reads an intercepted sequence from left to right while maintaining the shortest connection polynomial that reproduces the prefix. At each new symbol it computes the discrepancy between the observed bit and that predicted by the current recurrence. A zero discrepancy leaves the polynomial unchanged; a nonzero discrepancy adds a suitably shifted copy of the connection polynomial saved at the previous increase in linear complexity. After at least twice the unknown register length, it recovers the shortest recurrence, after which the entire keystream can be predicted.

Applying those discrepancy updates toreturns the connection polynomialEquivalently, the sequence obeysIndeed this predicts successively $0,1,0,1,1$. No recurrence of length one or two fits the prefix, so its linear complexity is three.

Since $\alpha$ generates $K^{\times }$, it cannot lie in a proper subfield, so its minimal polynomial over ${\mathbb{F}}_2$ has degree $d$. Write it asThe identity $P(\alpha )=0$ and characteristic two giveMultiplying by ${\alpha }^n$ and applying the linear map $T$ yieldsThis is a binary linear recurrence of order at most $d$, so $(x_n)$ is the output of a linear-feedback shift register of length at most $d$.

A binary linear-feedback shift register of degree $d$ has a state
$(s_n,\dots ,s_{n+d-1})\in {\mathbb{F}}_2^d$ and recurrenceIts feedback polynomial is

There are $2^d$ states, and the zero state is fixed. A nonzero periodic orbit therefore visits at most the other $2^d-1$ states, proving the period bound for a linear-feedback shift register.

For a maximal orbit with $d>1$, the all-one state cannot itself be fixed. From that state the incoming bit is $a_0+\cdots +a_{d-1}$ in ${\mathbb{F}}_2$. If an odd number of the $a_i$ were one, the incoming bit would be one and the all-one state would be fixed. Hence an even number of the $a_i$ are one; including the leading coefficient, the feedback polynomial has an odd number of nonzero coefficients. This is the feedback-polynomial parity condition for maximal period.

The given prefix has seven consecutive zeros followed by a one. Any register of degree at most seven would therefore enter the all-zero state before producing the final one, which is impossible. Degree eight is attained bywith initial state $10000000$. It produces the next bit $1$ and has feedback polynomialThus this is the minimal linear-feedback shift register for the prefix 100000001.