Finite fields, or Galois fields*, are a crucial and intriguing concept in mathematics (mathematical spaces, finite numbers) and have practical applications in computer science, cryptography and many other fields.
Let's start by demystifying these concepts in an accessible way.
Imagine a world where everything operates in binary fashion:
switches can only exist as either on or off.
This forms the foundation of the Finite Field $GF(2)$. Here, all mathematical operations are performed with just two digits: 0 and 1.
For instance, addition in $GF(2)$ is akin to the XOR operation, where similar states result in 0 and dissimilar states yield 1.
In other terms, $GF(2)$ is isomorphic to XOR operations. We can say that XOR operations mimic the addition operations within $GF(2)$.
Multiplication in $GF(2)$ operates similarly to the logical AND operation. It's as if two switches are in series: the circuit is on only when both switches are on.
Now, let's do $GF(3)$, where arithmetic is based on modulo 3 operations. Here, numbers range from 0 to 2, and when 3 is reached, it cycles back to 0 (as you would read the time on a clock).
In $GF(3)$, multiplication also follow modulo 3 rules.
These operations satisfy the properties of a ring and an abelian group. But what the hell does it means ?
For short, we just need to verify that the properties of closure, associativity, commutativity, distributivity, the existence of an identity element, and the presence of an inverse for each non-zero element are satisfied.
Let's prove the properties for both $GF(2)$ and $GF(3)$.
Both addition and multiplication are trivially associative for elements in $GF(2)$.
Addition and multiplication both commute in $GF(2)$ trivially.
$a * (b + c) = a * b + a * c$ holds true for all $a, b, c$ in $GF(2)$.
0 acts as the additive identity: $0 + x = x$ for all $x$ in $GF(2)$.
Additive inverses: 0 is its own inverse, and 1 is its own inverse in $GF(2)$.
Addition and multiplication are both associative for elements in $GF(3)$.
Both addition and multiplication commute in $GF(3)$.
$a * (b + c) = a * b + a * c$ holds true for all $a, b, c$ in $GF(3)$.
0 acts as the additive identity: $0 + x = x$ for all $x$ in $GF(3)$.
Every non-zero element in $GF(3)$ has an additive inverse:
PFFFIOU! DONE!
So, we just proved that $GF(2)$ and $GF(3)$ are indeed fields, since they are respectively a ring and an abelian group.
Take your time, pause and ponder to understand the properties of each concept and why it is verified with $GF(2)$ and $GF(3)$.
Finite Fields can be extended to any prime number or a power of prime numbers ($GF(p)$ and $GF(q)$).
Often, these fields are represented using polynomials.
$GF(p)$ and $GF(q)$ enable advanced arithmetic calculations used in various domains such as telecommunications, error-correcting codes, and other advanced mathematical applications.
For $GF(p)$ with $p$ being a prime number, the elements are $\{0, 1, 2, ..., p-1\}$.
The operations of addition and multiplication are performed modulo $p$.
For instance, in $GF(3)$ (since now you are pro with $GF(3)$), the elements are $\{0, 1, 2\}$, and arithmetic operations are performed modulo 3.
However, when dealing with $GF(q)$, where $q$ is not necessarily a prime but a power of a prime, the representation is slightly different (and harder).
$GF(q)$ involves a finite field with $q$ elements, and the elements are represented using polynomials over $GF(p)$, where $p$ is the prime base.
For example, $GF(4)$ is not $\{0, 1, 2, 3\}$ because it is constructed as $$GF(2^2)$$, not as a simple extension of integers up to 4.
It's based on the polynomial representation over $GF(2)$ (binary field).
The elements in $GF(4)$ are represented as polynomials modulo an irreducible polynomial of degree 2 over $GF(2)$.
Specifically, the elements of $GF(4)$ are: $$\{0, 1, α, α + 1\}$$where α is a root of an irreducible polynomial, for instance: $$α^2 + α + 1 = 0 \pmod 2$$
In this case, the operations are performed using polynomial arithmetic modulo this irreducible polynomial.
Addition and multiplication of elements in $GF(4)$ are carried out using polynomial operations with coefficients in $GF(2)$ and reduction modulo the chosen irreducible polynomial to keep the result within the field of GF(4).
*. Unambiguously denoted ${\mathbb {F}}_{{q}}$, $\mathbf{F_q}$ or $GF(q)$, where the letters $GF$ stand for "Galois field".