What is the decomposition of the ring $\mathbb{F}_p[x]/(x^n-1)$?

Question

Let $p$ be a prime, and $n\ge 1$ an integer.

I'd like to decompose the ring $\mathbb{F}_p[x]/(x^n-1)$ into a direct product of artinian local rings.

I know we can write $x^n-1 = \prod_{d\mid n}\Phi_d(x)$, but how do the cyclotomic polynomials $\Phi_d(x)$ decompose mod $p$? I know their irreducible factors should have degree equal to the order of $p$ modulo $d$. Can $\Phi_d(x)$ have distinct irreducible factors (or do they always decompose as a power of an irreducible?)? Can $\Phi_d(x),\Phi_{d'}(x)$ share irreducible factors for $d\ne d'$?

Is there a nice way to write this decomposition?

Answer 1

I think that your approach via the cyclotomic polynomials $\Phi_d (X)$ is misleading, because their irreducibility is a "global" property (all primes intervene), whereas your question here is a "local" one (a fixed prime $p$ is given). Let us start afresh and write $n=p^r m$, $p$ not dividing $m$. Then, as in the answer of @Jyrki Lahtonen, $X^n - 1 = (X^m - 1)^{p^r}$ in $\mathbf F_p [X]$ , so that we need only to study the decomposition of $X^m - 1$ . By Galois theory, this amounts to study the extension $\mathbf E =\mathbf F_p(\zeta_m)$ over $\mathbf F_p$, where $\zeta_m$ is a primitive $m$-th root of unity. If $f$ is the degree of $\mathbf E/\mathbf F_p$, by the theory of finite fields, $G =Gal(\mathbf E/\mathbf F_p)$ is cyclic of order $f$, generated by the Frobenius automorphism $\sigma_p$ defined by $\sigma_p(x) = x^p$. It follows that $f$ is the order of $p$ mod $m$ (cp. your remark on the irreducible factors of $\Phi_d (X)$ mod $p$) and $G$ can be identifed with a cyclic subgroup of order $f$ of $(\mathbf Z /m\mathbf Z)^*$. It remains to deduce from this the decomposition of $X^m - 1$ in $\mathbf F_p [X]$.

For any $d$ dividing $m$, let $\zeta_d$ be any primitive $d$-th root of unity. Since $G$ permutes transitively the primitive roots $\zeta_d$ (which are all distinct because $p$ does not divide $m$), the polynomial $\Psi_d (X) :=$ product of the $(X - \zeta_d)$ 's belongs to $\mathbf F_p [X]$, and $X^m - 1$ is the product over all $d$ dividing $m$ of the $\Psi_d (X)$'s. Moreover $\Psi_d (X)$ is irreducible : suppose that it decomposes as a product $g_1. ... g_s$ of distinct irreducible polynomials in $\mathbf F_p [X]$ (no power because all the zeroes are simple); if $\zeta$ is a root of $g_1$ (so that $g_1$ is the minimal polynomial of $\zeta$ over $\mathbf F_p$), then $\zeta ^p$ will be a root of some $g_j$, but since $g_j (\zeta ^p)=(g_j(\zeta))^p=0$, $g_1$ will divide $g_j$, so $g_1 = g_j$ up to a multiplicative constant, a contradiction.

In conclusion, the decomposition of $X^m - 1$ in $\mathbf F_p [X]$ is the product of all the $\Psi_d (X)$'s for $d$ dividing $m$. This is the analog (but not the reduction) mod $p$ of the decomposition of $X^m - 1$ into the product of the cyclotomic polynomials $\Phi_d (X)$.

Answer 2

If you want to decompose the cyclotomic polynomials modulo primes, take a look at section 14.10 "Cyclotomic polynomials and constructing BCH code" of the book Modern Computer Algebra by Joachim von zur Gathen and Juergen Gerhard.

Algorithm 14.48 outputs the $n$-th cyclotomic polynomial in time $O(M(n)\log(n))$ where $M(n)$ is the time for $n$-bit multiplication.

The remark after Lemma 14.50/Example 14.51 tells you that you can directly use the equal-degree factorization algorithm over finite fields (given in another chapter), but in Exercise 14.47 an even faster algorithm is given that factors $x^n-1$ in time $O^\tilde{}(n\log^2(q))$ word operations (for the definition of "soft Oh" $O^\tilde{}$ see Definition 25.8 of the book, it's for "swallowing" ugly $\log$-factors).

Answer 3

A natural way is to look at your ring as the ring of $n\times n$ circulant matrices over $\mathbb{F}_p$ (see e.g. Sect 2.3 here). In this paper we have written down explicit decompositions for the group of units in such rings as an abelian group. I imagine this would help to deal with your question too.