Extension Field

The real numbers \(\mathbb{R}\) have no solution to \(x^2 + 1 = 0\). Instead of giving up, we adjoin a root: declare \(i\) to be a symbol satisfying \(i^2 = -1\), then build the smallest field containing \(\mathbb{R}\) and \(i\). Every element takes the form \(a + bi\) with \(a, b \in \mathbb{R}\). This is \(\mathbb{C}\), an extension of \(\mathbb{R}\).

Extension fields generalize exactly this idea to any base field \(F\) and any irreducible polynomial over \(F\).

Given a field \(F\) and an irreducible polynomial \(f(x)\) of degree \(n\) with coefficients in \(F\):

1. \(f(x)\) has no roots in \(F\), so we cannot factor it there.
2. Introduce a formal symbol \(\alpha\) and declare it to be a root: \(f(\alpha) = 0\).
3. The extension field \(K = F(\alpha)\) is the set of all polynomials in \(\alpha\) with coefficients in \(F\), where any power \(\alpha^k\) with \(k \ge n\) is replaced using the relation \(f(\alpha) = 0\).

Every element of \(K\) looks like: \[a_0 + a_1 \alpha + a_2 \alpha^2 + \cdots + a_{n-1} \alpha^{n-1}, \quad a_i \in F\]

\(K\) has \(|F|^n\) elements and the degree of the extension is \([K : F] = n\).

• Addition: add coefficient-wise using arithmetic in \(F\).
• Multiplication: multiply polynomials normally, then reduce any power \(\alpha^k\) with \(k \ge n\) back into the basis \(\{1, \alpha, \ldots, \alpha^{n-1}\}\) using the relation \(f(\alpha) = 0\).

The key reduction rule comes from rearranging \(f(\alpha) = 0\) to express \(\alpha^n\) in terms of lower powers.

Start with \(F = \mathbb{Z}_2 = \{0, 1\}\). The polynomial \(f(x) = x^2 + x + 1\) is irreducible over \(\mathbb{Z}_2\) since neither \(0\) nor \(1\) is a root.

Adjoin a root \(\alpha\) satisfying \(\alpha^2 + \alpha + 1 = 0\). Rearranging: \(\alpha^2 = \alpha + 1\) (since \(-1 = 1\) in \(\mathbb{Z}_2\)). This is the reduction rule for any product that produces \(\alpha^2\).

The four elements of \(GF(4)\) are: \(\{0,\ 1,\ \alpha,\ \alpha + 1\}\).

Sample multiplication: \(\alpha \cdot (\alpha + 1) = \alpha^2 + \alpha = (\alpha + 1) + \alpha = 1\).

\(GF(q)\), or the Galois Field of order \(q\) (named after Évariste Galois), is the unique finite field with \(q\) elements. A finite field of order \(q\) exists if and only if \(q = p^n\) for some prime \(p\) and positive integer \(n\).

\(GF(p)\) is just \(\mathbb{Z}_p\) (integers mod \(p\)). \(GF(p^n)\) for \(n > 1\) is constructed as an extension of \(GF(p)\) by adjoining a root of an irreducible polynomial of degree \(n\) over \(GF(p)\).

All such constructions yield the same field up to relabeling of elements, so \(GF(q)\) is unique. However, the choice of irreducible polynomial affects how elements are represented. For small cases like \(GF(4)\), there is only one irreducible polynomial of the required degree to choose from, so the representation is forced. For larger cases like \(GF(8) = GF(2^3)\), multiple irreducible polynomials of degree 3 exist over \(GF(2)\) (e.g. \(x^3 + x + 1\) and \(x^3 + x^2 + 1\)), and any of them works.