THE GARDEN

Finite Fields (Galois Fields: GF(p) and GF(2^n))

Updated 13 Sep 2026

• •

  What it is

  • •

    A field is a set with two operations (addition and multiplication) where both behave like ordinary arithmetic — associative, commutative, distributive — and, critically, every nonzero element has a multiplicative inverse (division works, except by zero). A finite field (Galois field, written $GF(q)$ or $\mathbb{F}_q$) exists precisely when $q$ is a prime or a prime power. Two shapes show up constantly in cryptography: prime fields $GF(p) = \mathbb{F}_p$ — ordinary integers mod a prime $p$, the setting for Diffie-Hellman, RSA's underlying number theory, and quadratic-residue attacks — and binary extension fields $GF(2^n)$ — polynomials with coefficients in $\{0,1\}$, added by XOR and multiplied modulo a fixed irreducible polynomial, the setting for AES's S-box/MixColumns arithmetic and GCM's GHASH. Despite looking different, both are genuine fields: $GF(2^n)$'s "addition" is bitwise XOR (its own inverse — no separate subtraction needed), and its "multiplication" wraps around using a fixed reduction polynomial the same way integer multiplication mod $p$ wraps around using $p$.

• •

  When to apply

  • •

    Any time arithmetic is described as happening "in $\mathbb{F}_p$" or "in $GF(2^8)$"/"$GF(2^{128})$" — recognizing which kind of field you're in tells you which arithmetic rules actually apply (ordinary mod-p arithmetic vs. XOR-based polynomial arithmetic), which is easy to get wrong by assuming one when the code actually implements the other.

• •

  Symbols and assumptions

  • •

    $\mathbb F_p$ is arithmetic modulo prime $p$. $\mathbb F_{2^n}$ consists of binary polynomials of degree below $n$, reduced modulo a chosen irreducible polynomial $f(X)$ of degree $n$. It is not integer arithmetic modulo $2^n$.

• •

  Math — step by step

  • •
    1. In a prime field, add or multiply integers and reduce modulo $p$. Every nonzero denominator has an inverse, so division means multiplying by that inverse.
  • •
    2. In a binary field, coefficient addition is XOR: $1+1=0$. Multiplication is polynomial multiplication, followed by replacing multiples of $f(X)$ with zero.
  • •
    3. Irreducibility matters: it prevents zero divisors and guarantees inverses for nonzero elements. Bit strings are just the chosen polynomial representation; integer multiplication of their encodings is generally wrong.
• •

  Worked example

  • •

    Work in $\mathbb F_8=\mathbb F_2[X]/(X^3+X+1)$. The bit strings 011 and 101 represent $X+1$ and $X^2+1$.

  • •

    Add: $(X+1)+(X^2+1)=X^2+X$, encoded 110. The two constant terms cancel.

  • •

    Multiply: $(X+1)(X^2+1)=X^3+X^2+X+1$. Since $X^3=X+1$ in this field, the result is $(X+1)+X^2+X+1=X^2$, encoded 100.

  • •

    Contrast with integers: $3\cdot5\bmod8=7$, which is not the field result 4. Always state the field representation before interpreting a number.

• •

  Python

  • •

    # GF(2^n) multiplication via shift-and-XOR (here: GF(2^8), AES's reduction polynomial 0x11b)
    def gf28_mul(a, b):
            p = 0
            for _ in range(8):
                if b & 1: p ^= a
                hi = a & 0x80
                a = (a << 1) & 0xFF
                if hi: a ^= 0x1b
                b >>= 1
            return p
    

• •

  SageMath

  • •

    F = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1, names='a')   # binary extension field
    Fp = GF(p)                                                  # prime field
    

• •

  Related

  • •

    Groups (Group Theory Basics)

  • •

    AES

• •

  Cards

  • •

    What's the key difference between how GF(p) and GF(2^n) implement "addition"?

    • •

      GF(p) addition is ordinary integer addition mod p; GF(2^n) addition is bitwise XOR (which is its own inverse, so there's no separate subtraction).

  • •

    What role does a "reduction polynomial" play in GF(2^n) arithmetic?

    • •

      It's the fixed irreducible polynomial that multiplication results are reduced modulo, playing the same structural role that the prime p plays for reducing products mod p in GF(p).

◌ Explore connections in Graph view