Encontrar todos los irreductible monic polinomios en $\mathbb{Z}/(2)[x]$ con grado igual o menos de 5

Question

Encontrar todos los irreductible monic polinomios en $\mathbb{Z}/(2)[x]$ con grado igual o menos de $5$.

Esto es lo que he intentado:

Es evidente que $x,x+1$ son irreductibles. A continuación, utilice estos para encontrar todos los reducible polinomios de grado 2. Hay unos que no se pueden realizar son irreductibles. A continuación, utilice estos para hacer polinomios de grado 3, los que no se pueden realizar son irreductibles. Repetir hasta el grado 5.

Haciendo de esta manera se tarda mucho y me di por vencido cuando estaba a punto de llegar a grado 4 polinomios.

Mi pregunta es: ¿hay alguna manera más fácil encontrar estos polinomios?

P. S.: esto no es exactamente la tarea, pero una pregunta que me encontré mientras estudiaba para un examen.

Answer 1

Extrapolado Comentarios convertido a responder:

En primer lugar, observamos que hay $2^n$ polinomios en $\mathbb{Z}_2[x]$ grado $n$.

Un polinomio $p(x)$ grado $2$ o $3$ es irreducible si y sólo si no tiene factores lineales. Por lo tanto, es suficiente para mostrar que $p(0) = p(1) = 1$. Esto rápidamente se nos dice que $x^2 + x + 1$ es el único polinomio irreducible de grado $2$. Esto también nos dice que $x^3 + x^2 + 1$ $x^3 + x + 1$ son los únicos polinomios irreducibles de grado $3$.

Como hardmath puntos, para un polinomio $p(x)$ grado $4$ o $5$ a ser irreductible, es suficiente para mostrar que $p(x)$ no tiene lineal o cuadrática factores. Para descartar los lineales de los factores, podemos volver a tirar cualquier polinomio no satisfacer $p(0) = p(1) = 1$. Es decir, podemos tirar cualquier polinomio con término constante $0$, y podemos tirar cualquier polinomio con un número par de términos. Esto descarta $3/4$ de los polinomios. Por ejemplo, el $4^{th}$ grado de los polinomios que no tienen lineal factores son:

• $ x^4 + x^3 + x^2 + x + 1 $
• $ x^4 + x^3 + 1 $
• $ x^4 + x^2 + 1 $
• $ x^4 + x + 1 $

El $5^{th}$ grado de los polinomios que no contienen lineal factores son:

• $x^5 + x^4 + x^3 + x^2 + 1$
• $x^5 + x^4 + x^3 + x + 1$
• $x^5 + x^4 + x^2 + x + 1$
• $x^5 + x^3 + x^2 + x + 1$
• $x^5 + x^4 + 1$
• $x^5 + x^3 + 1$
• $x^5 + x^2 + 1$
• $x^5 + x + 1$

Queda por comprobar si $x^2 + x + 1$ (que es la única cuadrático irreducible polinomio en $\mathbb{Z}_2[x]$) divide a alguno de estos polinomios. Esto puede ser hecho a mano para suficientemente pequeño grados. De nuevo, como hardmath puntos, ya que el $x^2 + x + 1$ es el único polinomio irreducible de grado $2$, se deduce que el $(x^2 + x + 1)^2 = x^4 + x^2 + 1$ es el único polinomio de grado $4$ que no tiene factores lineales y, sin embargo, no es irreducible. Por lo tanto, el otro $3$ polinomios de la lista debe ser irreductible. Del mismo modo, el grado $5$ polinomios, podemos descartar

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

y

$$ (x^2 + x + 1)(x^3 + x + 1) = x^5 + x^4 + 1. $$

El otro $6$ aparece polinomios por lo tanto debe ser irreductible.

Aviso que este truco de tirar polinomios lineales de los factores, entonces cuadrática factores, etc. (que hardmath llamado similar a la Criba de Eratóstenes) no es eficiente para grandes polinomios de grado (incluso el grado $6$ empieza a ser un problema, ya que un polinomio de grado $6$ factor como un producto de polinomios de grado $3$). Este método, por lo tanto solo funciona lo suficientemente pequeño grado de los polinomios.

En resumen, los polinomios irreducibles en $\mathbb{Z}_2[x]$ grado $\leq 5$ son:

• $x$
• $x+1$
• $x^2 + x + 1$
• $x^3 + x^2 + 1$
• $x^3 + x + 1$
• $ x^4 + x^3 + x^2 + x + 1 $
• $ x^4 + x^3 + 1 $
• $ x^4 + x + 1 $
• $x^5 + x^4 + x^3 + x^2 + 1$
• $x^5 + x^4 + x^3 + x + 1$
• $x^5 + x^4 + x^2 + x + 1$
• $x^5 + x^3 + x^2 + x + 1$
• $x^5 + x^3 + 1$
• $x^5 + x^2 + 1$

Answer 2

El difícil camino para hacer esto es darse cuenta de que si $p(x)$ es el primer polinomio de grado $n$, ${\mathbb{Z}_2[z]}/{p(z)}$ es un campo de orden de $2^n$ y, por tanto, para cada elemento $a$ del campo, $\ a^{2^n}-a = 0$. En particular, entonces, $z^{2^n}-z$ debe ser divisible por $p(z)$. Ahora, $z^{2^n}-z$ también es divisible por cualquier primer polinomio de grado $d|n$, por lo que primero tenemos que el factor de aquellos, y luego de obtener el producto de los números primos de grado $n$.

En particular, $x^8-x$ debe ser un producto de los números primos de grado uno y los números primos de grado $3$. Podemos fácilmente factor $x(x+1),$ y vemos que los números primos de grado $3$ deben multiplicar para obtener $x^6+x^5+x^4+x^3+x^2+x+1$. Así que usted puede probar para primeness de un polinomio de grado $3$ por ver si se divide en dicho polinomio.

Del mismo modo, para $n=4$, usted tiene $x^{16}-x$ debe ser el producto de los números primos de grados $1,2$$4$. El único de primer grado $2$ $x^2+x+1,$ por lo que el producto de los números primos de grado $4$ debe $\dfrac{x^{16}-x}{(x^2+x+1)x(x+1)}\ =\ 1 + x^3 + x^6 + x^9 + x^{12}\:.\ $, por Lo que sabemos que hay $3$ primos de orden $4$.

Finalmente, los productos de los números primos de grado $5$ debe $\ \dfrac{x^{32}-x}{x(x+1)}\ =\ 1 + x + x^2 +\:\cdots\: + x^{30}$.

Tenga en cuenta que los números primos de grado $3$ ser $x^3+x+1$$x^3+x^2+1$. Eso es porque si $p(x)$ es primo, entonces $p(1)=1$$p(0)=1$. Por lo tanto tenemos que $x^3$ $1$ términos f $p(x)$, y tenemos que tener un número impar de cero términos en $p(x)$.

Answer 3

Como DJC señala que gran parte de la pala trabajo es de notar que los polinomios tienen lineal de los factores, o, equivalentemente, que tienen sus raíces en 0 o 1. Esto es suficiente para comprobar cuadrática y cúbica de polinomios (mod 2).

La única otra cosa que la regla (en la búsqueda de polinomios irreducibles de grado 5 o menos) es una ecuación cuadrática factor! Así por analogía con la Criba de Eratóstenes, vamos a utilizar la evaluación en 0 y 1 (término constante no es 0 y el número de distinto de cero los coeficientes impares) para obtener una lista de todos los polinomios irreducibles (mod 2) de grado 2:

$x^2 + x + 1$

Luego de un polinomio (mod 2) de grado 4 o 5 es irreducible si y sólo si, además de no tener una raíz en x = 0 o x = 1, el polinomio no tiene la irreductible cuadrática anterior como un factor. Para el grado 4 es sólo posible tener el cuadrática factor, pero no lineal si el polinomio es el cuadrático irreducible al cuadrado, de modo que sólo un caso para comprobar.

$(x^2 + x + 1)^2 = x^4 + x^2 + 1$
[reducible]

Para el grado 5 análogas a las de la prueba sería de descartar la irreductible cuadrática veces uno de los (dos) irreductible polinomios cúbicos.