Galois Fields
We have already looked at some examples of fields on the Field Axioms page. We will now look at another specific type of field known as a Galois Field. Before we do that though, we must first get a little bit acquainted to a special type of relation known as the modulus of an integer $a$ to a divisor $m$.
| Definition: Let $a$ be an integer. Then we write $r = a \pmod m$ which says that $r$ is the remainder of $a$ when $a$ is divided $m$, that is for some positive integer $k$ we have that $a = km + r$. |
For example, consider $7 \pmod 3$. We note that $1 = 7 \pmod 3$ since when $7$ is divided by $3$ we have a remainder of $1$, and so $7 = 2(3) + 1$. We are now ready to define what a Galois field is.
| Definition: A Galois Field of the prime number $p$ denoted $GF(p)$ or $\mathbb{Z}_p$ is a set containing the nonnegative integers $0, 1, 2, ..., p - 1$ whose operation of addition between any two elements $a, b \in GF(p)$ is defined by $a + b \pmod p$ and whose multiplication is defined as $a \cdot b \pmod p$. |
The simplest Galois Field is $GF(2)$ whose addition and multiplication tables are given below.
| $+$ | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
| $\cdot$ | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
We can verify that all eleven axioms of a field hold for $GF(2)$. For example, commutativity of addition and multiplication can be observed on both tables since the tables have symmetric values upon the top-left to top-right diagonal.
Example 1
Write the addition table for $GF(5)$ and verify that an additive identity $0$ exists such that $\forall a \in GF(5)$ that $a + 0 = 0 + a = a$
The addition table for $GF(5)$ is as follows where the red column and row verifies that $0$ is the identity element of $GF(5)$.
| $+$ | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | 4 | 0 |
| 2 | 2 | 3 | 4 | 0 | 1 |
| 3 | 3 | 4 | 0 | 1 | 2 |
| 4 | 4 | 0 | 1 | 2 | 3 |
Example 2
Write down the multiplication table for $GF(3)$ and verify that multiplication is commutative.
The multiplication table for $GF(3)$ is as follows. The commutativity of multiplication is represented by the symmetry across the diagonal of this multiplication table, that is for all $a, b \in GF(3)$, $a \cdot b = b \cdot a$.
| $\cdot$ | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 |
| 2 | 0 | 2 | 1 |
Example 3
Explain why $GF(4)$ does not form a field.
In this case we note that $p = 4$ is not a prime number. When we write the addition table for $GF(4)$ we get that:
| $+$ | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 2 | 3 | 0 |
| 2 | 2 | 3 | 0 | 1 |
| 3 | 3 | 0 | 1 | 2 |
So nothing is wrong with addition. We can verify that all of the addition axioms hold. The reason why $GF(4)$ does not form a field actually lies within the operation of multiplication.
| $\cdot$ | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 |
| 2 | 0 | 2 | 0 | 2 |
| 3 | 0 | 3 | 2 | 1 |
We first note that $1$ is the multiplicative identity. Suppose that we are given the element $2$ and want to find its multiplicative inverse $b$ such that $2b = 1$. If we look down the column/row containing $2$ we notice that no such element exists since $2b = 0$ or $2b = 2$ for all $b \in GF(4)$. Therefore not all elements in $GF(4)$ contain multiplicative inverses and so $GF(4)$ is not a field.