Galois fields, worked by hand: GF(8) in one table

In the Reed–Solomon note, rebuilding lost data needed one division: dividing by 2 became multiplying by 4, because 2 × 4 = 8 = 1 mod 7. That only worked because 7 is prime. Computers want fields whose size is a power of two, so that a symbol is a whole number of bits, and 8, 16 or 256 are not prime. This note shows how that is solved.

What makes a field

A field is a set with addition and multiplication that behave the way you expect from ordinary numbers: both are commutative and associative, multiplication distributes over addition, there is a 0 and a 1, every element has a negative, and every element except 0 has an inverse, a number you can multiply it by to get 1.

That last rule is what makes division possible, and it is the one that fails easily. A finite field is a field with a finite number of elements. They are also called Galois fields, after Évariste Galois, and written GF(q) for a field with q elements.

Why mod 7 works and mod 8 does not

Multiply 2 by every number mod 7: 0, 2, 4, 6, 1, 3, 5. Every value appears once, including 1, at 2 × 4. So 2 has an inverse, 4. The same is true for every non-zero number mod 7, and mod any prime p. The integers mod p are the field GF(p).

Multiply 2 by every number mod 8: 0, 2, 4, 6, 0, 2, 4, 6. Only even numbers come out, so 1 never does, and 2 has no inverse. Worse, 2 × 4 = 0 mod 8: two non-zero numbers multiply to zero. Arithmetic mod 8 is not a field, and neither is arithmetic mod any number that is not prime.

So the eight numbers 0 to 7 cannot be made into a field with ordinary arithmetic. They can with a different arithmetic.

Building GF(8)

Read each 3-bit number as a polynomial whose coefficients are its bits. 6 is 110 in binary, so it is x² + x. 3 is 011, so x + 1. The coefficients are themselves in GF(2), the integers mod 2, where 1 + 1 = 0.

Addition adds coefficients mod 2, which is XOR on the bits. 5 + 3 is 101 XOR 011 = 110 = 6. Every element is its own negative, since x + x = 0, so subtraction is the same operation as addition. No carries, ever.

Multiplication multiplies the polynomials, then takes the remainder after dividing by a fixed polynomial of degree 3. Here that is x³ + x + 1. It has to be irreducible, meaning it cannot be factored into smaller polynomials over GF(2). It plays the part the prime 7 played above.

Work 3 × 7. That is (x + 1)(x² + x + 1) = x³ + x² + x + x² + x + 1. The x² terms cancel in pairs, and so do the x terms, leaving x³ + 1. The remainder rule says x³ + x + 1 = 0, so x³ = x + 1 (remember subtraction is addition). Then x³ + 1 = x + 1 + 1 = x. And x is 010, which is 2.

So in GF(8), 3 × 7 = 2.

The whole table

Doing the same for every pair gives the table in the drawing. Each row from 1 to 7 is a rearrangement of 1 to 7, with no zeros and no repeats. That is the field property you can see: a 1 appears in every row, so every non-zero element has an inverse. The inverses are 1 ↔ 1, 2 ↔ 5, 3 ↔ 6 and 4 ↔ 7.

Logarithms: multiplying by adding

Call x by the name α and take its powers: α⁰ = 1, α¹ = 2, α² = 4, α³ = 3, α⁴ = 6, α⁵ = 7, α⁶ = 5, and α⁷ = 1 again. Every non-zero element appears exactly once. An element whose powers reach all of them is called primitive.

That turns multiplication into addition of exponents, mod 7. Check 3 × 7 again: 3 = α³ and 7 = α⁵, so the product is α⁸ = α¹ = 2. Same answer. Real implementations work this way, with a log table and an antilog table, so multiplying two symbols costs two lookups and an addition.

GF(256): one byte per symbol

The same construction with 8-bit polynomials and an irreducible polynomial of degree 8 gives GF(256). Each element is exactly one byte. Addition is still XOR.

Which polynomial is a choice, and different standards chose differently. QR codes use x⁸ + x⁴ + x³ + x² + 1, often written as 0x11D. AES uses x⁸ + x⁴ + x³ + x + 1, 0x11B. Both give a field of 256 elements, but the multiplication tables differ, so a QR decoder and an AES implementation do not share one.

The difference shows in a detail. With 0x11D, x itself, the byte 2, is primitive: its powers run through all 255 non-zero bytes. With 0x11B they do not. Powers of 2 reach only 51 of them, so AES implementations that use log tables build them from 3, whose powers reach all 255. I checked both by running the powers out in code. FIPS 197, the AES standard, gives {57} × {83} = {c1} as a worked example, and the same code reproduces it.

That is all a Galois field is, in practice: a small, exact number system where every non-zero element can be divided by, sized so that each element fits in the bits you have.