¿Qué son los polinomios irreducibles sobre GF (2)?

Hablaré de manera más general acerca de encontrar polinomios irreducibles en F_p [x]. La idea es que el proceso sea similar al tamiz de Eratóstenes. Usted enumera los polinomios monicos grado por grado y tacha los que son productos. Como estás interesado en F_2, ahora nos especializaremos en eso.

Para F_2 [x], los polinomios monicos de grado 1 son xyx + 1, los cuales son irreductibles. Los polinomios monicos de grado 2 son x ^ 2, x ^ 2 + 1, x ^ 2 + x, y x ^ 2 + x + 1. Como x ^ 2, x ^ 2 + 1, x ^ 2 + x tienen raíces en F_2, se pueden escribir como productos de x y x + 1. Por lo tanto, x ^ 2 + x + 1 es el único polinomio irreducible de grado 2 en F_2 [x]. Para el grado 3, el polinomio p (x) no debe tener ningún factor lineal. Esto significa que p (0) = p (1) = 1, y vemos que x ^ 3 + x ^ 2 + 1 y x ^ 3 + x + 1 son los únicos polinomios irreducibles de grado 3. Puede avanzar en la manera demostrada Pero esto claramente no es muy eficiente, si desea determinar todos los polinomios irreducibles de grado <n para n grande.

Sea p (x) un polinomio de grado 4. Es irreducible si no tiene factores lineales o cuadráticos. Como arriba, todavía necesitamos p (0) = p (1) = 1. El polinomio debe tener un número impar de términos (¿por qué?) Dado que hay 2 ^ 4 = 16 polinomios de grado 4, podemos descartar 12 de ellos mediante este simple análisis, por lo que solo quedan cuatro. Ahora, solo tenemos un polinomio irreducible de grado 4, por lo que el único polinomio que queda que debemos eliminar y que aún no se ha eliminado es (x ^ 2 + x + 1) ^ 2 = x ^ 4 + x ^ 2 + 1) Los otros tres son irreductibles. A saber, x ^ 4 + x ^ 3 + x ^ 2 + x + 1, x ^ 4 + x ^ 3 + 1 y x ^ 4 + x + 1. Ahora que sabemos cuáles son los polinomios irreducibles de grado 3, podemos usar un análisis similar para determinar los polinomios irreducibles de grado 5, y así sucesivamente.

Ejercicio: ¿cuáles son los polinomios monicos irreducibles de grado 2 en F_3 [x]? (Estoy haciendo esta pregunta en particular como un ejercicio porque la respuesta está ahí para que la revises en la página 373 del libro de Artin).