# Explanation of trace function $\operatorname{Tr}_m(x) = x^{2^{m}} \oplus x$

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

For all $$x \in \operatorname{GF}(2^{n})$$, it holds that $$x^{2^{n}} \oplus x = 0$$.
If $$n= 2m$$ then we define the trace from $$\operatorname{GF}(2^{2m}) \to \operatorname{GF}(2^{m})$$ as the function $$\operatorname{Tr}_m(x) = x^{2^{m}} \oplus x$$.

I don't understand why this works for all $$x \in \operatorname{GF}(2^{2m})$$. Why is it safe to say that this operation ends in the subfield $$\operatorname{GF}(2^{m})$$?

• @Aleph could you explain that further please? – winklerrr Jun 24 '19 at 21:07
• This isn't a question about cryptography. Anyway, the answer is because $(x^{2^m} + x)^{2^m} = x^{2^m} + x$ for $x \in \mathbb{F}_{2^{2m}}$. I'd recommend reading some introductory lecture notes/book on (finite) fields though. – Aleph Jun 24 '19 at 21:10
• Because $x^{2^{2m}} = x$ in $\mathbb{F}_{2^{2m}}$. The proper explanation would be that the Galois group of $\mathbb{F}_{2^{2m}} / \mathbb{F}_{2^{m}}$ consists of the identity map and $x \mapsto x^{2^m}$... – Aleph Jun 24 '19 at 21:12

All elements of $$\text{GF}(q)$$ are roots of $$x^q-x$$. In fact, this is a litmus test for determining membership in $$\text{GF}(q)$$: when working in an extension field of $$\text{GF}(q)$$, say $$\text{GF}(q^m)$$, we can determine whether an $$\alpha$$ is a member of $$\text{GF}(q)$$ by computing $$\alpha^q$$ and checking whether the result equals $$\alpha$$ or not.
So, in $$\text{GF}(2^n)$$, $$\alpha^{2^n} - \alpha = 0$$, and if we remember that addition and subtraction are the same operation in fields of characteristic $$2$$ and that this operation is often denoted by $$\oplus$$, we have that $$x^{2^n}\oplus x = 0$$.
The trace function from $$\text{GF}(q^k)$$ to $$\text{GF}(q)$$ is defined as $$\operatorname{Tr}(x) = x + x^q + x^{q^2} + \cdots + x^{q^{k-1}}.$$ Verify that for all $$x \in \text{GF}(q^k)$$, $$\operatorname{Tr}(x)$$ belongs to $$\text{GF}(q)$$. (Hint: apply the litmus test). So for the special case when $$k=2$$, the trace function from $$\text{GF}(q^2)$$ to $$\text{GF}(q)$$ is just $$\operatorname{Tr}(x) = x + x^q$$. I will leave it to the OP see what happens when $$q$$ equals $$2^m$$ and whether the statements of the S-Box book are true or not.