¿Cada polinomio sobre un campo finito tiene una raíz cuadrada modulo un polinomio irreducible?

Question

¿Dado un polinomio $p \in \operatorname{GF}(2^m)[x]$ y un % polinomio irreducible $g \in GF(2^m)[x]$, existe un $d \in \operatorname{GF}(2^m)[x]$ tal que $d^2(x) = p \pmod{g(x)}$?

En otras palabras, ¿cada polinomio $p$ sobre un campo finito con $2^m$ elementos tiene una raíz cuadrada de $d$ modulo un % polinomio irreducible $g$?

Estoy tratando de entender el algoritmo de Patterson para la corrección de errores en códigos de Goppa binario irreducibles, y mayoría de los papeles parece asumir que tal polinomio existe siempre, pero no puedo encontrar una prueba en cualquier lugar.

Answer 1

El cociente $K = \operatorname{GF}(2^m)[x]/(g)$ es de nuevo un campo finito de característica $2$. El mapa $$ f \colon K \a K, \quad y \mapsto y^2 $$ es aditivo, porque $$ 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). $$ Tenemos que $\ker(f) = 0$, lo $f$ es inyectiva, y debido a $K$ es finito, por tanto, también surjective. (El mapa de $f$ es en realidad un campo de automorphism, el llamado Frobenius homomorphism.) Por $\overline{p} \in K$ que existe cierta $\overline{q} \in K$$\overline{q}^2 = \overline{p}$, lo que significa que para los polinomios $p, q \in \operatorname{GF}(2^m)[x]$ tenemos que $q^2 \equiv p \pmod{g}$.

---

PS: Como fue señalado por Ravi Fernando en los comentarios, uno puede ser más explícito: Para $n \geq 1$ $K \cong \operatorname{GF}(2^n)$ (es decir,$n = m \cdot \deg(g)$) tenemos que $y^{2^n} = y$ todos los $y \in K$. (Esto está claro para $y = 0$, y para $y \neq 0$ tenemos que $y \in K^\times$, que es un grupo de orden $2^n - 1$, que es la razón por la $y^{2^n - 1} = 1$.) De ello se desprende que $y = y^{2^n} = (y^{2^{n-1}})^2$ por cada $y \in K$.