The $GF(2^n)$ field
First of all, let’s examine what a $GF(2^n)$ field is: it is a finite field with $2^n$ elements that is built as a field extension of $GF(2)$ using some polynomial $P(x)$ with degree $n$. It has basis $\mathcal{B} = {x^i}\big|_{0}^{n-1}$.
It also has the following properties:
- $GF(2^n)$ is a field with characteristic $2$: $\forall a \in GF(2^n)\colon\; a+a = 0$.
- From the property above follows: $\forall a \in GF(2^n)\colon\; a = -a$.
- Also, $\forall a, b \in GF(2^n)\colon\; (a+b)^2 = a^2 + b^2$ (the $2ab$ term nullifies because of characteristic $2$).
Check the existence of the solution for $x^2 + x = c$
For the equations of format $x^2 + x = c$ we have the following properties:
- For the linear operator $L(x) = x^2 + x$ we obviously have $\ker L(x) = {0,1}$ (because $L(1) = 1+1=0$ same as for $L(0)$).
- Following the rank–nullity theorem: $\dim(\text{Im}(L)) = \dim(\mathcal{B}) - \dim(\ker L)$, so $\dim(\text{Im}(L)) = n - 1$.
Let’s define a trace as a linear function $Tr\colon GF(2^n) \rightarrow GF(2)$ as follows:
\[Tr(z) = z + z^2 + z^{2^2} + \dots + z^{2^{n-1}}\]Let’s also note the following property of $Tr(z)$:
-
Following the rank–nullity theorem it has $\dim(\ker Tr(z)) = n - 1$, because $\dim(\text{Im}(Tr)) = \dim(GF(2)) = 1$:
\[\dim(\ker Tr) = \dim(\mathcal{B}) - \dim(\text{Im}(Tr)) = n - 1\]
Note that $Tr(L(x)) = 0$:
\[\begin{aligned} Tr(x^2+x) &= (x^2+x) + (x^2+x)^2 + (x^2+x)^{2^2} + \dots + (x^2+x)^{2^{n-1}} \\ (x^2+x)^{(2^k)} &= (x^{2^k})^2 + x^{2^k} \\ Tr(x^2+x) &= \sum_{k = 0}^{n-1} \Big((x^{2^k})^2 + x^{2^k}\Big) \end{aligned}\]In this sum each term $(x^{2^k})^2$ will have a pair $x^{2^{k+1}}$ that will nullify this pair sum. So, $Tr(x^2+x) = 0$.
Thus,
\[\text{Im}(L) \subseteq \{c \in GF(2^n)\colon Tr(c) = 0\}\]— the image of the linear operator $L(x)$ is a subset of the kernel of $Tr(z)$. We also already know the size of the image of $L(x)$ is exactly $n-1$, as well as the size of the kernel of $Tr(z)$. That is why:
\[\begin{gathered} \text{Im}(L) \subseteq \{c \in GF(2^n)\colon Tr(c) = 0\} \;\wedge\; \dim(\ker Tr(z)) = \dim(\text{Im}(L)) = n-1 \;\;\Leftrightarrow\\ \text{Im}(L) = \ker Tr(z) \end{gathered}\]Therefore, the equation $L(x) = c$ has a solution if and only if $Tr(c) = 0$.