quadratic equation of characteristic 2

Solution 1:

The quadratic equation $x^2+ax+b$ in the case of characteristic 2 takes two forms depending on whether or not $a=0$. When $a=0$, it's clear if $b$ is not a square there is no solution over the ground field, and the quadratic factors as $(x+\sqrt{b})^2$ over an extension of the ground field generated by attaching $\sqrt{b}$.

When $a\neq0$ we can show that the irreducible quadratic $x^2+ax+b$ cannot have a solution $\alpha = u+v\sqrt{w}$ with $u,v,$ and $w$ in the ground field. Suppose it did, then $$ \begin{align} 0 &= (u+v\sqrt{w})^2 + a (u+v\sqrt{w}) + b \\ 0 &= u^2+wv^2+au + v\sqrt{w}+b \\ v\sqrt{w} &= u^2+wv^2+au+b \end{align} $$ which is impossible, since $\sqrt{w}$ cannot be in the ground field.

While a solution using radical extensions is impossible, the case $a\neq 0$ can be reduced to considering equations of the form $x^2+x+c$. David Cox in his book Galois Theory calls a root of this equation a $2$-root of $c$ and denotes it $R(c)$. It's easy to check that $R(c)+1$ also satisfies the equation, so we now have two $2$-roots of $c$. The "quadratic formula" for characteristic 2 becomes $$ x= aR(b/a^2), a(R(b/a^2)+1) \text { provided }\, a\neq 0 $$

Solution 2:

The point of this post is to give a bit more precise description of the criteria listed in Sharding4's great answer in the case of finite fields of characteristic two. I thought I had explained this already somewhere on the site but cannot find it now, the closest match is here, but there the focus is very different.

Let $F=\Bbb{F}_{2^m}$, aka $GF(2^m)$, be the field of cardinality $2^m$. We have the so called (absolute) trace $T:F\to\Bbb{F}_2$ given by the sum of the Galois conjugates (= powers of the Frobenius): $$ T(x)=x+x^2+x^4+x^8+\cdots+x^{2^{m-1}}. $$

1. Because $T(x)^2=T(x)$ we always have $T(x)\in\Bbb{F}_2$ as claimed.
2. $T$ is an additive homomorphism, $T(x+y)=T(x)+T(y)$ because the powers of Frobenius are.
3. We trivially also have $T(x^2)=T(x)$, because we can square $T(x)$ term-by-term, and the square of the last term is $(x^{2^{m-1}})^2=x^{2^m}=x$ for all $x\in F$.
4. The mapping $L:F\to F, x\mapsto x+x^2$ is also an additive homomorphism, and its kernel clearly equals $\mathrm{Ker}(L)=\{0,1\}$. It follows that $\mathrm{Im}(L)$ has $2^{m-1}$ elements.
5. By items 2 and 3 it follows that $\mathrm{Im}(L)\subseteq\mathrm{Ker}(T)$. Because $T$ is a polynomial of degree $2^{m-1}$, it cannot have more than $2^{m-1}$ zeros in $F$. Therefore we must have equality: $$ \mathrm{Im}(L)=\mathrm{Ker}(T).$$

Let us then look at the solutions of the equation $$ x^2+ax+b=0\qquad(*) $$ with $a,b\in F$.

If $a=0$, we have $x^2=b$, and this has a double root $x=\sqrt b=b^{2^{m-1}}$ that always exists in a finite field of characteristic two.

If $a\neq0$ then we introduce the new variable $y=x/a$ and rewrite $(*)$ divided by $a^2$ to read $$ y^2+y=c\qquad(**) $$ with $c=b/a^2$.

By item 5. $(**)$ has two solutions $y\in F$ if $T(c)=0$ and no solutions in $F$ when $T(c)=1$. This is standard from all the text books covering finite field characteristic two arithmetic. If $y$ is one solution then $y+1$ is the other, either by Vieta relations or by linearity of the Frobenius, really, we are looking for a coset of $\mathrm{Ker}(L)$.

A less well known trick of the trade for finding one of the solutions is to use the so called half-trace. It is a function $H:\mathrm{Ker}(T)\to F$ with the property that $$ H(y)+H(y)^2=y $$ for all $y\in\mathrm{Ker}(T)$. This is by no means a unique function, but we can make the following observations.

• If $m=2k+1$ is odd, we can use $$H(y)=y^2+y^8+\cdots+y^{2^{m-2}}$$ because then $H(y)^2=y^4+y^{16}+\cdots+y^{2^{m-1}}$. Therefore $$H(y)+H(y)^2=\sum_{j=1}^{m-1}y^{2^j}=y+T(y)=y$$ as we are assuming that $T(y)=0$. So here roughly one half of the terms of the trace $T(y)$ appear in $H(y)$ — hence the name half-trace. See also here.
• When $m\equiv2\pmod4$ there is a similar explicit formula for the half trace as an $\Bbb{F}_4$ linear combination of the powers of the Frobenius. This time the coefficients are third roots of unity — they are each others squares and their sum $=1$, and that makes it tick.
• If we use a normal basis $b_i=b_0^{2^i}, i=0,1,\ldots,m-1$, $b_0$ a carefully chosen element of $F$ to store an element $x=\Bbb{F}_{2^m}$ by saving its coordinates $a_i\Bbb{F}_2$ w.r.t. to the normal basis, that is $x=\sum_ia_ib_i$. Then we know that $T(x)=\sum_ia_i=0$, and (one of the points of using normal bases), $x^2=\sum_ia_ib_{i+1\bmod m}$ - the coordinates of $x^2$ are gotten by cyclically shifting those of $x$. So if $x\in\mathrm{Ker}{T}$ then there is an even number of $1$s among the coordinates. It follows that we can solve the system $c_{m-1}=0=c_{-1}$, $c_{j-1}+c_j=a_j$, $j=0,1,\ldots,m-2$, whence $H(x)=\sum_i c_ib_i$ works. This is useful for large $m$, when normal bases are a common option.
• If we need to solve a large number of quadratic equations over the same field $F$, we can build a useful look-up-table. Let $\{x_1,x_2,\ldots,x_{m-1}\}$ be a basis of $\mathrm{Ker}(T)$ over the prime field. Using linearity of $L$ we can easily build a table of elements $y_1,\ldots,y_{m-1}$ such that $L(y_i)=x_i$. It follows that with $c=\sum_i a_ix_i$ we can then use $H(c)=\sum_ia_iy_i$.