# Quadratic equation of characteristic $2$

We know it is easy to decide whether a quadratic equation has a root in a field which has characteristic $$\neq$$ 2. It is equivalent to judge whether there exists an element whose square is a specific number (cancel the linear term).

But this method doesn't work for the case of characteristic $$2$$. Is there any idea to solve this case?

• Why does it not work? A quadratic polynomial, say, $x^2+ax+b$ has no root over $K$ if and only if it irreducible. Also in characteristic $2$. Jan 22, 2017 at 12:19
• @Dietrich, maybe the point of the question is that in other characteristics you just have to check whether $a^2-4b$ is a square, but this breaks down in characteristic 2. Jan 22, 2017 at 12:27
• @GerryMyerson Yes, you got it. Jan 22, 2017 at 13:05

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

• It's worth pointing out that in a finite field of characteristic 2, every element is a square (so $x^2 + b = 0$ always has a solution). Just note that in GF($2^k$), we have $b = b^{2^k} = (b^{2^{k-1}})^2$.
– Rhys
May 26, 2021 at 22:43

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$$.
• I miss you. I know you keep busy. I am commenting only to ask if you would undelete your answer here. You've got a talent for describing issues in a non-binary way (meaning: not "hard-ass", because that doesn't facilitate learning, but also not doing work for students, without their contributing, participating in the process. Anyway, the choice is yours, of course. I just know you to offer well-reasoned posts, food for thought, in non-offensive words. Stop by the Cafe sometime soon, if you're up to it! Mar 9 at 22:17