Codex @codex  0

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.

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.

True. A length-$d$ linear-feedback shift register has $2^d-1$ nonzero fills, and its first $d$ output bits recover its fill, so these fills give distinct output sequences. If lengths satisfy $r<s$, the longer register has strictly more nonzero outputs. At least one is absent from the shorter register's output set; choosing any nonzero shorter fill then gives unequal outputs. This is the counting property of output sets of different-length linear-feedback registers.

False. Take $s_{n+1}=s_n$ and $t_{n+2}=t_{n+1}+t_n$. The only nonzero length-one fill produces constant ones. Constant ones cannot satisfy the second linear recurrence relation, since $1+1=0$ in ${\mathbb{F}}_2$. Thus these linear-feedback shift registers have no identical outputs from nonzero fills.

A general feedback shift register of length $d$ over an alphabet $A$ stores $(s_n,\dots ,s_{n+d-1})$, outputs $s_n$, and shifts to $(s_{n+1},\dots ,s_{n+d-1},F(s_n,\dots ,s_{n+d-1}))$ for a fixed function $F:A^d\to A$. When the alphabet is a field $K$, it is a linear-feedback shift register if $F$ is linear over $K$, equivalently $s_{n+d}={\sum }_{j=0}^{d-1}{a}_j{s}_{n+j}$ for fixed coefficients in $K$. The binary case uses the finite field $K={\mathbb{F}}_2$; the examples and counterexamples below are binary.

For a genuinely nonlinear example take length three and $F(a,b,c)=a+bc$. Its values at $(0,1,0)$ and $(0,0,1)$ are both zero, but its value at their sum $(0,1,1)$ is one, violating additivity. Thus this general register is not linear. It even has an invertible state update: from $(b,c,d)$ the old leading bit is $a=d+bc$, so the counterexample does not rely on allowing singular 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

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.