Introduction
Throughout calculus and continuous optimization, we rely on infinite fields like the real numbers \(\mathbb{R}\) or
complex numbers \(\mathbb{C}\). However, in digital computing, continuous numbers are often approximated using floating-point
arithmetic, which inherently introduces precision loss. When we require an algebraic structure where addition, subtraction,
multiplication, and division are exact and bounded within a discrete memory space, we must turn to finite structures.
Enter finite fields, also known as Galois fields (denoted \(GF(q)\)), named after the French
mathematician Évariste Galois. Finite fields are the crown jewel of abstract algebra for computer scientists. Because they possess
exactly a finite number of elements, operations never "overflow" into infinity or require decimals. This absolute precision makes
finite fields the indestructible mathematical engine powering modern cryptography (like the AES standard), error-correcting codes
(like those in QR codes), and digital signal processing.
Classification
A fundamental question arises: for which integers \(q\) does a field of exactly \(q\) elements exist? For instance,
can we construct a field with exactly 10 elements to naturally map to our decimal system? The answer is determined by
the Classification Theorem, which tightly constrains the possible sizes of finite fields to prime powers.
Theorem: Classification of Finite Fields
Every finite field has prime-power order. Moreover, for each prime \(p\) and each positive integer \(n\),
there exists a unique finite field of order \(p^n\) up to isomorphism.
This theorem dictates that a field of size 10 is mathematically impossible, as 10 is not a prime power. Conversely,
it guarantees the existence of a unique field of size \(2^8 = 256\).
This structural guarantee is highly consequential for computing. Because an 8-bit byte inherently has 256 distinct states,
we can map any byte directly to an element in \(GF(2^8)\). This algebraic mapping enables cryptographic algorithms to securely
add, multiply, and compute inverses of bytes without ever exceeding the 8-bit space constraint.
Structure
To utilize \(GF(p^n)\) effectively, we must understand the behavior of its elements under algebraic operations.
The following theorem explicitly defines the underlying group structures of a finite field.
Theorem: Structure of Finite Fields
As a group under addition, \(GF(p^n)\) is isomorphic to
\[
\underbrace{\mathbb{Z}_p \oplus \mathbb{Z}_p \oplus \ldots \oplus \mathbb{Z}_p}_{n \text{ factors }}.
\]
As a group under multiplication, the set of nonzero elements of \(GF(p^n)\) is isomorphic to \(\mathbb{Z}_{p^n - 1}\)
and is cyclic.
Proof:
By Characteristic of a Ring with Unity, \(GF(p^n)\) has characteristic \(p\).
Thus, every nonzero element of \(GF(p^n)\) has additive order \(p\).
Then by the Fundamental Theorem of Finite Abelian Groups, \(GF(p^n)\) under
addition is isomorphic to a direct product of \(n\) copies of \(\mathbb{Z}_p\).
To see that the multiplicative group \(GF(p^n)^*\) of nonzero elements of \(GF(p^n)\) is cyclic, we first note that
by the Fundamental Theorem of Finite Abelian Groups, \(GF(p^n)^*\) is isomorphic to a direct product of the form:
\[
\mathbb{Z}_{n_1} \oplus \mathbb{Z}_{n_2} \oplus \ldots \oplus \mathbb{Z}_{n_m}.
\]
If the orders of these components are pairwise relatively prime, then it follows from
Criterion for \(G_1 \times G_2 \times \cdots \times G_n\) to be Cyclic
that \(GF(p^n)^*\) is cyclic.
Assume for the sake of contradiction that they are not pairwise relatively prime. Then there exists an integer \(d > 1\) that
divides the orders of at least two of the components. From the
Fundamental Theorem of Cyclic Groups, we know that each of these
components has a unique subgroup of order \(d\).
This means that the overall group \(GF(p^n)^*\) contains at least two distinct subgroups, \(H\) and \(K\), both of order \(d\).
Since \(H \neq K\), the union \(H \cup K\) contains strictly more than \(d\) elements. However, every element in both \(H\) and \(K\)
satisfies the equation \(x^d = 1\), meaning they are all roots of the polynomial \(x^d - 1\).
This yields strictly more than \(d\) roots for a polynomial of degree \(d\). This contradicts the theorem from
Part 21: Polynomial Rings, which states that a polynomial of
degree \(d\) over a field can have at most \(d\) roots. Thus, the components must be pairwise relatively prime, and \(GF(p^n)^*\) is cyclic.
We have established both claims of the theorem. The additive group is isomorphic to the direct product of \(n\) copies of \(\mathbb{Z}_p\), and
the multiplicative group of nonzero elements is isomorphic to \(\mathbb{Z}_{p^n-1}\) and is therefore strictly cyclic.
The Additive Structure:
The additive group indicates that elements of \(GF(p^n)\) can be treated as \(n\)-dimensional vectors over \(\mathbb{Z}_p\).
When \(p=2\) (the binary case), polynomial addition modulo 2 is equivalent to the bitwise XOR operation.
This allows for highly efficient hardware implementations, as addition in \(GF(2^n)\) requires no carry propagation.
Caution: Component-wise Multiplication is NOT a Field
It is important to understand that the isomorphism to \(\mathbb{Z}_p \oplus \ldots \oplus \mathbb{Z}_p\) applies only to addition.
If we attempted to multiply these vectors component-wise, the resulting structure would fail to be a field.
Why? Because in a field, every nonzero element must have a multiplicative inverse. But under component-wise multiplication, any vector that has at
least one coordinate equal to \(0\) (but is not the all-zero vector) can never be multiplied by anything to reach the identity element \((1, 1, \ldots, 1)\).
Furthermore, it creates zero-divisors. For example, in \(\mathbb{Z}_2 \oplus \mathbb{Z}_2\):
\[
(1, 0) \times (0, 1) = (0, 0)
\]
Because fields cannot contain zero-divisors, \(GF(p^n)\) must use a completely different rule for multiplication—specifically, polynomial multiplication
modulo an irreducible polynomial—to ensure every nonzero element has an inverse.
The Multiplicative Structure:
Because the multiplicative group is cyclic, there exists at least one generator (primitive element) \(g\). Every nonzero element
in the field can be expressed as \(g^k\) for some integer \(k\). This predictable cyclic behavior forms the mathematical basis for
discrete logarithm cryptography, such as the Diffie-Hellman key exchange algorithm.
Insight: Maximum-Period PRNGs
The cyclic nature of the multiplicative group provides the exact mathematical foundation for Pseudo-Random Number Generators (PRNGs).
Machine learning relies heavily on high-quality PRNGs for weight initialization, Dropout layers, and Stochastic Gradient Descent (SGD).
Fast random number generators, such as Linear Feedback Shift Registers (LFSRs) and the famous Mersenne Twister, operate via polynomial
arithmetic over \(GF(2)\). Because this theorem guarantees the existence of a "primitive element" (generator), we can strictly design
state transitions that multiply by this generator, forcing the internal state to visit every single non-zero element in \(GF(2^n)\)
exactly once before repeating.
This guarantees a sequence with the maximum possible period length (e.g., \(2^n - 1\)). Without this cyclic property ensuring a maximal
period, random generators would fall into short, predictable loops, introducing statistical correlations that severely degrade the
convergence and generalization of neural networks.
Corollary: Degree of \(GF(p^n)\)
\[
[GF(p^n): GF(p)] = n.
\]
Corollary: \(GF(p^n)\) Contains an Element of Degree \(n\)
Let \(a\) be a generator of the group of nonzero elements of \(GF(p^n)\) under multiplication. Then
\(a\) is algebraic over \(GF(p)\) of degree \(n\).
These corollaries connect finite fields directly to the theory of Algebraic Extensions. Just as \(\mathbb{C}\) is constructed
by adjoining a root of an irreducible polynomial to \(\mathbb{R}\), \(GF(p^n)\) is constructed by taking an irreducible
polynomial of degree \(n\) over \(\mathbb{Z}_p\) and adjoining its root.
Theorem: Zeros of an Irreducible over \(\mathbb{Z}_p\)
Let \(f(x) \in \mathbb{Z}_p[x]\) be an irreducible polynomial over \(\mathbb{Z}_p\) of degree \(d\) and let
\(a\) be a zero of \(f(x)\) in some extension field \(E\) of \(\mathbb{Z}_p\). Then \(a, a^p, a^{p^2}, \ldots, a^{p^{d-1}}\)
are the zeros of \(f(x)\) and they are distinct.
Corollary: Splitting Field of an Irreducible Polynomial Over \(\mathbb{Z}_p\)
If \(f(x)\) is an irreducible polynomial over \(\mathbb{Z}_p\) and \(a\) is a zero of \(f(x)\) in some extension field
of \(\mathbb{Z}_p\), then \(\mathbb{Z}_p(a)\) is the splitting field of \(f(x)\) over \(\mathbb{Z}_p\).
This reveals a remarkable property of fields of characteristic \(p\): if one root \(a\) of an irreducible polynomial is known,
the remaining roots are generated simply by repeatedly taking the \(p\)-th power. The mapping \(x \mapsto x^p\) is a field
automorphism known as the Frobenius automorphism, which plays a critical role in polynomial factorization
algorithms over finite fields.
Subfields
Just as we can track the dimensions of vector spaces, we can track how smaller finite fields nest inside larger ones.
This creates a highly structured "lattice" of fields, which is heavily utilized when optimizing cryptographic hardware
to save space and power.
Theorem: Subfields of a Finite Field
For each divisor \(d\) of \(n\), \(GF(p^n)\) has a unique subfield of order \(p^d\). Moreover,
these are the only subfields of \(GF(p^n)\).
For instance, does \(GF(2^8)\) contain a subfield of size \(2^4\)? Yes, because 4 divides 8. Does it contain a subfield of size \(2^3\)?
No, because 3 does not divide 8. This strict divisibility condition defines the exact structural dependencies within the field.
Theorem: Degrees of Irreducible Factors of \(x^{p^n} - x\) over \(\mathbb{Z}_p\)
The degree of an irreducible factor of \(x^{p^n} - x\) over \(\mathbb{Z}_p\) divides \(n\).
The polynomial \(x^{p^n} - x\) completely characterizes the elements of \(GF(p^n)\). As a consequence of Lagrange's theorem on
the multiplicative group, every element in \(GF(p^n)\) is a root of this exact polynomial. Thus, \(x^{p^n} - x\) factors into
the product of all monic irreducible polynomials over \(\mathbb{Z}_p\) whose degrees divide \(n\). This theorem elegantly ties
together the concepts of polynomial factorization, extension degrees, and field sizes into one unified algebraic structure.