Describe the construction of a field with eight elements.
Solution
Note that \(8=2^3\) is a prime power \(p^n\), so we can get this as a quotient of a polynomial algebra. In particular, since \(p=2\), we’ll want to look at \(\FF_2[t]\), and we’ll want to quotient it by a polynomial of degree \(n=3\) that is irreducible in the base field \(\FF_2\).
We could use Rabin’s test: \(f\) is irreducible over \(F\) iff \[ x^{p^n} - x \equiv 0 \mod f \quad\text{ and }\quad \left( f , x ^ { p ^ { n / q } } - x \right) = 1 ~~\forall \text{ prime $q$ dividing $n$} \]
But I’m bad at polynomial division. With some work, we can brute force by listing out all of the \(2^4 = 16\) polynomials over \(\FF_2\) of degree at most 3. Then start multiplying together low-degree terms to cross off higher degree terms; using degree arguments you can show that the irreducible polynomials are: \[ x \\ x+1 \\ x^2 + x + 1 \\ x^3 + x + 1 \\ x^3 + x^2 + 1. \]
So we can pick one of the degree 3 ones to obtain our desired field: \[ GF(8) = \frac{\FF_2[t]}{\generators{t^3+t+1}}. \qed \] General Principle Trinomials of the form \(x^n + ax^{<n} + b\) with \(a,b \in \FF_p\) are usually irreducible.
Solution
Goal: Construct a finite field with 8 elements, \(\mathbb{F}_8\), as a quotient of the polynomial ring \(\mathbb{F}_2[t]\).
1. A field of order \(8 = 2^3\) can be constructed as \(\mathbb{F}_2[t]/\langle p(t)\rangle\), where \(p(t) \in \mathbb{F}_2[t]\) is an irreducible polynomial of degree \(3\).Proof:
1.1. \(\mathbb{F}_2[t]\) is a principal ideal domain because \(\mathbb{F}_2\) is a field.
1.2. For any irreducible polynomial \(p(t) \in \mathbb{F}_2[t]\), the ideal \(\langle p(t)\rangle\) is maximal.
1.3. Hence the quotient ring \(K = \mathbb{F}_2[t]/\langle p(t)\rangle\) is a field.
1.4. The dimension of \(K\) as an \(\mathbb{F}_2\)-vector space is \(\deg(p(t)) = 3\), so \(|K| = |\mathbb{F}_2|^3 = 2^3 = 8\).
2. The polynomial \(p(t) = t^3 + t + 1 \in \mathbb{F}_2[t]\) is irreducible over \(\mathbb{F}_2\).Proof:
2.1. A polynomial of degree \(2\) or \(3\) over a field is reducible if and only if it has a root in the field.
2.2. The elements of \(\mathbb{F}_2\) are \(0\) and \(1\).
2.3. Evaluating \(p(t)\) at these points:\[p(0) = 0^3 + 0 + 1 = 1 \neq 0 \pmod 2,\]\[p(1) = 1^3 + 1 + 1 = 3 \equiv 1 \neq 0 \pmod 2.\]
2.4. Since \(p(t)\) has degree \(3\) and has no roots in \(\mathbb{F}_2\), \(p(t)\) is irreducible over \(\mathbb{F}_2\).
3. Construction of \(\mathbb{F}_8\):\[\mathbb{F}_8 \cong \mathbb{F}_2[t]/\langle t^3 + t + 1\rangle = \{a_0 + a_1 \alpha + a_2 \alpha^2 \mid a_0, a_1, a_2 \in \mathbb{F}_2\},\]where \(\alpha = t \pmod{t^3+t+1}\) satisfies \(\alpha^3 = \alpha + 1\).
2. Q.E.D.