Es $x^8 + x^5 + x^3 + x^2 + 1$ un polinomio irreducible o no en GF $2^8$

Question

Es $x^8 + x^5 + x^3 + x^2 + 1$ un polinomio irreducible o no en el campo de Galois $2^8$ ? Gracias de antemano.

Answer 1

La pregunta es un poco confusa. Si usted está realmente preguntando si este polinomio $$ p(x)=x^8+x^5+x^3+x^2+1 $$ es irreducible en el anillo $GF(256)[x]$ entonces la respuesta es trivialmente ¡NO! Esto se debe a que:

• O bien es reducible sobre $GF(2)$ en cuyo caso también es reducible sobre el campo de extensión,
• O es irreducible sobre $GF(2)$ en cuyo caso $GF(2)[x]/\langle p(x)\rangle$ es un campo de 256 elementos, y por tanto isomorfo (o igual a) $GF(256)$ . En este caso $p(x)$ tiene 8 ceros distintos en el campo, a saber, los cosets $x^{2^i}+\langle p(x)\rangle$ , $i=0,1,2,\ldots,7$ . En consecuencia $p(x)$ se dividiría en factores lineales sobre $GF(256)$ .

Pero he sido un poco travieso, porque me he tomado la pregunta al pie de la letra. Es de suponer que usted no preguntaría cosas como: "¿Es $x^2+1$ irreducible sobre los números complejos?", porque sabes que factoriza como $(x+i)(x-i)$ sur $\Bbb{C}[x]$ . La única suposición sensata es que usted está preguntando si $p(x)$ es irreducible sobre $GF(2)$ .

Como se ha señalado en los comentarios, debe demostrar que $p(x)$ no tiene factores de grado 4 o inferior. Los sospechosos habituales son $x,x+1,x^2+x+1,x^3+x+1,x^3+x^2+1,x^4+x+1,x^4+x^3+1$ y $x^4+x^3+x^2+x+1$ . Si te lo han dado como ejercicio, tu profesor/libro debe haberlo producido en algún momento anterior (de lo contrario, sería un poco travieso por su parte, salvo que introduzcan un algoritmo general como el de Berlekamp).

• Porque $p(x)$ tiene cinco términos $1$ podemos descartar inmediatamente los factores lineales.
• El factor cuadrático es un factor de $x^3+1$ . Pero $x^8+x^5=(x^3+1)x^5$ Así que $$p(x)\equiv x^2\pmod{x^2+x+1}.$$ Por lo tanto no hay factor cuadrático irreducible.
• Ambos polinomios cúbicos irreducibles son factores de $x^7+1$ (el grupo multiplicativo del campo $GF(8)$ es cíclico de orden siete). Vemos que $x^8\equiv x\pmod{x^7+1}$ Así que $p(x)\equiv x^5+x^3+x^2+x+1\pmod {x^7+1}$ . Si esto fuera divisible por $x^3+x+1$ entonces también lo haría $x^5+x^2=x^2(x^3+1)=x^2(x+1)(x^2+x+1)$ lo cual es absurdo. Del mismo modo, si fuera divisible por $x^3+x^2+1$ entonces también lo haría $x^5+x=x(x^4+1)=x(x+1)^4$ violando de nuevo la unicidad de la factorización.

Esto deja la posibilidad de que $p(x)$ podría ser un producto de dos cuárticos irreducibles, es decir, un producto de dos de $f_1(x)=x^4+x+1$ , $f_2(x)=x^4+x^3+1$ , $f_3(x)=x^4+x^3+x^2+x+1$ . ¿Podría $f_1(x)$ ser un factor? Tenemos $f_1(x)^2=x^8+x^2+1$ Así que $$ p(x)\equiv x^5+x^3\pmod{f_1(x)}. $$ Como en el caso cúbico esto lleva a una contradicción ya que $x^5+x^3=x^3(x+1)^2$ no es divisible por $f_1(x)$ .

Porque $p(x)$ contiene términos de grado impar, no es el cuadrado de un polinomio. La única posibilidad que queda es $$ p(x)=f_2(x)f_3(x). $$ Le dejo a usted la tarea de descartar esta posibilidad. Ya sea por fuerza bruta o mediante el uso de una de las técnicas descritas aquí.

Answer 2

Voy a decir al principio que no estoy muy familiarizado con esta área, sólo pensé que iba a tomar un tiro en esto ya que no ha habido mucho. Por favor, corrígeme si estoy malinterpretando algo.

Supongamos que tenemos los polinomios

$$ P_0(x) = x^8 + x^5 + x^3 + x^2 + 1$$

$$ P_1(x) = A_7\,x^7 + A_6\,x^6 + A_5\,x^5 + A_4\,x^4 + A_3\,x^3 + A_2\,x^2 + A_1\,x^1 + A_0\,x^0 $$ $$ P_2(x) = B_7\,x^7 + B_6\,x^6 + B_5\,x^5 + B_4\,x^4 + B_3\,x^3 + B_2\,x^2 + B_1\,x^1 + B^0\,x^0 $$

Ahora bien, si $P_0(x) \equiv P_1(x)\cdot P_2(x) \pmod{256}$ entonces $P_0(x) \equiv P_1(x)\cdot P_2(x) \pmod{2}$ desde $2 \mid 256$ . Así podemos comprobarlo:

$$\begin{align} 0 & \equiv A_7\,B_7\pmod{2} \\ 0 & \equiv A_6\,B_7 + A_7\,B_6\pmod{2} \\ 0 & \equiv A_5\,B_7 + A_6\,B_6 + A_7\,B_5\pmod{2} \\ 0 & \equiv A_4\,B_7 + A_5\,B_6 + A_6\,B_5 + A_7\,B_4\pmod{2} \\ 0 & \equiv A_3\,B_7 + A_4\,B_6 + A_5\,B_5 + A_6\,B_4 + A_7\,B_3\pmod{2} \\ 0 & \equiv A_2\,B_7 + A_3\,B_6 + A_4\,B_5 + A_5\,B_4 + A_6\,B_3 + A_7\,B_2\pmod{2} \\ 1 & \equiv A_1\,B_7 + A_2\,B_6 + A_3\,B_5 + A_4\,B_4 + A_5\,B_3 + A_6\,B_2 + A_7\,B_1\pmod{2} \\ 0 & \equiv A_0\,B_7 + A_1\,B_6 + A_2\,B_5 + A_3\,B_4 + A_4\,B_3 + A_5\,B_2 + A_6\,B_1 + A_7\,B_0\pmod{2} \\ 0 & \equiv A_0\,B_6 + A_1\,B_5 + A_2\,B_4 + A_3\,B_3 + A_4\,B_2 + A_5\,B_1 + A_6\,B_0\pmod{2} \\ 1 & \equiv A_0\,B_5 + A_1\,B_4 + A_2\,B_3 + A_3\,B_2 + A_4\,B_1 + A_5\,B_0\pmod{2} \\ 0 & \equiv A_0\,B_4 + A_1\,B_3 + A_2\,B_2 + A_3\,B_1 + A_4\,B_0\pmod{2} \\ 1 & \equiv A_0\,B_3 + A_1\,B_2 + A_2\,B_1 + A_3\,B_0\pmod{2} \\ 1 & \equiv A_0\,B_2 + A_1\,B_1 + A_2\,B_0\pmod{2} \\ 0 & \equiv A_0\,B_1 + A_1\,B_0\pmod{2} \\ 1 & \equiv A_0\,B_0\pmod{2} \\ \end{align}$$

Esto es bastante simple de comprobar con un ordenador, mi búsqueda resultó que es irreductible.