= Trace-generated maximal-period linear-feedback sequence
Let $K=\mathbb F_{2^d}$, let $\alpha$ generate $K^\times$, and let $T:K\to\mathbb F_2$ be nonzero linear with <nondegenerate bilinear form> $(x,y)\mapsto T(xy)$. If the <minimal polynomial> of $\alpha$ is $P(X)=X^d+\sum_{j<d}c_jX^j$, then $x_n=T(\alpha^n)$ satisfies
$$
x_{n+d}=\sum_{j<d}c_jx_{n+j},
$$
so it is produced by an LFSR of length at most $d$. Its period is exactly $2^d-1$: any period $r$ would imply $T((\alpha^r-1)y)=0$ for every $y\in K$, hence $\alpha^r=1$ by nondegeneracy.
Back to article page
