# 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. đź¦Š