Encontrando el inverso de un polinomio en un campo

Question

Tengo problemas con el procedimiento para encontrar el inverso de un polinomio en un campo. Por ejemplo, toma:

En $\frac{\mathbb{Z}_3[x]}{m(x)}$, donde $m(x) = x^3 + 2x +1$, encuentra el inverso de $x^2 + 1$.

Entiendo que se necesita usar el Algoritmo (Extendido) de Euclides e Identidad de Bezout. Esto es lo que tengo actualmente:

Procediendo con el algoritmo de Euclides:

$$ x^3 + 2x + 1 =(x^2 + 1)(x) + (x + 1) \\\\ x^2 + 1 = (x + 1)(2 + x) + 2$$

Paramos aquí porque 2 es invertible en $\mathbb{Z}_3[x]$. Lo reescribimos usando una congruencia:

$$(x+1)(2+x) \equiv 2 \mod{(x^2+1)}$$

No entiendo los conceptos de alto nivel suficientemente bien y estoy perdido a partir de aquí. ¿Algún pensamiento?

Wikipedia tiene una página sobre esto con una explicación decente, pero aún no está claro en mi mente.

Nótese que esta pregunta tiene casi el mismo título, pero es a un nivel de abstracción superior. No me ayuda, ya que no entiendo los conceptos básicos.

Gracias.

Answer 1

Escribe $f := x^3+2x+1$ y $g := x^2+1$. Queremos encontrar el inverso de $g$ en el campo $\mathbb F_3[x]/(f)$ (Prefiero escribir $\mathbb F_3$ en lugar de $\mathbb Z_3$ para evitar confusiones con los enteros $3$-ádicos), es decir, estamos buscando un polinomio $h$ tal que $gh \equiv 1 \pmod f$, o equivalentemente $gh+kf=1$ para algún $k\in \mathbb F_3[x]$. El algoritmo de Euclides se puede usar para encontrar $h$ y $k: \begin{align} f &= x\cdot g+(x+1)\\ g &= (x+2)\cdot(x+1) + 2\\ (x+1) &= (2x)\cdot2 + 1 \end{align} Trabajando hacia atrás, encontramos \begin{align} 1 &= (x+1)-(2x)\cdot 2\\ &= (x+1)-(2x)(g-(x+2)(x+1))\\ &= (2x^2+x+1)(x+1)-(2x)g\\ &= (2x^2+x+1)(f-xg)-(2x)g\\ &= (2x^2+x+1)f- (x^3+2x^2)g\\ &= (2x^2+x+1)f - (2x^3+x^2)g\\ &= (2x^2+x+1)f + (x^3+2x^2)g. \end{align} Entonces, el inverso de $g$ módulo $f$ es $h = x^3+2x^2 \pmod f = 2x^2+x+2 \pmod f$.

Answer 2

Esto es muy fácil al usar la forma de matriz aumentada del algoritmo extendido de Euclides, es decir, realizamos el algoritmo de Euclides mientras seguimos la expresión de cada resto como una combinación lineal de $f$ y $g$ de la siguiente manera.

$\begin{eqnarray} (1)&& &&f = x^3\!+2x+1 &\!\!=&\, \left<\,\color{#c00}1,\,\color{#0a0}0\,\right>\quad\ \ \, {\rm i.e.}\ \qquad f\, =\ \color{#c00}1\cdot f\, +\, \color{#0a0}0\cdot g\\ (2)&& &&\qquad\ \, g =x^2\!+1 &\!\!=&\, \left<\,\color{#c00}0,\,\color{#0a0}1\,\right>\quad\ \ \,{\rm i.e.}\ \qquad g\, =\ \color{#c00}0\cdot f\, +\, \color{#0a0}1\cdot g\\ (3)&=&(1)-x(2)\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &&\qquad\qquad\ \ x+1 \,&\!\!=&\, \left<\,\color{#c00}1,\,\color{#0a0}{-x}\,\right>\ \ \ {\rm i.e.}\quad x\!+\!1\, =\, \color{#c00}1\cdot f\,\color{#0c0}{-\,x}\cdot g\\ (4)&=&(2)+(1\!-\!x)(3)\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &&\qquad\qquad\qquad\ 2 \,&\!\!=&\, \left<\,\color{#c00}{1\!-\!x},\,\color{#0a0}{1\!-\!x+x^2}\,\right>\\ \end{eqnarray}$

Por lo tanto, la línea anterior implica: $\,\ 2\, =\, (\color{#c00}{1\!-\!x})f + (\color{#0a0}{1\!-\!x\!+\!x^2})g,\, $ así que al reducir esto módulo $f$ y $3$

obtenemos en $\,\Bbb Z_3[x] \bmod f\!:\,\ {-}1\equiv 2 \equiv (\color{#0a0}{1\!-\!x\!+\!x^2})g\ \Rightarrow\ \bbox[6px,border:1px solid red]{g^{-1}\equiv\, {-}(\color{#0a0}{1\!-\!x\!+\!x^2})}$

Nota $\ $ En general, este método es más fácil de memorizar y mucho menos propenso a errores que el método alternativo de "sustitución inversa".

Esto es un caso especial de reducción de filas/columnas de Hermite/Smith de matrices a forma normal triangular/diagonal _, usando el algoritmo de división/Euclides para reducir entradas módulo pivotes. Aunque se puede entender esto conociendo solo las técnicas de eliminación de álgebra lineal análogas, será más claro cuando se estudian módulos - que, informalmente, generalizan los espacios vectoriales al permitir coeficientes de anillos vs. campos. En particular, estos resultados se estudian cuando se estudian formas normales para módulos finitamente generados sobre un PID, por ejemplo, cuando se estudian sistemas lineales de ecuaciones con coeficientes en el anillo de polinomios no-campo! polinomio anillo $\rm F[x],$ para $\rm F$ un campo, como arriba._

Answer 3

Otra forma de hacer esto es representando los elementos de tu campo cociente (un espacio vectorial tridimensional con campo base $GF(3))$ como matrices con respecto a la base $1, x, x^2$. La multiplicación por $x$ envía $1$ a $x$, $x$ a $x^2$ y $x^2$ a $x^3 = -2x - 1 = x + 2 \bmod 3$. Así que (la multiplicación por) $x$ se representa por la siguiente matriz $m$:

\begin{pmatrix} 0 & 0 & 2 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}

$m^0$ (correspondiente a la multiplicación por $x^0 = 1$) es la matriz identidad:

\begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}

y $m^2$ (multiplicación por $x^2$) es igual a:

\begin{pmatrix} 0 & 2 & 0 \\ 0 & 1 & 2 \\ 1 & 0 & 1 \end{pmatrix}

El elemento $(x^2 + 1)^{-1}$ está representado por $(m^2 + m^0)^{-1}$, que es igual a

\begin{pmatrix} 2 & 1 & 2 \\ 1 & 1 & 2 \\ 2 & 1 & 1 \end{pmatrix}

Los coeficientes de $(x^2 + 1)^{-1}$ se pueden leer de la primera columna de esta matriz: $(m^2 + m^0)^{-1}$ = $2m^0 + m + 2m^2$, entonces $(x^2 + 1)^{-1} = 2 + x + 2x^2$. En resumen: tu problema puede ser resuelto sumando, multiplicando e invirtiendo matrices.

Answer 4

El algoritmo euclidiano comienza con dos polinomios $r^{(0)}(x)$ y $r^{(1)}(x)$ tales que $\deg r^{(0)}(x) > \deg r^{(1)}(x)$ y luego encuentra de forma iterativa polinomios cociente $q^{(1)}(x), q^{(2)}(x), \ldots$ y polinomios residuo $r^{(2)}(x), r^{(3)}(x), \ldots$ de grados sucesivamente menores mediante la división $$\begin{align*} r^{(0)}(x) &= q^{(1)}(x)\cdot r^{(1)}(x) + r^{(2)}(x)\\ r^{(1)}(x) &= q^{(2)}(x)\cdot r^{(2)}(x) + r^{(3)}(x)\\ \vdots\qquad &= \qquad\qquad\vdots \end{align*}$$ Una versión del Algoritmo Euclidiano Extendido también encuentra pares de polinomios $(s^{(0)}(x),t^{(0)}(x)), (s^{(1)}(x),t^{(1)}(x)), (s^{(2)}(x),t^{(2)}(x)) \ldots$ donde $(s^{(0)}(x),t^{(0)}(x)) = (1,0)$ y $(s^{(1)}(x),t^{(1)}(x)) = (0,1)$ que satisfacen la identidad de Bezout generalizada $$s^{(i)}(x)\cdot r^{(0)}(x) + t^{(i)}(x)\cdot r^{(1)}(x) = r^{(i)}(x).$$

Estos polinomios satisfacen la misma recursión que los polinomios residuo, es decir, $$\begin{align*} r^{(i+1)}(x) &= r^{(i-1)}(x) - q^{(i)}(x)\cdot r^{(i)}(x)\\ s^{(i+1)}(x) &= s^{(i-1)}(x) - q^{(i)}(x)\cdot s^{(i)}(x)\\ t^{(i+1)}(x) &= t^{(i-1)}(x) - q^{(i)}(x)\cdot t^{(i)}(x)\\ \end{align*}$$

Esta forma del algoritmo euclidiano extendido es útil en aplicaciones prácticas ya que solo es necesario recordar dos polinomios $r, s,$ y $t$ con cada nuevo polinomio $(i+1)$-ésimo reemplazando al polinomio $(i-1)$-ésimo que ya no se necesita.

En tu caso, tienes $r^{(0)}(x) = x^3 + 2x+1$ y $r^{(1)}(x) = x^2 + 1$. Ya has calculado la secuencia de cociente y residuo terminando con $r^{(3)}(x) = 2$. Ahora calcula $t^{(2)}(x)$ y $t^{(3)}(x)$ de forma iterativa usando la secuencia de polinomios cociente y escribe $$\begin{align*} s^{(3)}(x)\cdot (x^3 + 2x + 1) + t^{(3)}(x)\cdot(x^2 + 1) &= 2\\ -s^{(3)}(x)\cdot (x^3 + 2x + 1) - t^{(3)}(x)\cdot(x^2 + 1) &= 1\\ (-t^{(3)}(x))\cdot (x^2 + 1) &= 1 ~ \mod (x^3 + 2x + 1) \end{align*}$$ y deduce que el inverso multiplicativo de $x^2 + 1$ en $\mathbb Z_3[x]/(x^3 + 2x + 1)$ es $-t^{(3)}(x)$. Nota que la secuencia $s^{(i)}(x)$ no necesita ser calculada en absoluto si todo lo que uno necesita es el inverso.

Answer 5

El mismo algoritmo utilizado para resolver la ecuación diofántica lineal se puede utilizar aquí. $$ \begin{array}{c} &&x&x-1&(x+1)/2\\ \hline 1&0&1&1-x&(x^2+1)/2\\ 0&1&-x&x^2-x+1&-(x^3+2x+1)/2\\ x^3+2x+1&x^2+1&x+1&2&0 \end{array} $$ Por lo tanto, $$ (1-x)(x^3+2x+1)+(x^2-x+1)(x^2+1)=2 $$ Así, el inverso de $x^2+1$ es $\tfrac12(x^2-x+1)$ módulo $x^3+2x+1$.