6
$\begingroup$

Given a polynomial $p \in \operatorname{GF}(2^m)[x]$ and an irreducible polynomial $g \in GF(2^m)[x]$, is there a $d \in \operatorname{GF}(2^m)[x]$ such that $d^2(x) = p \pmod{g(x)}$?

In other words, does every polynomial $p$ over a finite field with $2^m$ elements have a square root $d$ modulo an irreducible polynomial $g$?

I am trying to understand Patterson's algorithm for error correction in irreducible binary Goppa codes, and most papers seem to assume that such a polynomial always exists, but I cannot find a proof anywhere.

$\endgroup$

1 Answer 1

Reset to default
12
$\begingroup$

The quotient $K = \operatorname{GF}(2^m)[x]/(g)$ is again a finite field of characteristic $2$. The map $$ f \colon K \to K, \quad y \mapsto y^2 $$ is additive because $$ f(y_1 + y_2) = (y_1 + y_2)^2 = y_1^2 + 2y_1y_2 + y_2^2 = y_1^2 + y_2^2 = f(y_1) + f(y_2). $$ We have that $\ker(f) = 0$, so $f$ is injective, and because $K$ is finite therefore also surjective. (The map $f$ is actually a field automorphism, the so called Frobenius homomorphism.) It follows for $\overline{p} \in K$ that there exists some $\overline{q} \in K$ with $\overline{q}^2 = \overline{p}$, which means that for the polynomials $p, q \in \operatorname{GF}(2^m)[x]$ we have that $q^2 \equiv p \pmod{g}$.

PS: As was pointed out by Ravi Fernando in the comments, one can be more explicit: For $n \geq 1$ with $K \cong \operatorname{GF}(2^n)$ (namely $n = m \cdot \deg(g)$) we have that $y^{2^n} = y$ for all $y \in K$. (This is clear for $y = 0$, and for $y \neq 0$ we have that $y \in K^\times$, which is a group of order $2^n - 1$, which is why $y^{2^n - 1} = 1$.) It follows that $y = y^{2^n} = (y^{2^{n-1}})^2$ for every $y \in K$.

$\endgroup$
4
  • 1
    $\begingroup$ And explicitly, if $K$ is the field with $2^n$ elements ($n = m \cdot \mathrm{deg}(g)$), then we have $(x^{2^{n-1}})^2 = x^{2^n} = x$ for all $x \in K$. $\endgroup$
    – Ravi Fernando
    Commented Jun 10, 2018 at 17:43
  • $\begingroup$ Great, thank you! $\endgroup$
    – J. Doe
    Commented Jun 10, 2018 at 18:11
  • 1
    $\begingroup$ Perhaps it might help to explain why the map $f$ is injective. If $y,z \in K$ and $f(y)=f(z)$, then $y^2=z^2$, i.e. $y^2-z^2 = (y-z)^2 = 0$. Then letting $u=y-z$, we have $u \in K$ such that $u^2 = 0$. In a finite field, that implies $u=0$, i.e., $y=z$. $\endgroup$
    – D.W.
    Commented Jun 10, 2018 at 20:16
  • $\begingroup$ Thanks for the feedback, I incorporated it into the answer. $\endgroup$
    – Jendrik Stelzner
    Commented Jun 10, 2018 at 20:44

You must log in to answer this question.

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