Irreducible polynomials of degree greater than 4 over finite fields

Question

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 $\leq$ 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?

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.