Solving quadratic equations in $GF(2^n)$ (Part 1)

 

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