Suppose we have $GF(2^n)$ expressed as the quotient ring $GF(2)[x]/p(x)$ where $p(x)$ is a particular primitive polynomial of degree $n$.
Suppose also that the function $c_0(f(x))$ is the constant coefficient of $f(x) \bmod p(x)$, e.g. $c_0(1) = 1$, $c_0(x^2+x) = 0$, $c_0(x^5) = c_0(x^2+1) = 1$ for $p(x) = x^5 + x^2 + 1$.
It appears (based on some empirical work on my computer) that the following sequences are just cyclic shifts of each other. Is there any way to prove it? (or find a counterexample?)
- $\{c_0({x^k})\} = \{c_0(1), c_0(x), c_0(x^2), c_0(x^3), \ldots \}$
- $\{c_0({x^{2k}})\} = \{c_0(1), c_0(x^2), c_0(x^4), c_0(x^6), \ldots \}$
- $\{c_0({x^{4k}})\} = \{c_0(1), c_0(x^4), c_0(x^8), c_0(x^{12}), \ldots \}$
- $\{c_0({x^{8k}})\} = \{c_0(1), c_0(x^8), c_0(x^{16}), c_0(x^{24}), \ldots \}$
...
- $\{c_0({x^{2^{n-1}k}})\} = \{c_0(1), c_0(x^4), c_0(x^8), c_0(x^{12}), \ldots \}$
$\newcommand{\F}{\Bbb F}$ Every $\F_2$-linear map from $\F_{2^2}$ to $\F_2$ has the form $\alpha\mapsto T(\xi\alpha)$ where $\xi$ is a fixed element of $\F_{2^n}$ and $T$ is the trace map from $\F_{2^m}$ to $\F_2$.
Your first two sequences are $T(\xi x^n)$ and $T(\xi x^{2n})$. The trace function $T$ satisfies $T(\alpha^2)=T(\alpha)$, so $T(\xi x^n)=T(\xi^2 x^{2n})$. Provided that $x$ is a primitive element of $\F_{2^m}$, that is it is a generator of its multiplicative group, then $\xi=x^{2r}$ for some $r$. Then $T(\xi x^n)=T(\xi x^{2(n+r)})$. Therefore the first two sequences are cyclic shifts of each other. It will follow that all of them are.
If your $x$ is not a primitive element, I'm not sure the conclusion will hold...