A Detailed Overview of Galois Fields

The night before his fatal duel, Évariste Galois wrote a letter to his friend Auguste Chevalier. He was 20 years old. In the margins of his mathematical manuscripts, he scrawled: "I have not time" — and proceeded to outline discoveries that would take the mathematical community decades to fully understand. Among them was the complete theory of what we now call Galois fields: finite algebraic structures that underpin nearly every piece of modern cryptography and error correction.

"Ask Jacobi or Gauss to publicly express their opinion — not on the truth, but on the importance of these theorems. Later, I hope, there will be people whom it will benefit to sort through all this chaos." — Évariste Galois, 1832

What Is a Field?

A field is a set equipped with two operations — addition and multiplication — satisfying the following axioms:

• Closure: Adding or multiplying two elements always produces another element in the set
• Associativity and commutativity: Both operations commute and associate freely
• Distributivity: Multiplication distributes over addition
• Identity elements: There exists a 0 (additive identity) and a 1 (multiplicative identity)
• Inverses: Every element has an additive inverse; every nonzero element has a multiplicative inverse

The rationals ℚ, reals ℝ, and complex numbers ℂ are all infinite fields. A Galois field (or finite field) GF(q) is a field with exactly q elements. Galois proved the fundamental theorem: finite fields exist if and only if q = p^n, where p is prime and n is a positive integer. Furthermore, all fields of the same size are isomorphic — there is essentially one GF(q) for each valid q.

Modular Arithmetic: The Foundation

The simplest Galois fields are GF(p) — the integers modulo a prime p. In GF(7), for instance:

• 3 + 5 = 1 (since 8 mod 7 = 1)
• 3 × 5 = 1 (since 15 mod 7 = 1, meaning 3 and 5 are multiplicative inverses)

Finding the multiplicative inverse in GF(p) uses the extended Euclidean algorithm — the same algorithm Euclid described for computing GCDs, extended to express the GCD as a linear combination of the two inputs. Since gcd(a, p) = 1 for any nonzero a in GF(p), the algorithm produces integers x, y satisfying ax + py = 1, which means ax ≡ 1 (mod p): x is the inverse of a.

Fermat's Little Theorem offers an alternative for prime fields: a^(p-1) ≡ 1 (mod p) for any nonzero a, so a^(p-2) is the multiplicative inverse of a. This is computationally convenient with fast modular exponentiation.

Extension Fields: GF(2⁸)

Cryptographic and coding applications almost always use extension fields of the form GF(2^n) — fields with 2^n elements built over the base field GF(2) = {0, 1}. The construction works as follows:

Represent each element as a polynomial of degree less than n with coefficients in GF(2) (i.e., binary coefficients). Addition of two elements is coefficient-wise XOR — no carries, no modular reduction needed. Multiplication is polynomial multiplication followed by reduction modulo an irreducible polynomial of degree n.

For GF(2^8) — the field used in AES — a common choice of irreducible polynomial is:

x⁸ + x⁴ + x³ + x + 1   (0x11B in hex)

A byte value like 0xC2 is interpreted as the polynomial x⁷ + x⁶ + x + 1, and multiplication in GF(256) is polynomial multiplication reduced modulo 0x11B.

C++ Implementation of GF(256) Arithmetic

uint8_t gf256_mul(uint8_t a, uint8_t b) {
    uint8_t result = 0;
    for (int i = 0; i < 8; i++) {
        if (b & 1) result ^= a;
        bool high = (a & 0x80);
        a <<= 1;
        if (high) a ^= 0x1B;  // x^8 mod (x^8+x^4+x^3+x+1)
        b >>= 1;
    }
    return result;
}

This is the schoolbook algorithm: iterate over bits of b, accumulating a into result when the current bit is 1, and updating a by doubling (left shift) with reduction when needed. Correct, but not fast for bulk operations.

Optimization: Look-Up Tables

Since GF(256) has only 256 elements, multiplication can be precomputed entirely. The standard approach uses the observation that GF(256) has a multiplicative group of order 255, and if g is a generator (primitive element) of that group, then every nonzero element is a power of g. Multiplication becomes:

a × b = g^(log_g(a) + log_g(b))

Two 256-byte tables — one for discrete logarithms, one for exponentiation — reduce any field multiplication to two table lookups, an addition, and a table lookup:

// Precomputed tables with g = 0x03 (a generator of GF(256)*)
uint8_t EXP[512];  // exp[i] = g^i, with wraparound
uint8_t LOG[256];  // log[x] = discrete log of x base g

uint8_t gf256_mul_lut(uint8_t a, uint8_t b) {
    if (a == 0 || b == 0) return 0;
    return EXP[LOG[a] + LOG[b]];  // sum may reach 510, handled by 512-entry EXP
}

Tower Field Construction: GF(2¹⁶) over GF(2⁸)

Larger fields can be built as extensions of smaller ones. GF(2^16) can be constructed as GF(2^8)[y] / (y^2 + y + v), where v is a carefully chosen element of GF(2^8) making the polynomial irreducible. Each GF(2^16) element is then a pair (a₁, a₀) of GF(2^8) elements representing a₁y + a₀:

struct GF16 {
    uint8_t hi, lo;  // represents hi*y + lo in GF(2^8)[y]/(y^2+y+v)
};

GF16 gf16_mul(GF16 a, GF16 b) {
    uint8_t a1b1 = gf256_mul(a.hi, b.hi);
    uint8_t a0b0 = gf256_mul(a.lo, b.lo);
    return {
        .hi = gf256_mul(a.hi ^ a.lo, b.hi ^ b.lo) ^ a0b0,
        .lo = gf256_mul_v(a1b1) ^ a0b0  // v is a fixed GF(256) constant
    };
}

This Karatsuba-style formula reduces a GF(2^16) multiplication to three GF(2^8) multiplications rather than four.

Fast Inversion: The Itoh-Tsujii Algorithm

Computing the multiplicative inverse a^(-1) = a^(2^n - 2) naively requires n-1 squarings and n-2 multiplications. The Itoh-Tsujii algorithm exploits the additive structure of the exponent to reduce multiplications by approximately 4×:

The key observation is that 2^n - 2 = (2^(n-1) - 1) × 2. Computing a^(2^k - 1) can be done efficiently through a chain of additions in the exponent, where each addition corresponds to a field multiplication. For GF(2^8), the full inversion requires only 4 multiplications and 7 squarings (versus 6 multiplications naively).

Applications

AES (Advanced Encryption Standard)

AES operates on 4×4 byte arrays, applying four transformations per round. The SubBytes step — the nonlinear component that provides confusion — computes the multiplicative inverse of each byte in GF(256) followed by an affine transformation. The MixColumns step performs matrix multiplication where the matrix entries are GF(256) elements. Every byte of encrypted data passes through GF(256) arithmetic multiple times per encryption round.

Reed-Solomon Error Correction

Reed-Solomon codes treat data blocks as polynomials over GF(2^8) or GF(2^16). The encoding process evaluates the data polynomial at multiple points in the field, producing redundancy symbols. Decoding recovers the original polynomial even if some evaluation points (transmitted symbols) are corrupted or erased — using polynomial interpolation over the field. This is why QR codes can still be scanned when partially obscured, and why satellite transmissions can survive burst errors.

Linear Feedback Shift Registers (LFSRs)

An LFSR of length n over GF(2) generates a sequence by repeatedly computing a linear recurrence over the field. When the feedback polynomial is primitive (irreducible and of maximal period), the LFSR cycles through all 2^n - 1 nonzero states before repeating. This is equivalent to computing successive powers of a generator element in GF(2^n). LFSRs underpin stream ciphers and pseudorandom sequence generators in hardware implementations where speed and simplicity matter.

Intel GFNI: Hardware-Accelerated Field Arithmetic

In 2021, Intel introduced the Galois Field New Instructions (GFNI) extension to x86. The GF2P8MULB instruction performs GF(2^8) multiplication on packed bytes in SIMD registers — 16 or 32 independent GF(256) multiplications per instruction, using the AES field polynomial. For algorithms like Reed-Solomon that process data in bulk, this can deliver an order-of-magnitude speedup over software LUT-based approaches.

// Using GFNI intrinsics
#include <immintrin.h>

__m128i gf256_mul_simd(__m128i a, __m128i b) {
    // Multiply 16 bytes of a by 16 bytes of b simultaneously in GF(256)
    return _mm_gf2p8mul_epi8(a, b);
}

Galois did not know his midnight letter would one day secure bank transactions, protect satellite telemetry, and run inside every AES-NI enabled processor sold. The fields he discovered are not abstract curiosities — they are the arithmetic of modern information.