Constructing finite fields of order $8$ and $27$ or any non-prime

Question

I want to construct a field with $8$ elements and a field with $27$ elements for an ungraded exercise.

---

For $\bf 8$ elements: So we can't just have $\Bbb Z/8\Bbb Z$ since this is not even an integral domain. But rather we can construct $\Bbb F_2 \oplus \Bbb F_2 \oplus\Bbb F_2 \oplus \Bbb F_2 = \{0,1,\alpha,\alpha+1,\beta,\beta+1,\gamma,\gamma+1\}$.

This line of thinking seems to break from what I tried. Is there a better way to construct these things?

I saw this answer: Construct a finite field of order 27

We pick a polynomial irreducible polynomial and take the quotient of $\Bbb Z_3[x]$ but this wasn't helpful in me understanding the general ideal/method.

Answer 1

Let $p$ be some prime and $k$ some natural exponent.

The field $\mathbb F_{p^k}$ can be thought of as a splitting field of $χ = X^{p^k} - X$ over $\mathbb F_p$.

There is a general way to construct splitting fields for any set of polynomials, in your case you just repeatedly construct $F[X]/(f)$ for some irreducible non-linear factor $f$ of $χ$ and some field $F$ you wish to extend. You start with $F = \mathbb F_p$, see here.

Answer 2

There are two ways you might want to represent a field of order $q^k$ (where $q\in \mathbb{N}$ is a prime and $k \gt 0$ a positive integer).

One is to imagine a simple algebraic field extension of $\mathbb{Z}_q$ which has a basis $\{1,\alpha,\ldots,\alpha^{k-1}\}$, namely $\mathbb{Z}_q[\alpha]$ where $\alpha$ satisfies an irreducible monic polynomial of degree $k$ over $\mathbb{Z}_q$:

$$ \alpha^k + c_1 \alpha^{k-1} + \ldots + c_{k-1}\alpha + c_k = 0 $$

Any element of this field extension can be represented in terms of the basis, and the addition is just the same as the addition of the $k$-dimensional vector space over $\mathbb{Z}_q$. But when we multiply, we have to perform substitutions to eliminate powers $\alpha^k$ and higher by using:

$$ \alpha^k = - c_1 \alpha^{k-1} - \ldots - c_{k-1}\alpha - c_k $$

The other way to think about it is to start with an irreducible polynomial $p(x)$ of degree $k$ over $\mathbb{Z}_q$ and construct $\mathbb{Z}_q[x]/p(x)$ as a quotient ring. Since the ideal generated by $p(x)$ is maximal, the quotient ring is a field and has dimension $k$ over $\mathbb{Z}_q$ as a vector space.

These two constructions are equivalent, with $\alpha$ being a root of:

$$ p(x) = x^k + c_1 x^{k-1} + \ldots + c_{k-1}x + c_k $$

and identified with $x \bmod{p(x)}$ in $\mathbb{Z}_q[x]/p(x)$.

It turns out that all field extensions of degree $k$ over $\mathbb{Z}_q$ are isomorphic, so as a computational convenience the irreducible polynomial $p(x)$ may be chosen to be simple in some way (e.g. having as few nonzero coefficients as possible).

It's not hard to come up with a monic irreducible polynomial of degree $3$ over $\mathbb{Z}_2$ in order to construct a field of $8$ elements. You only need to check for divisibility by linear (first degree) factors to be sure of irreducibility.

Answer 3

Use Zech logarithms. For primitive a, compute 1+a^k = a^Z(k). See Collected Algorithms of the ACM 1973 Lam and McKay. Arithmetic over a finite field. Number 469.