As per <classification of finite fields> those must be of <prime power> order.

<video Finite fields made easy by Randell Heyman (2015)> at https://youtu.be/z9bTzjy4SCg?t=159 shows how for order $9 = 3 \times 3$. Basically, for order $p^n$, we take:
* each element is a polynomial in $GF(p)[x]$, $GF(p)[x]$, the <polynomial over a field>[polynomial ring over the finite field $GF(p)$] with degree smaller than $n$. We've just seen how to construct $GF(p)$ for prime $p$ above, so we're good there.
* addition works element-wise modulo on $GF(p)$
* multiplication is done modulo an <irreducible polynomial> of order $n$
For a worked out example, see: <GF(4)>.


Finite field of non-prime order

{c}
{wiki}

<Ciro Santilli> tried to https://en.wikipedia.org/w/index.php?title=Finite_field&type=revision&diff=1044934168&oldid=1044905041[add this example to Wikipedia], but it was reverted, so here we are, see also: <Deletionism on Wikipedia>{full}.

This is a good first example of a field of a <finite field of non-prime order>, this one is a <prime power> order instead.

$4 = 2^2$, so one way to represent the elements of the field will be the to use the 4 polynomials of degree 1 over <GF(2)>:
* 0X + 0
* 0X + 1
* 1X + 0
* 1X + 1

Note that we refer in this definition to anther field, but that is fine, because we only refer to fields of <prime> order such as <GF(2)>, because we are dealing with <prime powers> only. And we have already defined fields of prime order easily previously with <modular arithmetic>.

Over GF(2), there is only one <irreducible polynomial> of degree 2:
$$
X^2+X+1
$$

Addition is defined element-wise with <modular arithmetic> modulo 2 as defined over GF(2), e.g.:
$$
(1X + 0) + (1X + 1) = (1 + 1)X + (0 + 1) = 0X + 1
$$

Multiplication is done modulo $X^2+X+1$, which ensures that the result is also of degree 1.

For example first we do a regular multiplication:
$$
(1X + 0) \times (1X + 1) = (1 \times 1)X^2 + (1 \times 1)X + (0 \times 1)X + (0 \times 1) = 1X^2 + 1X + 0
$$

Without modulo, that would not be one of the elements of the field anymore due to the $1X^2$!

So we take the modulo, we note that:
$$
1X^2 + 1X + 0 = 1(X^2+X+1) + (0X + 1)
$$
and by the definition of modulo:
$$
(1X^2 + 1X + 0) \mod (X^2+X+1) = (0X + 1)
$$
which is the final result of the multiplication.

TODO show how taking a reducible polynomial for modulo fails. Presumably it is for a similar reason to why things fail for the prime case.


Ciro Santilli @cirosantilli 34

 Incoming links: Irreducible polynomial