# Determine and construct irreducible polynomial (of degree >3) over finite fields.

Wanted to determine whether a polynomial $x^p+...+a_0$ was irreducible.

The common sense came from that

A polynomial of degree two or three over a field F was irreducible if and only if it had a root in $F$.

and

A monic polynomial with integer coefficients and $p(d)\neq0$ for all integer dividing the constant term of $p(x)$, then $p(x)$ had no root in $Q$.

However, the first one only limited in polynomial of degree 2 or 3. The second one, like Eisenstein's Criterion and many others, was in $\mathbb{Z}[x]$ or UFDs.

I also read an article in Construction of Irreducible Polynomials over Finite Fields and the procedure was way too messy, and the remaining option seemed to actually calculated out all the possible outcomes.

My question was that:

1. Was there any theorems to determine polynomials irreducible or not in a finite field? (Especially, monic polynomials of degree 4 -6.)

2. Was there any other general procedure to create irreducible polynomials?

• I once ran Berlekamp's algorithm by hand to prove that a polynomial was irreducible. No transformation was allowing Eisenstein, so I got rid of it that way. Last resource, I would say. – user550929 Apr 12 '18 at 1:19
• For practical purposes, use a computer algebra system such as Maple, which has quite efficient irreducibility tests for polynomials over finite fields. If you generate a random monic polynomial of degree $d$ over the field of order $p^m$, the probability of its being irreducible is, I think, $1/d + O(p^{-dm/2})$. – Robert Israel Apr 12 '18 at 2:03

To find all irreducible polynomials of degree $n$ over $\mathbb F_p$, factor $x^{p^n}-x$ mod $p$. See an example here.
• +1 thank you for the help. I was also wondering if there was some way to get around with the coefficients as a short cut. i.e. $x^4+1$ was irreducible in $Z/3Z$. I wanted to know if we could in general to determine weather some simple polynomials such as $x^p++x+1$ was irreducible or not. (Notice that $1+x+$...$+x^{p-1}$ was irreducible in $Q[x]$ but can we find some similar trick to deal with them in finite fields?) – user416486 Apr 12 '18 at 1:34
Not a general method by any means, but here’s how to determine that $X^4+1$ is irreducible over $\Bbb F_3$:
Notice that you’re asking for a fourth root of $-1$, in other words, for an eighth root of unity. This means you’re looking for a field $\Bbb F_q$, $q=3^m$, such that $8|(q-1)$. In this case, you’re looking for the smallest power $q=3^m$ of three such that $3^m\equiv1\pmod8$. That’s the fourth power, of course, and this means that if $\rho$ is a root of $X^4+1$, then $[\Bbb F_3(\rho):\Bbb F_3]=4$. In other words, $X^4+1$ is the minimal polynomial for $\rho$ over $\Bbb F_3$. So irreducible.
You can use this method to determine just how the $n$-th cyclotomic polynomial $\Phi_n(X)$, which is $\Bbb Z$-irreducible, splits over $\Bbb F_q$, for any prime power $q$ that’s relatively prime to $n$.