0
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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})^*$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – winklerrr Jun 24 at 20:39
  • $\begingroup$ I asked an extra question for that here $\endgroup$ – winklerrr Jun 24 at 21:00
  • $\begingroup$ @winklerrr That is the definition of the relative trace from $GF(2^{2m})$ to $GF(2^m)$. No other explanation is needed. $\endgroup$ – Jyrki Lahtonen Jul 12 at 3:29
0
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – winklerrr Jun 22 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.