= Feedback-polynomial parity condition for maximal period
For a binary <linear-feedback shift register> of length $d\ge2$, a feedback <polynomial> with maximal period $2^d-1$ cannot have $1$ as a <polynomial root>. A root at $1$ would make the nonzero all-one state fixed, whereas maximal period requires all nonzero states to lie in one cycle of length greater than one.
Writing the <monic polynomial> as $p(X)=X^d+a_{d-1}X^{d-1}+\cdots+a_0$, this gives
$$
p(1)=1+a_{d-1}+\cdots+a_0\ne0.
$$
Over the <field with two elements>, an even number of the feedback coefficients $a_i$ must therefore equal one, and $p$ has an odd number of nonzero coefficients. This is a necessary condition, not a sufficient test for a <primitive polynomial>. The restriction $d\ge2$ matters: for $d=1$, $X+1$ has maximal nonzero-state period $1$ despite having $1$ as a <polynomial root>.
Back to article page