# $\alpha^{2^{m} + 1}$ is a generator of $\operatorname{GF}(2^m)$?

This is from a paper (Partitions in the S-Box of Streebog and Kuznyechik) about S-Boxes:

Let $$\operatorname{GF}(2^{2m}) = \mathbb{F}_2[X]/p(X)$$ be a finite field of even degree defined by a primitive polynomial $$p$$. The multiplicative subgroup $$\operatorname{GF}(2^{2m})^*$$ is cyclic and generated by $$\alpha$$ which is such that $$p(\alpha) = 0$$.

In this context, $$\alpha^{2^{m} + 1}$$ is a generator of the multiplicative subgroup of the subfield $$\operatorname{GF}(2^m)$$

I don't understand why it holds that $$\alpha^{2^{m} + 1}$$ is a generator of the subfield?

Since you haven't heard of splitting fields, here is an argument based on more elementary group theory.

Let $$G$$ denote a cyclic group. Then, it is easy to show (or you might already know it) that if $$\alpha \in G$$ is an element of order $$n$$ (we write $$\mathsf{ord}(\alpha)=n$$ to denote this), then $$\mathsf{ord}(\alpha^k)= \frac{\mathsf{ord}(\alpha)}{\gcd(\mathsf{ord}(\alpha),k)} = \frac{n}{\gcd(n,k)}.$$ Choose $$G = \text{GF}(2^{2m})^*$$ whose generator $$\alpha$$ is of order $$n = 2^{2m}-1$$, observe that $$2^{2m}-1 = (2^m-1)(2^m+1)$$, and deduce that $$\mathsf{ord}(\alpha^{2^{m}+1}) = \frac{2^{2m}-1}{\gcd(2^{2m}-1,2^{m}+1)} = \frac{(2^m-1)(2^m+1)}{2^{m}+1} = 2^m-1.$$ Thus, $$\alpha^{2^{m}+1}$$ generates the unique cyclic subgroup (of order $$2^m-1$$) of $$\text{GF}(2^{2m})^*$$ which itself is of order $$2^{2m}-1$$. Now, $$\text{GF}(2^{m})$$ is a subfield of $$\text{GF}(2^{2m})$$ and so this subgroup must be $$\text{GF}(2^{m})^*$$.

• Beautiful explanation, thanks! Could you please also explain to me why $\operatorname{GF}(2^{2m}) \to \operatorname{GF}(2^{m}): \operatorname{Tr}_m(x) = x^{2^{m}} \oplus x$ holds? – winklerrr Jun 24 '19 at 20:39
• I asked an extra question for that here – winklerrr Jun 24 '19 at 21:00
• @winklerrr That is the definition of the relative trace from $GF(2^{2m})$ to $GF(2^m)$. No other explanation is needed. – Jyrki Lahtonen Jul 12 '19 at 3:29

Hint: Remember that $$\operatorname{GF}(p^m)$$ is the splitting field of $$x^{p^m} - x$$ over $$\operatorname{GF}(p)$$. If $$m \mid n$$ so that $$\operatorname{GF}(p^n)$$ is a field extension of $$\operatorname{GF}(p^m)$$, then for $$u \in \operatorname{GF}(p^n)$$, we have $$u \in \operatorname{GF}(p^m)$$ if and only if $$u$$ is a root of $$x^{p^m} - x$$.

Can you use these to show that $$\alpha^{2^m + 1}$$ is a unit in $$\operatorname{GF}(p^k)$$ and has maximal order $$2^m - 1$$?

• Never heard of "splitting field" and I don't understand what $x^{p^m} - x$ means and what it has to do with the generator? Does it hold that $x^{p^m} = x$? So $x^{p^m} - x = 0$? But why over $\operatorname{GF}(p)$? Could you please show me why $\alpha^{2m + 1}$ is a unit in $\operatorname{GF}(p^k)$? – winklerrr Jun 22 '19 at 9:41