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?
 A: 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.
