Factoring $x^{n}-1$ over the finite field $\mathbf F_q$.

Question

If $\mathbf F_q$ is a finite field. Then how to factor $x^{n}-1$ in $\mathbf F_q[x]$?

I think we can suppose that $(q,n)＝1$,since if $n＝q^{e}n'$ then $x^{n}-1＝(x^{n'}-1)^{q^{e}}$ so that we just consider how to factor $x^{n'}-1$, which is the same.

Answer 1

Since $q$ might not be prime, but only a power of a prime $p$ (e.g., $q = 8$), you should not be factoring out the biggest power of $q$ from $n$, but the biggest power of $p$ from $n$. Write $n = p^en'$ where $p \nmid n'$ and then in $\mathbf F_q[x]$, $x^n - 1 = (x^{n'}-1)^{p^e}$.

You can factor $x^{n'}-1$ further in $\mathbf Z[x]$ to cyclotomic polynomials indexed by the (positive) factors of $n'$. Then reduce the factorization mod $p$ to have a factorization in $\mathbf F_p[x] \subset \mathbf F_q[x]$. In order to factor each of those cyclotomic factors further in $\mathbf F_q[x]$, Galois theory for finite fields says the degree of a number over $\mathbf F_q$ is the number of its distinct $q$-power iterates. So if $q$ is a power of the prime $p$ and $\alpha$ in a field of characteristic $p$ has multiplicative order $m$ (necessarily $p \nmid m$), then $[\mathbf F_q(\alpha):\mathbf F_q]$ is the number of distinct values among $\alpha, \alpha^q, \alpha^{q^2}, \ldots$, which is the order of $q \bmod m$. So when $p \nmid m$, the $m$th cyclotomic polynomial (with coefficients reduced mod $p$, where $q$ is a power of $p$, and having degree $\varphi(m)$) will break up over $\mathbf F_q$ into irreducible factors all having degree equal to the order of $q \bmod m$.