# Reducibility of polynomials over finite fields

I'm asking this question with regards to when a polynomial $m(t)$ can be the minimal polynomial of an algebraic element $\alpha$ of a field extension $F(\alpha):F$, when $F$ is a finite field.

For example, if we have a polynomial like $t^{37}+1$, we know the polynomial has an obvious root in $\mathbb{F}_p$, namely we can use $(p-1)^{37}+1=0$. That means we can factorise the polynomial into $t^{37}+1=(t-(p-1))\cdot(t^{36}+\ldots+(p-1))$. What about general monic polynomials over finite fields? Is there something analogous to Eisenstein's criterion that we can use to check for irreducibility?

• You might be interested in en.wikipedia.org/wiki/… – azimut Aug 29 '13 at 10:02
• Yes. Eisenstein Crierion applies for integral domains in general...but it isn't as useful as with the rationals, since finite integral domains = fields. – DonAntonio Aug 29 '13 at 10:04
• Finite fields are not fields of fractions of anything simpler, so divisibility questions between coefficients are meaningless => nothing like Eisenstein's criterion exists. – Jyrki Lahtonen Aug 29 '13 at 10:06
• I often approach irreducibility of these polynomials from a different angle: non-zero elements of finite fields are always roots of unity. Characteristic zero theory tells that the minimal polynomials of roots of unity are the cyclotomic polynomials, so the question can, in a way, be rephrased as: how do the cyclotomic polynomials factor, when reduced modulo a prime? The easy part is that a field of $p^n$ elements has a root of unity of $\alpha$ order $k$ (coprime to $p$), iff $k\mid p^n-1$. The degree of the minimal polynomial of $\alpha$ is then the smallest exponent $n$ with that property. – Jyrki Lahtonen Aug 29 '13 at 10:15
• one useful thing: the map $\alpha\mapsto\alpha^p$ (Frobenius automorphism) gives you a permutation of the roots of your polynomial $f$ (they are in some extension of $\mathbb F_p$). The permutation splits to cycles, and that determines the factorization of $f$ to irreducible factors. (This method works nicely for $f=t^n-1$, when it's easy to find the permutation explicitly). – user8268 Aug 29 '13 at 11:04

If the polynomial is reducible in $\mathbb{Z}[x]$, then it is reducible over $\mathbb{F}_p[x]$ for every prime. The converse unfortunately is not true, e.g., $x^4+1$ is irreducible in $\mathbb{Z}[x]$, but reducible over any finite field. On the other hand, if we have a given polynomial in $\mathbb{F}_q[x]$, we can use several algorithms, e.g., the Berlekamp algorithm, to obtain a factorisation into powers of irreducible polynomials. For example, $$x^{37} + 37x + 37$$ is irreducible over a finite field with $103$ elements, but reducible over a field with $101$ elements, namely $$x^{37} + 37x + 37=(x+17)(x^2+9x+99)(x^{34}+ \cdots +91).$$