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

Question

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?

Answer 1

There are a few general algorithms for factoring polynomials over a finite field; see Wikipedia.

To find all irreducible polynomials of degree $n$ over $\mathbb F_p$, factor $x^{p^n}-x$ mod $p$. See an example here.

Answer 2

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$.