Cuál es la descomposición del anillo $\mathbb{F}_p[x]/(x^n-1)$ ?

Question

Dejemos que $p$ sea un primo, y $n\ge 1$ un número entero.

Me gustaría descomponer el anillo $\mathbb{F}_p[x]/(x^n-1)$ en un producto directo de anillos locales artinianos.

Sé que podemos escribir $x^n-1 = \prod_{d\mid n}\Phi_d(x)$ pero, ¿cómo los polinomios ciclotómicos $\Phi_d(x)$ descomponer mod $p$ ? Sé que sus factores irreducibles deben tener grado igual al orden de $p$ modulo $d$ . Puede $\Phi_d(x)$ tienen factores irreducibles distintos (¿o siempre se descomponen como una potencia de un irreducible?)? ¿Puede $\Phi_d(x),\Phi_{d'}(x)$ comparten factores irreducibles para $d\ne d'$ ?

¿Existe una forma agradable de escribir esta descomposición?

Answer 1

Creo que su enfoque a través de los polinomios ciclotómicos $\Phi_d (X)$ es engañoso, porque su irreductibilidad es una propiedad "global" (todos los primos intervienen), mientras que su pregunta aquí es una "local" (un primo fijo $p$ se da). Empecemos de nuevo y escribamos $n=p^r m$ , $p$ no dividir $m$ . Entonces, como en la respuesta de @Jyrki Lahtonen, $X^n - 1 = (X^m - 1)^{p^r}$ en $\mathbf F_p [X]$ por lo que sólo tenemos que estudiar la descomposición de $X^m - 1$ . Por la teoría de Galois, esto equivale a estudiar la extensión $\mathbf E =\mathbf F_p(\zeta_m)$ en $\mathbf F_p$ , donde $\zeta_m$ es una primitiva $m$ -en la raíz de la unidad. Si $f$ es el grado de $\mathbf E/\mathbf F_p$ por la teoría de los campos finitos, $G =Gal(\mathbf E/\mathbf F_p)$ es cíclico de orden $f$ generado por el automorfismo de Frobenius $\sigma_p$ definido por $\sigma_p(x) = x^p$ . De ello se desprende que $f$ es el orden de $p$ mod $m$ (cp. su comentario sobre los factores irreducibles de $\Phi_d (X)$ mod $p$ ) y $G$ puede identificarse con un subgrupo cíclico de orden $f$ de $(\mathbf Z /m\mathbf Z)^*$ . Queda por deducir de esto la descomposición de $X^m - 1$ en $\mathbf F_p [X]$ .

Para cualquier $d$ dividiendo $m$ , dejemos que $\zeta_d$ sea cualquier primitiva $d$ -raíz de la unidad. Como $G$ permuta transitivamente las raíces primitivas $\zeta_d$ (que son todos distintos porque $p$ no divide $m$ ), el polinomio $\Psi_d (X) :=$ producto de la $(X - \zeta_d)$ pertenece a $\mathbf F_p [X]$ y $X^m - 1$ es el producto sobre todos los $d$ dividiendo $m$ de la $\Psi_d (X)$ 's. Además $\Psi_d (X)$ es irreducible : supongamos que se descompone como un producto $g_1. ... g_s$ de distinto polinomios irreducibles en $\mathbf F_p [X]$ (sin potencia porque todos los ceros son simples); si $\zeta$ es una raíz de $g_1$ (para que $g_1$ es el polinomio mínimo de $\zeta$ en $\mathbf F_p$ ), entonces $\zeta ^p$ será una raíz de algún $g_j$ pero como $g_j (\zeta ^p)=(g_j(\zeta))^p=0$ , $g_1$ dividirá $g_j$ Así que $g_1 = g_j$ hasta una constante multiplicativa, una contradicción.

En conclusión, la descomposición de $X^m - 1$ en $\mathbf F_p [X]$ es el producto de todos los $\Psi_d (X)$ 's para $d$ dividiendo $m$ . Este es el análogo (pero no la reducción) mod $p$ de la descomposición de $X^m - 1$ en el producto de los polinomios ciclotómicos $\Phi_d (X)$ .

Answer 2

Si quieres descomponer los polinomios ciclotómicos en módulo de primos, echa un vistazo a la sección 14.10 "Cyclotomic polynomials and constructing BCH code" del libro Álgebra computacional moderna por Joachim von zur Gathen y Juergen Gerhard.

El algoritmo 14.48 da como resultado el $n$ -ésima polinómica ciclotómica en el tiempo $O(M(n)\log(n))$ donde $M(n)$ es el tiempo para $n$ -multiplicación de bits.

La observación después del Lemma 14.50/Ejemplo 14.51 dice que se puede utilizar directamente el algoritmo de factorización de igual grado sobre campos finitos (dado en otro capítulo), pero en el Ejercicio 14.47 se da un algoritmo aún más rápido que factoriza $x^n-1$ en el tiempo $O^\tilde{}(n\log^2(q))$ operaciones de palabras (para la definición de "soft Oh" $O^\tilde{}$ ver definición 25.8 del libro, es para "tragar" feo $\log$ -factores).