¿Hay alguna manera de encontrar un polinomio irreducible de grado n en el campo Z2

Question

Me piden que encuentre un polinomio irreducible de cierto grado en el campo Z2.

No voy a especificar el grado que me piden aquí porque me gustaría entender el método y saber aplicarlo a preguntas posteriores. Sólo necesito un polinomio irreducible, no necesito encontrarlos todos, etc.

Supongamos que el grado es demasiado alto para buscar 2^n polinomios diferentes, o para usar la división larga de polinomios para probar contra polinomios irreducibles de grado < n+1/2

Su ayuda y sus sencillas explicaciones serán muy apreciadas.

Editar: Vale, gracias por vuestras respuestas, ¡son muy útiles! Parece que para obtener una respuesta directa tendré que dar el grado específico (sin embargo, si alguien pudiera responder para resolver con el grado n sería fantástico).

Necesito encontrar un polinomio irreducible de grado 20 en Z2. Tengo una idea pero me parece muy larga:

Para encontrar todos los polinomios irreducibles de grado 5 entonces necesito encontrar todos los polinomios de grado 5 sin divisores polinómicos de grado < 3.

¿Podría entonces repetir esto para encontrar los polinomios irreducibles de grado 10 utilizando los polinomios de grado 5 que encontré en el paso anterior, y luego repetir de nuevo para encontrar los polinomios irreducibles de grado 20?

Como he dicho esto parece muy largo, estoy seguro de que hay una manera más fácil.

Answer 1

Si $p(x)$ es un polinomio primo, entonces es un polinomio irreducible. Si $p(x)$ es un polinomio primo de grado $n$ entonces $\mathbb{Z}[x]/p(x)$ es un campo de orden $2^n$ y así $p(z)|z^{2^n}-z$ . Esto reducirá en gran medida la búsqueda.

La mayoría de las técnicas se basan en cosas específicas del grado exacto, desgraciadamente, y no hay ninguna técnica general útil, según parece.

Answer 2

En general es difícil, pero como la comprobación de la irreductibilidad es razonablemente rápida (para una definición adecuada de razonablemente rápida) encontrar una por pinchazo aleatorio no llevará demasiado tiempo porque un grado aleatorio $n$ es irreducible con una probabilidad aproximada de $1/n$ .

Como dijo Stella Biderman, la mayoría de los métodos son específicos de la titulación y, por tanto, ad hoc. ¿Grado 20 ha dicho? Eso es fácil, porque

• $20=\phi(25)$ y
• $2$ genera el grupo $\Bbb{Z}_{25}^*$ .

Estos dos hechos juntos implican que el polinomio ciclotómico de característica cero $$ \Phi_{25}(x)=\frac{x^{25}-1}{x^5-1}=x^{20}+x^{15}+x^{10}+x^5+1 $$ sigue siendo irreducible sobre $\Bbb{Z}_2$ .

Esto se ve de la siguiente manera. Sea $\alpha$ sea una raíz primitiva de la unidad de orden $25$ (en algún campo de extensión de $\Bbb{Z}_2$ ). Sea $m(x)$ sea el polinomio mínimo de $\alpha$ . Por la teoría de Galois obtenemos todos los ceros de $m(x)$ aplicando repetidamente el automorfismo de Frobenius, $F:x\mapsto x^2$ , a $\alpha$ por lo que los ceros de $m(x)$ incluye $$ \alpha,\alpha^2,\alpha^4,\alpha^8,\alpha^{16},\alpha^{32}=\alpha^7, \alpha^{14},\ldots $$ Por el segundo punto anterior la lista contiene exactamente las potencias $\alpha^k, 1\le k<25, \gcd(k,25)=1$ . En otras palabras, todas las raíces primitivas de orden $25$ . Por lo tanto, $$ m(x)=\Phi_{25}(x) $$ es irreducible módulo 2.