# Finding the elements of a finite field?

How do I find the elements of a finite field.

For example I wanted to find the elements of $\mathbb{F}_4$ and I constructed an addition table for this:

\begin{align}+&&0&&1&&\omega && \omega +1\\0&&0&&1&&\omega&&\omega+1\\1&&1&&0&&1&&0\\\omega&&\omega&&1&&0&&\omega+1\\\omega+1&&\omega+1&&0&&\omega+1&&0\end{align}

But I am unsure how to make the multiplication table here, not the point however.

How would I find the elements for $\mathbb F_p$? The general case for a field of $p$ elements?

• Thinking of $\mathbb{F}_p$ as $\mathbb{Z}/p\mathbb{Z}$ you can write down the multiplication table easily for small $p$. $\mathbb{F}_{p^n}$ with $n \geq 2$, as in your example, probably needs more work. – Hoot Jan 1 '15 at 5:26
• @hoot so when I am dealing with $p$ prime, I am simply dealing with $\Bbb Z_p$, but when $p$ is not prime, it is trickier? – beginner Jan 1 '15 at 5:28
• Because all finite fields* of size $p$ prime, are isomorphic right? *edited whoops – beginner Jan 1 '15 at 5:30
• All finite fields of order $p$ are isomorphic to one another, yes; I don't know much about computational aspects but for $\mathbb{F}_4$, for example, I would probably write it as $\mathbb{F}_2[x]/(x^2 + x + 1)$ and view $\omega$ as the class of $x$ there. On that note, I don't think your table is right — certainly the sum of $\omega$ and $1$ should be $\omega + 1$ and not zero and indeed you already know a solution to the equation $X + 1 = 0$, namely $X = 1$. Just to give an example of multiplication: $\omega(\omega + 1) = \omega^2 + \omega = (-\omega - 1) + \omega = -1 = 1$. – Hoot Jan 1 '15 at 5:35
• @Hoot Yes true, silly me. I was thinking of $\Bbb F_4$ as being built by $\Bbb Z_2$ and $\Bbb Z_2$ and 'cheating' by treating $\omega$ as $0$, but then I realised because it is of characterstic $2$ that $\omega+\omega=0$ and not $\omega+\omega =\omega$ – beginner Jan 1 '15 at 5:39

The finite fields of characteristic $p$ can be constructed by taking all the roots of $t \mapsto t^{p^n} - t$ in some splitting field, and one good choice for the splitting field is $\overline{\mathbb{F}_p}$, the algebraic closure of $\mathbb{F}_p$, so that all these finite fields are contained in the same bigger field and we can then talk about inclusion or intersection or compositum. It is not hard to check that these roots are distinct and form a field, which we call $\mathbb{F}_{p^n}$.

Any finite field $F$ of characteristic $p$ is isomorphic to one of these, because it is a vector space over $\mathbb{F}_p$ and hence $|F| = p^n$ for some $n \in \mathbb{N}$, and its non-zero elements form a multiplicative group and hence they are roots of $t \mapsto t^{|F|-1} - 1$ by Lagrange's theorem. This also shows that $\mathbb{F}_{p^n}$ is the unique finite field within $\overline{\mathbb{F}_p}$ of that size.

This also means that for the finite field $\mathbb{F}_{p^n}$, it is spanned by $n$ elements over $\mathbb{F}_p$. For example $\mathbb{F}_{p^2} = \{ x+ya : x,y \in \mathbb{F}_p \}$ for any $a \in \mathbb{F}_{p^2} \backslash \mathbb{F}_p$.

Similarly $\mathbb{F}_{p^2} = \{ x+yr : x,y \in \mathbb{F}_p \}$ for any $r \in \overline{\mathbb{F}_p}$ such that $f(r) = 0$ for some irreducible quadratic polynomial $f \in \mathbb{F}_p[t]$, because $[\mathbb{F}_p(r):\mathbb{F}_p] = 2$ and hence $\mathbb{F}_p(r) \cong \mathbb{F}_{p^2}$ and so $\mathbb{F}_p(r) = \mathbb{F}_{p^2}$.

In general, $\mathbb{F}_{p^n} = \mathbb{F}_p(r) = \{ \sum_{k=0}^{n-1} a_k r^k : \forall k \in [0..n-1]\ ( a_k \in \mathbb{F}_p ) \}$ for some $r \in \overline{\mathbb{F}_p}$ such that $f(r) = 0$ for some irreducible degree-$n$ polynomial $f \in \mathbb{F}_p[t]$, because $[\mathbb{F}_p(r):\mathbb{F}_p] = n$ and so $\mathbb{F}_p(r) = \mathbb{F}_{p^n}$. The problem now reduces to finding just one irreducible polynomial of degree $n$, which can be done via factorizing $t \mapsto t^{p^n}-t$ over $\mathbb{F}_n$, since at least one factor is guaranteed to have degree $n$ because there is an element in $\mathbb{F}_{p^n} \backslash \bigcup_{k=1}^{n-1} \mathbb{F}_{p^k}$ and so it must have a degree-$n$ minimal polynomial over $\mathbb{F}_p$, which must be a divisor of $t \mapsto t^{p^n}-t$.

For example, to get $\mathbb{F}_{2^3}$ we can factorize $t^8-t$ over $\mathbb{F}_2$ to get $t(t+1)(t^3+t+1)(t^3+t^2+1)$. So we could use either of the two irreducible cubics as the modulus and take the quadratic polynomials over $\mathbb{F}_2$ to represent the elements of $\mathbb{F}_{2^3}$, where arithmetic is the usual one for polynomials but modulo the cubic. The inverse of any non-zero element can also be efficiently computed by finding the gcd of it and the cubic expressed as a linear combination of both, as in the standard Euclidean algorithm.

A degree-$p^n$ polynomial may not be easy to factor for large $p,n$, so probably there are better ways to get an irreducible polynomial of the desired degree, but I don't know off-hand such methods.

• I'm guessing you may not understand many terms I've used, which come from a field of mathematics called Galois theory. If you are interested you can look at maths.manchester.ac.uk/%7Ekhudian/Teaching/Galois/… or if you already know some ring theory you can look at jchl.co.uk/maths/Galois.pdf. – user21820 Jan 1 '15 at 8:06
• I'll accept this when I understand it, so that might be a few weeks still. thanks for the long answer – beginner May 17 '15 at 8:13
• @beginner: You're welcome! Feel free to ask about any part of my answer that is not too clear. – user21820 May 18 '15 at 4:57