Let $q=7681$ be a prime. The $n$-th cyclotomic polynomial for $n=512$ is $f=x^{256}+1$. This polynomial is supposed to be irreducible over $\mathbb{F}_q$. However the polynomial factors in the above field. I am pasting the gp/pari script.
q=7681; f=Mod(1,q)*x^256 + Mod(1,q); factor(f);
This returns 256 factors. For example
[Mod(1, 7681)*x + Mod(7587, 7681) 1], [Mod(1, 7681)*x + Mod(7619, 7681) 1], ..etc.
I cannot understand this behavior.
All cyclotomic polynomials are irreducible over $\mathbb Q$, but this is not true for finite fields, in general.
In this particular case, the order $q-1$ of the unit group $\mathbb F_q^\times$ is divisible by $512$, so $\mathbb F_q$ contains $512$th roots of unity and therefore, $X^{512}-1$ (and then also $f$) decomposes into linear factors over $\mathbb F_q$.