# Irreducible polynomials of degree greater than 4 over finite fields

I want to build a field with p^n elements. I know that this can be done by finding a irreducible (on Z_p) polynomial f of degree n and the result would be the Z_p/f. My question is finding this irreducible polynomial. I know that if it has degree <= 3, then it's irreducible iff it has no roots. But what if I want to construct a field with 81 = 3^4 elements? How can I find an irreducible polynomial of degree 4?

• For low degrees the best techniques are a bit ad hoc, not unlike Rene Schoof's answer (+1). I have used similar techniques to produce irreducibles of degree 20 and 21 (over $\Bbb{Z}_2$) on this site when requested. In general the task takes as much work as producing a prime number of a prescribed size. The tricks based on the algebra of roots of unity as well as splitting fields does simplify this in many occasions. – Jyrki Lahtonen Jan 2 at 5:39
• An alternative to Rene Schoof's observation would be to use the fact that $\Bbb{F}_{3^4}$ is the smallest extension field containing roots of unity of order sixteen. Those are always roots of the sixteenth cyclotomic polynomial $\Phi_{16}=x^8+1$. Over $\Bbb{F}_3$ that polynomial factors as $$x^8+1=(x^8+4x^4+4)-4x^4=(x^4+2)^2-(2x^2)^2=(x^4-2x^2+2)(x^4+2x^2+2),$$ so we can deduce right away that the quartics above are irreducible. – Jyrki Lahtonen Jan 2 at 5:45
• Hmm. Actually I don't think that this task would be asymptotically as arduous as that of locating prime numbers. But you need methods other than the Sieve of Eratosthenes (which is what Ethan Bolker's answer is suggesting). – Jyrki Lahtonen Jan 2 at 5:48

Find the irreducible quadratics. Multiply them together. Those fourth degree polynomials won't do. Now try some others at random (or systematically, following a list in some natural order). When you find one with no roots you're done.

This is mildly tedious, but you'll get good at the arithmetic, which may come in handy in other computations in the future.

You can also ask Wolfram alpha to factor polynomials modulo $$3$$.

• Asymptotically, a random monic polynomial of degree $n$ over $\Bbb{Z}_p$ is irreducible with probability $1/n$. – Jyrki Lahtonen Jan 2 at 5:33

Since $$3$$ is a primitive root modulo $$5$$, the fifth roots of unity are in $${\bf F}_{81}$$, but not in a proper subfield. This means that the cyclotomic polynomial $$\Phi_5(X)=X^4+X^3+X^2+X+1$$ is irreducible modulo $$3$$.

The elements of $$GF(p^n)$$ are the zeros of the polynomial $$x^{p^n}-x$$. This polynomials decomposes into irreducible polynomials of degree $$d$$ over $$GF(p)$$ where $$d$$ divides $$n$$. It can be shown that this decomposition contains at least one polynomial of degree $$n$$ which ensures the existence of a finite field with $$p^n$$ elements. In a CAS you usually have access to such irreducible polynomials.

I think the state of the art is Couveignes, J. M., & Lercier, R. (2013). Fast construction of irreducible polynomials over finite fields. Israel Journal of Mathematics, 194(1), 77-105. A preprint is available on arxiv.

If you want something simpler but better than brute force, you could look at Victor Shoup's work from the 1990s. Shoup, V. (1990). New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54(189), 435-447 is not the most recent, but is freely available online, unlike the follow-up.

Obviously both of these also serve as starting points for a literature search.

• +1 for the references – Jyrki Lahtonen Jan 2 at 5:40