¿Cómo puedo demostrar la irreducibilidad de un polinomio sobre un campo finito?

Question

Quiero demostrar lo que $x^{10} +x^3+1$ es irreducible sobre un campo $\mathbb F_{2}$ y $x^5$ + $x^4 +x^3 + x^2 +x -1$ es reducible sobre $\mathbb F_{3}$ .

Por lo que sé, los criterios de Eisenstein no ayudarán aquí. He oído hablar de un criterio de irreductibilidad que suena como

"Si $f(x)$ divide $x^{p^n-1}-1$ (donde $n=\deg(f))$ , $p$ es de $\mathbb F_{p}$ entonces $f(x)$ es irreductible".

Pero no sé cómo mostrar si $f(x)$ puede ser dividido por esto o no.

Answer 1

La prueba en la que estás pensando es La prueba de irreducibilidad de Rabin que se puede enunciar de la siguiente manera.

Dejemos que $f(x)$ sea un polinomio de grado $n$ en $\mathbb{F}_p$ . Entonces $f$ es irreducible sobre $\mathbb{F}_p$ si y sólo si

• $f(x)$ divide $x^{p^n}-x$ y

• $\mathrm{gcd}\bigl(f(x),x^{p^{n/q}}-x\bigr)=1$ para cada divisor primo $q$ de $n$ .

Para $f(x) = x^{10}+x^3+1 \in \mathbb{F}_2[x]$ debemos comprobar que $f(x)$ divide $x^{2^{10}}-x = x^{1024}-x$ y que es relativamente primo con $x^{32}-x$ y $x^4-x$ .

Para $f(x) = x^5 + x^4+x^3+x^2+x-1 \in\mathbb{F}_3[x]$ debemos comprobar que $f(x)$ divide $x^{243}-x$ y que es relativamente primo con $x^3-x$ .

Todo esto es fácil de hacer en un ordenador. En Mathematica El PolynomialExtendedGCD puede comprobar el GCD de un polinomio módulo cualquier primo.

In[1] := PolynomialExtendedGCD[x^10 + x^3 + 1, x^1024 - x, x, Modulus -> 2][[1]]

Out[1] := 1 + x^3 + x^10

In[2] := PolynomialExtendedGCD[x^10 + x^3 + 1, x^32 - x, x, Modulus -> 2][[1]]

Out[2] := 1

In[3] := PolynomialExtendedGCD[x^10 + x^3 + 1, x^4 - x, x, Modulus -> 2][[1]]

Out[3] := 1

Esto establece que $x^{10}+x^3+1$ es irreducible sobre $\mathbb{F}_2$ . Para el otro polinomio, podemos probar:

In[1] := PolynomialExtendedGCD[x^5+x^4+x^3+x^2+x-1, x^243 - x, x, Modulus -> 3][[1]]

Out[1] := 1

Como puede ver, el GCD es $1$ por lo que no se divide. De hecho, $$ x^5+x^4+x^3+x^2+x-1 \;=\; \bigl(x^2-x-1\bigr)\bigl(x^3-x^2+x+1\bigr) $$ en $\mathbb{F}_3$ , por lo que el segundo polinomio no es irreducible.

Editar: Como señalan Jyrki Lahtonen y Alex M., siempre se puede utilizar Mathematica directamente para comprobar si un polinomio es irreducible, por lo que no hay una razón práctica para utilizar la prueba de Rabin en Mathematica para estos dos polinomios. Además, si se tiene acceso a un ordenador, en principio siempre se puede comprobar si un polinomio es irreducible simplemente enumerando todos los factores posibles y luego intentando dividir por cada factor. Si no tienes acceso a un ordenador, los métodos sugeridos en sus respuestas son ciertamente mejores que hacer el método de Rabin a mano.

Sin embargo, la prueba de Rabin es importante desde el punto de vista algorítmico como una posible forma de comprobar la irreducibilidad. De hecho, para polinomios de alto grado, la prueba de Rabin supera claramente la división de prueba por todos los factores posibles, aunque hay otros algoritmos de la competencia . Los dos problemas dados son lo suficientemente sencillos como para que casi cualquier algoritmo que se utilice en un ordenador dé los resultados deseados muy rápidamente, pero sigue siendo instructivo ver cómo se puede aplicar la prueba de Rabin a estos ejemplos.

Answer 2

Ninguno de los dos polinomios tiene ceros en el respectivo campo primo, por lo que tampoco tienen factores lineales.

Comprobemos el primer polinomio $p(x)=x^{10}+x^3+1\in\Bbb{F}_2[x]$ . La afirmación es que es irreductible. Una forma más eficiente de utilizar el resultado citado es observar que si $p(x)$ fuera un producto de dos o más factores irreducibles al menos uno de esos factores tendría grado $\le5$ . Eliminamos estas posibilidades una por una. Comprobar la presencia de factores de mayor grado se vuelve progresivamente un poco más difícil a medida que el grado sube, pero el principio es siempre el mismo, y este resultado nos da una herramienta.

¿Podría tener un factor cuadrático irreducible? Por el resultado citado todos los polinomios cuadráticos irreducibles son factores de $p_2(x):=x^{2^2-1}-1=x^3+1$ . Para eliminar la posibilidad de $p(x)$ que tiene un factor cuadrático, basta con demostrar que $\gcd(p(x),p_2(x))=1$ . Porque $p(x)-p_2(x)=x^{10}$ cualquier factor común que tengan es también un factor de $x^{10}$ pero el único factor irreducible de $x^{10}$ es $x$ Así que hemos superado este obstáculo.

Para eliminar la posibilidad de $p(x)$ que tiene un factor cúbico, también basta con comprobar que $\gcd(p(x),p_3(x))=1$ , donde $p_3(x)=x^{2^3-1}-1=x^7+1$ . Aquí vemos (el primer paso para calcular este gcd por el algoritmo de Euclides) que $$ p(x)-x^3p_3(x)=1, $$ así que tampoco hay factores comunes ahí.

Para eliminar la posibilidad de un factor cuaternario de $p(x)$ necesitamos calcular $\gcd(p(x),p_4(x))$ con $p_4(x)=x^{2^4-1}-1=x^{15}+1.$ Vamos a ejecutar Euclides: $$ \begin{aligned} p_4(x)-x^5p(x)&=x^8+x^5+1=: r_1(x)\\ p(x)-x^2r_1(x)&=x^7+x^3+x^2+1=:r_2(x). \end{aligned} $$ Aquí podríamos seguir con Euclides, pero también podemos ahorrarnos un paso o dos factorizando el resto siempre que podamos hacerlo fácilmente. Aquí $$ r_2(x)=x^3(x^4+1)+(x^2+1)=x^3(x^2+1)^2+(x^2+1)=(x^2+1)(x^5+x^3+1). $$ Sabemos por los pasos anteriores que $p(x)$ no es divisible por $(x+1)$ . Porque $(x^2+1)=(x+1)^2$ podemos descartar ese factor como posibilidad, y continuar con Euclides con $\gcd(r_1(x), r_3(x))$ donde $r_3(x)=x^5+x^3+1$ . Vemos que $$ \begin{aligned} r_1(x)-x^3r_3(x)&=x^6+x^5+x^3+1=(x+1)(x^5+x^2+x+1)\\ &=(x+1)^2(x^4+x^3+x^2+1)=(x+1)^3(x^3+x+1). \end{aligned} $$ Aquí he utilizado ampliamente el truco (basado en sumas geométricas) de que siempre que $0<a<b$ tenemos $$ \frac{x^a+x^b}{x+1}=x^a+x^{a+1}+x^{a+2}+\cdots+x^{b-1}. $$ De todos modos, el cálculo anterior muestra que cualquier factor común eventual de $p(x)$ y $p_4(x)$ también es un factor del cúbico $x^3+x+1$ pero ya hemos demostrado que $p(x)$ no tiene factores cúbicos. Por lo tanto, también hemos terminado con este caso.

El último paso para demostrar que $p(x)$ ya que ningún factor quíntico necesita otra carrera de Euclides. Esta vez comprobando que $\gcd(p(x),p_5(x))=1$ , donde $p_5(x)=x^{31}+1$ . Para empezar utilizamos cuadrar y multiplicar . Ya hemos calculado en el paso anterior que $$ x^{15}\equiv x^8+x^5\pmod{p(x)}.\qquad(*) $$ En consecuencia, $x^{16}\equiv x^9+x^6\pmod{p(x)}$ . Cuadrando $(*)$ (El sueño del novato simplifica la cuadratura en la característica dos) da $$ x^{30}\equiv x^{16}+x^{10}\equiv (x^9+x^6)+x^{10}\pmod{p(x)}. $$ Aquí $$ x^{10}+x^9+x^6-p(x)=x^9+x^6+x^3+1. $$ Por lo tanto (multiplicar por $x$ ) $$ x^{31}\equiv x^{10}+x^7+x^4+x\equiv x^7+x^4+x^3+x+1\pmod{p(x)}. $$ Así que sabemos que el resto de $p_5(x)$ modulo $p(x)$ . Por lo tanto, la tarea restante es comprobar que $$ \gcd(p(x),x^7+x^4+x^3+x)=1. $$ Eso te lo dejamos a ti :-)

Su otro polinomio $$ q(x)=x^5+x^4+x^3+x^2+x-1\in\Bbb{F}_3(x) $$ es quíntica. Así que si es reducible, debe tener un factor que sea lineal o cuadrático. Eliminamos la posibilidad de factores lineales comprobando que no tiene ceros. Usando la técnica anterior encontramos eventuales factores cuadráticos calculando $$ \gcd(q(x),q_2(x))\in\Bbb{F}_3[x]. $$ Aquí $q_2(x)=x^{3^2-1}-1=x^8-1$ . Dejando a su cargo la ejecución de esta instancia de Euclides, y encontrar el factor cuadrático.

Answer 3

Creo que el criterio al que aludes es el siguiente:

Supongamos que $X^p - a$ no tiene raíces en $\Bbb F _{p^n}$ . Entonces $X^{p^m} - a$ es irreducible en $\Bbb F _{p^n}[X]$ $\forall m \ge 1$ .

En cualquier caso, no se puede utilizar aquí.

1) Veamos cómo demostrar que el segundo polinomio (llamémoslo $P$ ) es reducible. En primer lugar, ninguna de $0, 1, 2$ es una raíz, por lo que $P$ no tiene ningún factor de grado $1$ (y, por tanto, ningún factor de grado $4$ ). Veamos si $P$ puede escribirse como un producto de dos polinomios, de grado $2$ y, respectivamente, $3$ . El método largo consiste en multiplicar los polinomios $aX^2 + bX + c$ y $eX^3 + fX^2 + gX + h$ , igualar los coeficientes de potencias iguales, etc...

Una aproximación más corta es la siguiente: enumeremos todos los polinomios de grado $2$ y comprobar si se dividen $P$ . Desde $P$ no tiene ningún factor lineal, basta con enumerar sólo los polinomios de grado $2$ que son irreductibles. Nótese que ningún polinomio de este tipo puede terminar en $0$ por lo que el término constante es $1$ o $2$ . En cuanto al coeficiente principal, basta con considerar sólo los polinomios mónicos. Hasta aquí obtenemos los polinomios $X^2 + aX + 1$ , $X^2 + aX +2$ . Un polinomio de grado $2$ es irreducible si no tiene raíces, es decir, si su discriminante no es un cuadrado perfecto. Como los únicos cuadrados perfectos en $\Bbb F _3$ son $0$ y $1$ , usted quiere $a$ tal que el discriminante debe ser $2$ .

En el primer caso, el discriminante es $a^2 - 4$ , por lo que quiere $a$ tal que $a^2 - 4 = 2$ Así que $a=0$ .

En el segundo caso, el discriminante es $a^2 - 8$ , por lo que quiere $a$ tal que $a^2 - 8 = 2$ es decir $a^2 = 1$ es decir $a=1$ o $a=2$ .

Así, los únicos polinomios irreducibles mónicos de grado $2$ son $X^2 + 1$ , $X^2 + X + 2$ , $X^2 + 2X +2$ . Veamos cuál divide nuestro polinomio.

Tenga en cuenta que $P = X^3 (X^2+1) + X^2 (X^2+1) + X-1$ , por lo que al dividir $P$ por $X^2 +1$ usted obtiene el resto $X-1$ Así que $X^2-1 \not| P$ .

Por último, trate de dividir $P$ por los dos últimos polinomios. $X^2 + 2X +2$ resultará ser un factor.

2) En cuanto al primer polinomio (llámese $Q$ ), el enfoque será similar. En primer lugar, hay que tener en cuenta que no tiene raíces, por lo que no tiene ningún factor lineal. Por lo tanto, vamos a buscar sólo factores irreducibles de grado $2, \dots, 5$ . Para ser irreducibles, estos factores potenciales deben tener el término constante $1$ .

Buscando polinomios irreducibles de grado $2$ , estos deben parecer $X^2 +aX +1$ . Claramente, $a=1$ da el único irreducible.

Para el grado $3$ , quieres esos polinomios $X^3 + aX^2 + bX +1$ que no tienen ningún factor lineal; ya que $0$ no puede ser una raíz, tampoco quiere $1$ que sea así, por lo tanto quiere $1+a+b+1 \ne 0$ , lo que significa que $a+b =1$ Así que las únicas posibilidades son $X^3 + X^2 +1$ y $X^3 +X+1$ .

En grado $4$ , quieres esos polinomios $X^4 + aX^3 + bX^2 + cX +1$ que no tienen raíces (por lo que $1+a+b+c+1 \ne 0$ es decir $a+b+c=1$ ) y que no tienen ningún factor irreducible de grado $2$ es decir, que no están divididos por $X^2+X+1$ (encontrado arriba). Un factor reducible de grado $4$ al no tener raíz tendría que ser $(X^2+X+1)^2 = X^4 + X^2 +1$ . Por lo tanto, los únicos polinomios irreducibles de grado $4$ permanezca en $X^4 + X^3 +1$ , $X^4+ X+1$ y $X^4+ X^3 + X^2 + X + 1$ .

Finalmente, los polinomios reducibles $x^5 + aX^4 + bX^3 +cX^2 + dX +1$ de grado $5$ son los que tienen raíces (es decir $a+b+c+d=0$ ) y los que se pueden dividir por $X^2+1$ . Realización de la división larga por $X^2+1$ , se obtiene el resto $(b+d+1)x + (a+c+1)$ por lo que para obtener los polinomios reducibles se impone $a+b+c+d = 0, \; b+d+1 = 0, \; a+c+1 = 0$ . Resuelve este sistema (tendrá varias soluciones); los polinomios que no están entre estas soluciones son los irreducibles de grado $5$ .

Ahora que has enumerado todos los polinomios irreducibles de grado $\le 5$ comprobar (realizando la división larga o calculando el máximo común divisor) cuáles dividen $Q$ . Ninguno lo hará, así que $Q$ es irreducible.

---

A continuación, la prueba del criterio de irreductibilidad mencionado al principio de mi post.

Observe que $X^{p^m} - a$ tiene al menos una raíz $x$ en algún cierre algebraico $K$ de $\mathrm F_{p^m}$ ; si $y \in K$ es otra raíz, se deduce que $x^{p^m} = y^{p^m}$ y, como $r \mapsto r^{p^m}$ es un automorfismo de $K$ (porque el mapa de Frobenius $r \mapsto r^p$ es), se deduce que $x=y$ . De ello se desprende que $X^{p^m} - a$ tiene exactamente una raíz $x \in K$ de multiplicidad $p^m$ .

Si $g \in \mathrm F_{p^m} [X]$ es el polinomio mínimo de $x$ entonces $X^{p^m} - a = g^s$ ya que $p^m = s \deg g$ se deduce que $s = p^t$ . Dejemos que $b = -g(0)$ y asumir $t>0$ . Evaluación de $X^{p^m} - a = g^s$ en $0$ y asumiendo $t>0$ obtenemos $a = (b^{p^{t-1}})^p$ (porque $-1 = (-1)^s$ en la característica $p>0$ ), lo que implicaría que $X^p - a$ tiene la raíz $b^{p^{t-1}} \in \mathrm F _{p^m}$ , lo que contradiría la hipótesis del criterio. De ello se desprende que $t=0$ para que $s=1$ Por lo tanto $X^{p^m} - a$ es el polinomio mínimo de $a$ por lo que es irreducible según la definición del concepto de "polinomio mínimo".