12
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ Jan 22, 2017 at 12:19
  • 7
    $\begingroup$ @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. $\endgroup$ Jan 22, 2017 at 12:27
  • $\begingroup$ @GerryMyerson Yes, you got it. $\endgroup$ Jan 22, 2017 at 13:05

2 Answers 2

10
$\begingroup$

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

$\endgroup$
1
  • 5
    $\begingroup$ 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$. $\endgroup$
    – Rhys
    May 26, 2021 at 22:43
3
$\begingroup$

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$.
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – amWhy
    Mar 9 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.