How to construct finite fields of any prime power order?

Question

For a prime $p$, I know that $\mathbb Z_p$ is a field. To construct a field with four elements, I know I can just take $\frac{\mathbb Z_2[x]}{(x^2+x+1)}$. Similarly, to construct a field of order $p^n$, do I just need to take $\mathbb Z_p[x]$ and quotient out an irreducible polynomial of degree $n$? Is there any pattern to these irreducible polynomials, or do I just have to find one by brute force?

Answer 1

I don't think there is any general procedure to find an irreducible polynomial of degree $n$ over $\mathbb{Z}_p$. However, any such polynomial $p(x)$ works, i.e. it will produce a field $\mathbb{Z}[x]/(p(x))$ of order $p^n$.

Answer 2

If you want to "construct" such fields, when $n$ is a power of 2, and $p \neq 2$, you can do the following:

• Start with a field with $p$ elements.
• Such a field will always have an element that does not have a square roots. Let it be $Q$.
• Construct a field with $p^2$ elements with each element given by $a + \sqrt{Q} b$ where $a$ and $b$ are elements in the field

Above procedure can be repeated as many times as needed. If you write computer programs, or you want a concrete representation that does not involve square roots then you can set up an isomorphism between the new field and a subset of $2\times 2$ matrices in the original field as $$ a + \sqrt{Q} b \leftrightarrow \begin{pmatrix} a & b \\ Q^2 b & a \end{pmatrix} $$

This will allow you to do all your work in the base field (also very useful if you want to write computer programs and don't mind being a bit inefficient).