15
$\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$
2
  • $\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

2 Answers 2

15
$\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$
7
  • 7
    $\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
  • $\begingroup$ How is $R(c)$ actually got? I don't own a copy of David Cox's book, and couldn't easily find anything about this 2-root on Google. Is this operation known by another name? $\endgroup$ Nov 30, 2022 at 16:59
  • $\begingroup$ This answer seems to state that for $a\ne 0$, the polynomial $x^2+ax+b$ is always irreducible, which is false right? $\endgroup$ Jun 14, 2023 at 7:31
  • $\begingroup$ @JamesTheAwesomeDude If $x^2+x+c$ is irreducible you get $R(c)$ the same way you get $\sqrt{-1}$ in the real number field--by defining it into existence. If it's reducible, a brute-force approach would be to consult the multiplication table, looking for an element $x$ such that $x(x+1)=c$. For something more efficient, studying Jyrki Lahtonen's answer may be helpful. The final bullet point, in particular, seems to address this question. $\endgroup$ Aug 27, 2023 at 16:10
  • $\begingroup$ @stupid_question_bot I'm not sure what makes you say that this answer is asserting that. You are correct that $x^2+ax+b$ is not always irreducible. Simply choose distinct elements $c$, $d$ in the base field and multiply out $(x+c)(x+d)$. You'll get a quadratic polynomial with nonzero coefficient of $x$ that factorizes over the base field. $\endgroup$ Aug 27, 2023 at 16:12
8
$\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, 2022 at 22:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .