Finite-Field Construction

Intuition, Vocabulary and Foundations

An extension field treats polynomials as modular arithmetic treats integers. In $\mathrm{GF}(2^3)=\mathbb F_2[X]/(X^3+X+1)$, writing $\alpha=X\bmod f$ gives $\alpha^3=\alpha+1$. Every element therefore has one canonical form $a_0+a_1\alpha+a_2\alpha^2$, giving exactly eight elements.

Addition is coefficient-wise modulo $2$. Multiplication first multiplies polynomials and then replaces every power of degree at least three using the defining relation. Irreducibility is decisive: it makes every nonzero residue invertible; a reducible modulus instead creates zero divisors.

An extension field is a polynomial remainder system with an irreducible modulus. Its central invariant is one canonical representative of degree below $k$ for every residue class; without irreducibility, the quotient is generally only a ring.

Concept	Example	Boundary	Question answered
Residue class	$X^3\equiv X+1$ modulo $X^3+X+1$ over $\mathbb F_2$	An unreduced $X^3$ term is not canonical	How is an element represented?
Irreducibility	$X^3+X+1$ has no nontrivial factor over $\mathbb F_2$	$X^2+1=(X+1)^2$ over $\mathbb F_2$	Is the quotient a field?
Polynomial basis	$(1,\alpha,\alpha^2)$ spans $\mathrm{GF}(2^3)$	Four coordinates are redundant	Which coordinates encode an element?
Inverse	$a^{-1}=a^{2^3-2}$ for nonzero $a$	Zero has no inverse	How is division implemented?
Trace	$\operatorname{Tr}(a)=\sum_{i=0}^{k-1}a^{p^i}$	A non-base-field result signals a bug	What additive map returns to $\mathbb F_p$?
Norm	$\operatorname{N}(a)=a^{(p^k-1)/(p-1)}$	A nonzero element cannot have norm zero	What multiplicative map returns to $\mathbb F_p$?

Step-by-Step Derivations and Algorithms

Choose prime $p$ and a monic polynomial $f(X)=f_0+\cdots+f_{k-1}X^{k-1}+X^k$. For small fields, enumerate candidates and reject any divisible by a monic polynomial of degree at most $\lfloor k/2\rfloor$. Every reducible degree-$k$ polynomial has a factor in that range.

To reduce a product, use

$$X^k\equiv-\sum_{i=0}^{k-1}f_iX^i\pmod f.$$

Process coefficients from highest degree downward; every replacement strictly lowers degree. Binary exponentiation then supplies $a^{-1}=a^{p^k-2}$, Frobenius powers, trace, and norm. The identities $a^{p^k}=a$ and $a^{p^k-1}=1$ for nonzero $a$ provide strong test oracles.

Finite-Field Construction algorithm map

flowchart TD
    A[Choose prime p and degree k] --> B[Enumerate monic degree-k polynomials]
    B --> C{Irreducible?}
    C -->|No| B
    C -->|Yes| D[Create canonical coefficient vectors]
    D --> E[Multiply and reduce modulo polynomial]
    E --> F[Build powers, inverses, trace, and norm]
    F --> G[Verify field identities]

Reduction preserves the residue class while eliminating every term of degree at least $k$, so multiplication ends in a unique $k$-coefficient vector. Schoolbook multiplication costs $O(k^2)$ base-field operations and exponentiation costs $O(k^2\log e)$; exhaustive irreducibility search is suitable only for small educational fields.

Implementation, Complexity and Engineering

The implementation stores coefficients from lowest to highest degree, canonicalizes them modulo $p$, requires a monic irreducible modulus, and pads every element to exactly $k$ coordinates. Its readable exhaustive irreducibility test should be replaced by a Frobenius-based test for larger degrees.

from itertools import product
from math import isqrt


def is_prime(n):
    if not isinstance(n, int) or isinstance(n, bool) or n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    d = 3
    while d <= isqrt(n):
        if n % d == 0:
            return False
        d += 2
    return True


def trim(poly, p):
    result = [value % p for value in poly]
    while len(result) > 1 and result[-1] == 0:
        result.pop()
    return result


def poly_divmod(dividend, divisor, p):
    dividend, divisor = trim(dividend, p), trim(divisor, p)
    if divisor == [0]:
        raise ZeroDivisionError
    quotient = [0] * max(1, len(dividend) - len(divisor) + 1)
    inverse = pow(divisor[-1], -1, p)
    while dividend != [0] and len(dividend) >= len(divisor):
        shift = len(dividend) - len(divisor)
        scale = dividend[-1] * inverse % p
        quotient[shift] = scale
        for index, coefficient in enumerate(divisor):
            dividend[shift + index] = (
                dividend[shift + index] - scale * coefficient
            ) % p
        dividend = trim(dividend, p)
    return trim(quotient, p), dividend


def is_irreducible(poly, p):
    poly = trim(poly, p)
    degree = len(poly) - 1
    if not is_prime(p) or degree <= 0 or poly[-1] != 1:
        return False
    for factor_degree in range(1, degree // 2 + 1):
        for coefficients in product(range(p), repeat=factor_degree):
            candidate = list(coefficients) + [1]
            if poly_divmod(poly, candidate, p)[1] == [0]:
                return False
    return True


def find_irreducible(p, degree):
    if not is_prime(p) or degree <= 0:
        raise ValueError("invalid field parameters")
    for coefficients in product(range(p), repeat=degree):
        candidate = list(coefficients) + [1]
        if is_irreducible(candidate, p):
            return candidate
    raise ArithmeticError("no polynomial found")


class FiniteField:
    def __init__(self, p, modulus):
        modulus = trim(modulus, p)
        if not is_prime(p) or len(modulus) < 2 or modulus[-1] != 1:
            raise ValueError("invalid field parameters")
        if not is_irreducible(modulus, p):
            raise ValueError("modulus must be irreducible")
        self.p = p
        self.modulus = tuple(modulus)
        self.degree = len(modulus) - 1
        self.size = p ** self.degree

    def element(self, coefficients):
        values = [x % self.p for x in coefficients]
        if len(values) > self.degree:
            values = self.reduce(values)
        values += [0] * (self.degree - len(values))
        return tuple(values[:self.degree])

    def zero(self):
        return (0,) * self.degree

    def one(self):
        return (1,) + (0,) * (self.degree - 1)

    def add(self, left, right):
        left, right = self.element(left), self.element(right)
        return tuple((x + y) % self.p for x, y in zip(left, right))

    def reduce(self, coefficients):
        work = [x % self.p for x in coefficients]
        work += [0] * max(0, self.degree - len(work))
        for degree in range(len(work) - 1, self.degree - 1, -1):
            coefficient = work[degree] % self.p
            for index in range(self.degree):
                work[degree - self.degree + index] = (
                    work[degree - self.degree + index]
                    - coefficient * self.modulus[index]
                ) % self.p
        return work[:self.degree]

    def multiply(self, left, right):
        left, right = self.element(left), self.element(right)
        result = [0] * (2 * self.degree - 1)
        for i, x in enumerate(left):
            for j, y in enumerate(right):
                result[i + j] = (result[i + j] + x * y) % self.p
        return tuple(self.reduce(result))

    def power(self, value, exponent):
        if exponent < 0:
            return self.power(self.inverse(value), -exponent)
        result, base = self.one(), self.element(value)
        while exponent:
            if exponent & 1:
                result = self.multiply(result, base)
            base = self.multiply(base, base)
            exponent >>= 1
        return result

    def inverse(self, value):
        value = self.element(value)
        if value == self.zero():
            raise ZeroDivisionError("zero has no inverse")
        result = self.power(value, self.size - 2)
        if self.multiply(value, result) != self.one():
            raise ArithmeticError("inverse check failed")
        return result

    def trace(self, value):
        result, conjugate = self.zero(), self.element(value)
        for _ in range(self.degree):
            result = self.add(result, conjugate)
            conjugate = self.power(conjugate, self.p)
        if any(result[1:]):
            raise ArithmeticError("trace left base field")
        return result[0]

    def norm(self, value):
        result = self.power(value, (self.size - 1) // (self.p - 1))
        if any(result[1:]):
            raise ArithmeticError("norm left base field")
        return result[0]


assert find_irreducible(2, 3) == [1, 0, 1, 1]
field = FiniteField(2, [1, 1, 0, 1])
alpha = field.element([0, 1])
assert field.power(alpha, 3) == field.add(alpha, field.one())
assert len({field.power(alpha, i) for i in range(7)}) == 7

for coefficients in product(range(2), repeat=3):
    value = field.element(coefficients)
    assert field.power(value, 8) == value
    assert field.trace(value) in range(2)
    assert field.norm(value) in range(2)
    if value != field.zero():
        assert field.multiply(value, field.inverse(value)) == field.one()

try:
    FiniteField(2, [1, 0, 1])
except ValueError:
    pass
else:
    raise AssertionError("reducible modulus accepted")

print("all tests passed")

Choice	Cost	Failure mode	Mitigation
Polynomial basis	$k$ coefficients	Coefficient order confusion	Document low-degree-first storage
Schoolbook multiplication	$O(k^2)$ operations	Slow for large $k$	Use faster polynomial multiplication
Exhaustive irreducibility	Exponential search	Impractical at scale	Use Frobenius or Rabin tests
Fermat inversion	$O(k^2\log p^k)$	Zero is not invertible	Reject zero and verify the product
Canonical tuples	Stable equality and hashing	Unreduced duplicate encodings	Reduce at public boundaries
Lookup tables	Fast for tiny fixed fields	Memory grows as $p^k$	Restrict to small fields

Applications, Case Studies and Exercises

In $\mathrm{GF}(2^3)$ defined by $X^3+X+1$, enumerate the eight triples and the seven nonzero powers of $\alpha$. For a reusable package, treat $p$, the basis, and the defining polynomial as part of the type: isomorphic fields built from different polynomials do not share coefficient encodings.

Practice

Apply Finite-Field Construction

Case study 1. Build $\mathrm{GF}(2^3)$, list every element, and verify that the seven nonzero powers of $\alpha$ are distinct. Success means every nonzero element appears once and every inverse product equals one.

Case study 2. Construct $\mathrm{GF}(3^2)$ from an irreducible quadratic. Verify $a^9=a$ for all elements and that every trace and norm lies in $\mathbb F_3$. Success also requires rejecting serialization under a different defining polynomial.

Exercises. Prove why irreducibility removes zero divisors; derive the norm exponent; add division and polynomial-Euclid inversion; test coefficient-order and missing-reduction bugs; replace exhaustive irreducibility testing with the Frobenius criterion.

Use a polynomial basis for transparent general construction and specialized bases or tables only when workloads justify them. Never call a quotient a field before proving irreducibility or compare tuples from different bases; validated parameters are part of every field element's meaning.

Cookie Consent