Are cyclotomic polynomials irreducible modulo a prime? I am actually interested on cyclotomic polynomials of the form $x^n+1$ (i.e. $n$ is a power of 2, for large $n$).
Are these polynomials irreducible modulo a prime $q$? I already saw that $X^2+1$ is not irreducible modulo 5 because $Z_5$ contains roots of -1. What about $x^{512}-1$? Is there a general criterion?
Thanks

I find this relatively general answer from the Finite Field book by Rudolf, theorem 2.47, helpful:
The cyclotomic field $K^{(n)}$ is a simple algebraic extension of $K$. If $K=\mathbb{F}_q$ with $\gcd(q,n)=1$, then the cyclotomic polynomial $Q_n$ factors into $\phi(n)/d$ distinct monic irreducible polynomials in $K[x]$ of the same degree $d$. Here $d$ is the least positive integer such that $q^d \equiv 1 \mod n$.
