Determine si un polinomio es irreducible

Question

Considere el polinomio $P=X^5-X-1\in\Bbb{F}_3[X]$. Quiero mostrar que la $P$ es irreductible. Podemos comprobar fácilmente que no tiene raíces, por lo que la única manera en que podría no ser irreducible es por ser un producto de dos polinomios de grado $2$ e $3$ respectivamente. Así que determinar todos los polinomios irreducibles de grado $2$ en $\Bbb{F}_3[X]$. Estas son las $$X^2+1;{~~} X^2+X-1 {~~}\text{and}{~~}X^2-X-1.$$ Finalmente puedo comprobar mediante el algoritmo de la división Euclídea de que ninguno de los polinomios divide $P$, lo que concluye la prueba.

Mi pregunta es esta: ¿hay una manera más eficiente de hacer esto? Primero tuve que determinar todos los polinomios de un determinado grado ($2$) y, a continuación, aplicar el algoritmo de Euclides para cada uno de ellos. Que es algo de trabajo, y todavía estamos considerando polinomios de relativamente pequeño grado, y los campos de los pequeños cardenal. No me puedo imaginar aplicando el mismo razonamiento para determinar si $Q=X^9-X^2-1\in\Bbb{F}_{17}[X]$ es irreductible.

Así, hay un método más eficiente para determinar irreductibilidad, al menos en el caso de polinomios de grado pequeño, con pequeños campos?

Answer 1

Sí. Calcular el grado de $X$ en el cociente del anillo. En tu ejemplo, si $\deg(X) \lt 17^9-1$, a continuación, $Q$ es reducible. De lo contrario, es irreductible. Habrá accesos directos disponibles, basados en el hecho de que cada elemento del campo subyacente es una raíz de la unidad de la conocida grado. Yo no quiero hacer esto a mano, pero debe ser bastante simple para un equipo.

El uso de $P$ como su ejemplo, el grupo multiplicativo de el anillo tiene orden de $3^5-1=242=2 \cdot 11^2$ tan solo necesitamos comprobar que $X$ no tiene orden de $2, 11, 22, \text{ or } 121$.

Obviamente $X^2 \neq 1$.

$X^5=X+1$, lo $X^{10}={(X+1)}^2 = X^2-X+1 \text{ and } X^{11} = X(X+1)^2 = X^3 -X^2+X \neq 1.$

$X^{22} = (X^{11})^2 = (X(X+1)^2)^2 = X^2(X+1)^4 = X^2(X^4+X^3+X+1)= X^6+X^5+X^2+X= X^2+X+X+1+X^2+X = -X^2+1 \neq 1.$

La determinación de $X^{121}$ es un poco más tedioso, pero puede ser determinada por la mano así.