= Solution
A binary <linear-feedback shift register> of degree $d$ has a state
$(s_n,\ldots,s_{n+d-1})\in\mathbb F_2^d$ and recurrence
$$
s_{n+d}=a_{d-1}s_{n+d-1}+\cdots+a_0s_n.
$$
Its feedback polynomial is
$$
f(X)=X^d+a_{d-1}X^{d-1}+\cdots+a_0.
$$
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 by
$$
s_{n+8}=s_n,
$$
with initial state $10000000$. It produces the next bit $1$ and has feedback polynomial
$$
\boxed{f(X)=X^8+1}.
$$
\b[Thus this is the <minimal linear-feedback shift register for the prefix 100000001>.]
Back to article page
