# Playing with Finite Fields (or, "tfw gf(2^8)")

15 Nov 2021Itâs been a bit! Cryptography is fun, but so is coding theory, so weâre gonna take a dive in that direction starting today.

If youâve ever scanned a QR code before, youâve probably noticed that you donât need to get a very good picture of the code to have it work. In fact, as Wikipedia shows, you can literally tear off part of the code and it will still scan fine.

The trick is *error correction codes*. These are special algorithms for encoding information. If certain parts of the message are lost or modified, the original message can still be decoded. There is a limit to how much damage can be done to the encoded message, but as long as the damaged message is âclose enoughâ to the undamaged one, the original message can be decoded from it.

Today begins our journey to implement such a code from scratch. Weâll go right for the one QR codes use, called a *Reed-Solomon code*. These algorithms are built around finite fieldsâin our case the field \(\operatorname{GF}(2^8)\)âso weâll start by explaining finite field operations today.

## A first date with \(\small{\operatorname{GF}(2^8)}\)

First, what is the finite field \(\operatorname{GF}(2^8)\)?

Simply put, itâs the *unique field of order \(2^8 = 256\)*. (Donât worry about the unique part! Weâll show now that it exists, and at the end that itâs unique.)

To work with this field, we want an explicit construction. Let \(\mathbb{Z}_2\) be the integers mod 2, i.e. \(\mathbb{Z}/2\mathbb{Z}\). Then we can define

\[\operatorname{GF}(2^8) := \mathbb{Z}_2[X]/(f(X)),\]where \(f(X) \in \mathbb{Z}_2[X]\) is any irreducible polynomial of degree \(8\).

We note this is indeed a field, and that by subtracting off multiples of \(f(X)\), every element of this field can be uniquely represented by a polynomial of degree \(< 8\) in \(\mathbb{Z}_2[X]\). Moreover, no matter what irreducible degree \(8\) polynomial we choose for \(f(X)\), weâll get the same field up to isomorphism.

To make this a little more concrete, one element of \(GF(2^8)\) might be given by the polynomial

\[g(X) = X^7 + X^4 + X^2.\]and another might be given by the polynomial

\[h(X) = X^6 + X^2 + 1.\]To keep things simple, weâll tend to conflate an element of our field with the polynomial of degree \(< 8\) representing it. Weâll also fix a âstandardâ choice of \(f\):

\[f(X) = X^8 + X^4 + X^3 + X + 1.\]We can add \(g\) and \(h\) (remember the coefficients are mod 2) in \(\operatorname{GF}(2^8)\) to get

\[\begin{align*} g(X) + h(X) &= X^7 + X^6 + X^4 + 2X^2 + 1\\ &= X^7 + X^6 + X^4 + 1. \end{align*}\]Since the degree is still \(< 8\), thereâs no need to reduce. To multiply \(f\) and \(g\), we can perform the multiplication in \(\mathbb{Z}_2[X]\) and then reduce mod \(f\):

\[\begin{align*} g(X) \cdot h(X) &= X^{13} + X^{10} + X^9 + X^8 + X^7 + X^6 + X^2\\ &\rightsquigarrow X^7 + X^6 + X^3. \end{align*}\]This reduction can be done by polynomial long division, taking the remainder of \(g(X) \cdot h(X)\) divided by \(f(X).\)

Lastly, for inverses, we can use the extended Euclidean algorithm. Given a polynomial \(g(X) \in \mathbb{Z}_2[X],\) the extended Euclidean algorithm finds \(a(X), b(X) \in \mathbb{Z}_2[X]\) such that

\[a(X) f(X) + b(X) g(X) = \operatorname{gcd}(f(X), g(X)) = 1\]where the latter inequality holds since \(f(X)\) is irreducible. In this case, \(b(X) g(X) \in 1 + (f(X))\), so \(b(X)\) is inverse to \(g(X)\) in \(\operatorname{GF}(2^8)\).

## Coding it up!

With just this, we have enough to begin writing our own implementation of \(\operatorname{GF}(2^8)\)! Weâll do it in Python (of course) and represent polynomials as lists of coefficients, starting with the highest-degree monomial.

First, our modulusâŚ

```
# MOD is the coefficients of the modulus we choose for GF(2^K),
# which here is x^8 + x^4 + x^3 + x + 1
MOD = [1, 0, 0, 0, 1, 1, 0, 1, 1]
```

âŚand some basic utility functionsâŚ

```
# trim leading zeros from a polynomial (list of coefficents,
# starting with the largest-degree monomial)
def _trim(poly):
if _is_zero(poly):
return []
return poly[-(_degree(poly) + 1):]
# test if a polynomial is zero
def _is_zero(poly):
return all([coeff == 0 for coeff in poly])
```

Next, a function to get the degree of a polynomial:

```
# get the degree of a polynomial
def _degree(poly):
if _is_zero(poly):
return None
# get the highest-degree monomial with non-zero coefficient
exps = range(len(poly) - 1, -1, -1)
degree = max([exp for exp, coeff in zip(exps, poly)
if coeff == 1])
return degree
```

Now we can get into the real nitty-gritty. Adding two polynomials in \(\mathbb{Z}_2[X]\) is just xoring, but since our input polynomials might be different lengths, weâll want to zero-pad our arguments first:

```
# add two binary polynomials (i.e. as elts of Z/2Z[X])
def _add(poly_a, poly_b):
# zero-extend the shorter
len_diff = len(poly_a) - len(poly_b)
if len_diff > 0:
poly_b = [0] * len_diff + poly_b
elif len_diff < 0:
poly_a = [0] * (-len_diff) + poly_a
# just xor each coefficient
return [coeff_a ^ coeff_b
for coeff_a, coeff_b in zip(poly_a, poly_b)]
```

Next, multiplying in \(\mathbb{Z}_2[X]\). To do this, weâll create a result polynomial called `prod`

and accumulate partial sums into it. To we multiply \(a(X)\) and \(b(X)\), we can simply take each monomial in \(a(X)\), multiply them by \(b(X)\) (which just consists of âshifting overâ the coefficients, since each monomial has a coefficient of \(1\)), and sum the results.

```
# multiply two binary polynomials
def _multiply(poly_a, poly_b):
# create a product with all zeros
prod = [0 for _ in
range((len(poly_a) - 1) + (len(poly_b) - 1) + 1)]
# go through all self's terms
exps = range(len(poly_a)-1, -1, -1)
for exp, coeff_a in zip(exps, poly_a):
# if a term is nonzero
if coeff_a == 1:
# create a partial sum by shifting other's coefficients
part_sum = poly_b + exp * [0]
part_sum = (len(prod) - len(part_sum)) * [0] + part_sum
# add it into the product
prod = _add(prod, part_sum)
return prod
```

Now, we want a function to reduce one polynomial mod another using long division. We can do this by repeatedly taking our modulus, âshiftingâ it up (i.e. multiplying it by some power of \(X\)) until itâs the same degree as our polynomial, and then subtracting out the shifted modulus. Weâll also record what multiple we took of the modulus, and total that up into a quotient.

```
# divide one polynomial by another
def _reduce(poly, mod):
# get mod degree
mod_degree = _degree(mod)
# remove leading zeroes from mod
mod = _trim(mod)
# create quotient
quot = [0 for _ in range(len(poly))]
# long division to reduce
while True:
# get poly degree
poly_degree = _degree(poly)
# if we're fully reduced, break
if poly_degree is None or poly_degree < mod_degree:
break
# shift mod to cancel out the highest monomial
shift_amount = poly_degree - mod_degree
shift_mod = mod + [0] * shift_amount
# subtract result out of poly
poly = _add(poly, shift_mod)
# add corresponding value to quotient
quot[-(shift_amount + 1)] = 1
return quot, poly
```

We now have all the groundwork laid! Letâs define a class for elements of \(\operatorname{GF}(2^8).\) The only attribute of the class is a list of coefficients, again starting with the highest-degree monomial. (Also, `__str__`

and `__repr__`

are safe to ignore, but I wanted to include them just for completeness.)

```
class QRFiniteField:
"""
An element of the finite field GF(2^8).
Attributes
----------
coeffs : list[int]
A list of binary coefficients, starting with highest-degree
monomial, of the element of GF(2^8).
"""
def __init__(self, coeffs):
self.coeffs = _trim(coeffs)
def __str__(self):
if _is_zero(self.coeffs):
poly = '0'
else:
# get list of exponents, then monomials
exps = range(len(self.coeffs) - 1, -1, -1)
monos = [f'x^{exp}' if exp != 0 else '1'
for coeff, exp in zip(self.coeffs, exps)
if coeff == 1]
# join together with plusses
poly = ' + '.join(monos)
return poly
def __repr__(self):
# add some context for repr
return f'<value {self} in field GF(2^8)>'
```

Adding in our finite field is just as in \(\mathbb{Z}_2[X]\):

```
def __add__(self, other):
# adding is just adding binary polynomials
coeffs = _add(self.coeffs, other.coeffs)
return QRFiniteField(coeffs)
```

Multiplying is the same, but now with reduction:

```
def __mul__(self, other):
# multiply as regular binary polynomials
prod = _multiply(self.coeffs, other.coeffs)
# reduce the product
_, prod = _reduce(prod, MOD)
# return the result
return QRFiniteField(prod)
```

Lastly, to compute inverses, we just implement the extended Euclidean algorithm.

```
def inv(self):
"""
Compute the inverse of this element in GF(2^8).
Returns
-------
QRFiniteField:
The inverse of this element.
"""
# use extended euclidean method
# set initial values
r_last, r_cur = self.coeffs, MOD
s_last, s_cur = [1], [] # polynomials 1, 0
# iterate until we're done
while True:
# calculate next values
q_cur, r_next = _reduce(r_last, r_cur)
s_next = _add(s_last, _multiply(q_cur, s_cur))
if _is_zero(r_next):
# quit if no remainder
break
else:
# otherwise, step forward
r_last, r_cur = r_cur, r_next
s_last, s_cur = s_cur, s_next
# the inverse is stored in s_cur at the end
return QRFiniteField(s_cur)
```

Finally, we can run some tests and assert things work:

```
if __name__ == '__main__':
# run a basic test from Wikipedia, Finite Fields
a = QRFiniteField([0, 1, 0, 1, 0, 0, 1, 1])
b = QRFiniteField([1, 1, 0, 0, 1, 0, 1, 0])
assert a.inv().coeffs == b.coeffs
assert (a * a.inv()).coeffs == [1]
```

And lo and behold, things really work! If youâre curious, or want to play with the code, itâs available at this repository. Iâll be adding code there in the next entries in this series.

For the curious reader, there are certainly lots of ways to optimize finite field arithmetic. The C example here on Wikipedia shows a neat trick for speeding up multiplication in \(\operatorname{GF}(2^8)\), which performs multiplication and reduction simultaneously.

## A little math, as a treat

I promised proofs, and here they are! These arenât critical to understanding how to work with \(\operatorname{GF}(2^8)\) in practice, but since I couldnât find somewhere that had all these arguments in one place, I thought Iâd collect them here for the curious reader:

**\(\operatorname{GF}(2^8)\) is a field:** To see that \(\operatorname{GF}(2^8)\) is a field, it sufficies to show that \((f(X))\) is a maximal ideal in \(\mathbb{Z}_2[X]\). This is true, because if \((f(X))\) werenât maximal, it would be contained in some maximal ideal \(\mathfrak{m}\) containing \(g(X) \notin (f(X)).\) But since \(f(X)\) is irreducible, it is coprime to any such polynomial \(g(X)\). By Bezoutâs lemma, we can find \(a(X), b(X) \in \mathbb{Z}_2[X]\) such that

But then since \(f(X), g(X) \in \mathfrak{m}\), we have \(1 \in \mathfrak{m}\), a contradiction. Thus \(\operatorname{GF}(2^8)\) is a field.

**Elements of \(\operatorname{GF}(2^8)\) are represented by polynomials of degree \(< 8\):** Next, we claim any element of this ring can be uniquely represented by a polynomial of degree \(< 8\). Indeed, if \(g(X) \in \mathbb{Z}_2[X]\) is a representative of some element of \(\operatorname{GF}(2^8)\), then we can use polynomial long division to write

where \(a(x), r(x) \in \mathbb{Z}_2[X]\) and \(\operatorname{deg} r(x) < 8.\) Since \(g(X)\) and \(r(X)\) differ by a multiple of \(f(X)\), then \(r(X)\) is also a representative of our element of \(\operatorname{GF}(2^8)\). This shows our claim.

**These representatives are unique:** Moreover, we claim any two elements with distinct representatives of degree \(< 8\) are distinct. If this wasnât the case, weâd have equal elements of \(\operatorname{GF}(2^8)\) with representatives \(g(X), h(X)\) which are distinct but both have degree \(< 8.\) Subtracting \(g\) and \(h\), we would get a representative \(g(X) - h(X) \neq 0\) of \(0 \in \operatorname{GF}(2^8)\) with degree \(< 8\). But this is impossible, as the quotient map

only sends multiples of \(f(X)\) to \(0\), meaning \(g(X) - h(X)\) canât be a representative of \(0\).

**\(\operatorname{GF}(2^8)\) is well defined:** Lastly, we want to show that our choise of \(f(X)\) doesnât matter. It is sufficient to show the stronger statement that all finite fields of order \(2^8\) are isomorphic. Take any field \(F\) of order \(2^8\). \(F\) must have characteristic \(2\) (as \(F\)âs characteristic must divide its order). We claim that \(F\) is isomorphic to the splitting field of

It sufficies to show that every element of \(F\) is a root of \(h(X)\), as then \(h(X)\) must split into

\[\small{h(X) = \prod_{a \in F} (x - a)}.\]And indeed, \(0 \in F\) is clearly a root of \(h(X)\), and any other \(a \in F^\times\) must have order dividing \(\lvert F^\times \rvert = 2^8 - 1,\) meaning \(a\) is a root of \(X^{2^8 - 1} - 1\) and thus also a root of \(h(X) = X^{2^8} - X.\) Since splitting fields are unique up to isomorphism, we have all fields of order \(2^8\) are isomorphic.

Thanks for reading! Let me know if you liked this article, or if thereâs any improvements I can make for future ones. đŚ