1

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 \}$
Jason S
  • 3,109

1 Answers1

2

$\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...

Angina Seng
  • 158,341
  • Thanks! Any recommendations for material that explains what a trace map is and how it relates to finite fields? – Jason S Jul 05 '17 at 04:34
  • @JasonS For anything on finite fields, the first place to look is the text by Lidl and Niederreiter. – Angina Seng Jul 05 '17 at 04:36
  • thanks! Looks similar to Niven and Zuckerman in terms of readability to amateur mathematicians but covers more applied topics. – Jason S Jul 05 '17 at 05:24