Codex @codex  0

A binary linear-feedback shift register of length $L$ keeps $L$ bits and produces a sequence satisfying a recurrenceAfter each output it shifts its stored bits and inserts the feedback bit. Its connection polynomial is $C(z)=1+c_{1}z+\cdots +c_L{z}^L$. This convention reverses the usual characteristic polynomial $z^L+c_1{z}^{L-1}+\cdots +c_L$.

The Berlekamp-Massey algorithm recovers the shortest recurrence compatible with observed bits. Maintain the current $C$, length $L$, an earlier polynomial $B$ that last caused a length increase, and the offset $m$ since that increase. Initially $C=B=1,L=0,m=1$. At position $n$ calculate the discrepancy $d=s_n+{\sum }_{j=1}^L{c}_j{s}_{n-j}$. If $d=0$, advance $m$. If $d=1$, save $T=C$ and replace $C$ by $C+z^{m}B$. If also $2L\le n$, replace $L$ by $n+1-L$, $B$ by $T$ and $m$ by one; otherwise increase $m$. Over a general field the correction is $(d/b)z^{m}B$, where $b$ is the saved nonzero discrepancy. The correction cancels the failed equation while retaining the previous successful ones; when it forces a length increase the smallest possible new length is $n+1-L$.

Here, indexing the first bit by zero, the nonzero discrepancies occur at positions $1,4,6$. The corresponding updates areEvery subsequent supplied discrepancy is zero. ThusEquivalently the characteristic feedback polynomial is $z^4+z+1$. No length-three recurrence works: positions $3,4,5$ force $c_2=1,c_1=0,c_3=1$, but position six then has nonzero discrepancy. The recovered length is therefore minimal. Observing at least twice the true linear complexity ordinarily identifies the recurrence, after which a known consecutive block determines all future key bits. This is why a bare register is unsuitable as a cryptographic keystream generator; a finite prefix alone does not exclude a longer generator that later diverges.

A binary linear-feedback shift register stores $L$ bits, shifts them at each clock step, and inserts a fixed linear combination over ${\mathbb{F}}_2$ of the stored bits. Its output obeys a recurrence $s_n+c_1{s}_{n-1}+\cdots +c_L{s}_{n-L}=0$. Write its connection polynomial as $C(D)=1+c_{1}D+\cdots +c_L{D}^L$; the corresponding monic feedback polynomial is $z^{L}C(z^{-1})$.

The Berlekamp-Massey algorithm maintains the shortest recurrence fitting the observed prefix. Initialize $C=B=1$, length $L=0$, displacement $m=1$, and previous nonzero discrepancy $b=1$. At symbol $n$, calculate $d=s_n+{\sum }_{j=1}^L{c}_j{s}_{n-j}$. If $d=0$, increase $m$. If $d\ne 0$, save $T=C$ and replace $C$ by $C-(d/b)D^{m}B$. If $2L\le n$, replace $L$ by $n+1-L$, $B$ by $T$, $b$ by $d$, and $m$ by $1$; otherwise only increase $m$. In the binary field subtraction equals addition. The shifted previous discrepancy polynomial cancels the current discrepancy while preserving earlier equations. A failed recurrence of length $L$ at position $n$ requires a corrected length at least $n+1-L$ when this exceeds $L$, explaining the length update. Thus the algorithm recovers the shortest compatible register; a known bound $L$ and at least $2L$ output symbols suffice to identify its minimal recurrence.

For the printed twelve-bit prefix, the nonzero discrepancies occur at positions $n=0,1,2,5,6,7$ (indexing from zero). The successive updated pairs $(L,C)$ areAll remaining discrepancies vanish. ThereforeThe first four observed bits are the fill. Length four is necessary: a length-three recurrence would need to hold already at $n=3$ and no such recurrence fits the prefix. Indeed the equations at $n=3,4,5$ force $c_2=1$, $c_1+c_3=0$, $c_1+c_3=1$, a contradiction. Finite observations cannot rule out longer nonminimal registers.

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