Finite fields: basics, computer implementations, visualizations

01 Sep, 2025

In this post I want to talk about finite fields! This is the result of some teaching I did at Canada/USA Mathcamp in 2025. I taught a class on finite fields which assumed fewer prerequisites than is typical for students learning about finite fields, particularly avoiding any prior knowledge of abstract algebra.

I'll assume a bit more background in this post, but what I want to focus on more than the theory of finite fields (which one can read about in any algebra textbook after all) is some ideas as to how they can be implemented on computers, and ways to think about visualizing their multiplication tables.

Finite fields

In the phrase finite field, finite is an adjective modifying the noun field, so let's start with noun. A field is a set $F$ whose elements we can add, subtract, multiply, and divide. If you want to be formal about it there's a long list of axioms that the addition and multiplication operations must satisfy;¹ we think of subtraction and division as properties of addition and multiplication, respectively.

Many familiar sets of numbers are fields: the rational numbers (whole number fractions) form a field, the real numbers (anything on a number, typically represented by their decimal expansion), the complex numbers. Notice that these familiar fields are all infinite sets, and in fact one is contained in the next.

A finite field is simply a field whose underlying set is finite! The most common examples are given by arithmetic modulo a prime $p$: take the set of integers $0,1,\dots ,p-1$, and equip them with the usual addition and multiplication operations but have them wrap around at $p$ whenever we get a result larger $p$ or larger. We call this field ${𝔽}_p$. I'm skipping the details of why this is a field; the important thing here is that $p$ being prime is what enables us to have inverses for multiplication (aka division). If $p$ is not a prime this division property won't hold for all numbers (in particular it will fail with those which share a common factor with the modulus $p$).

Other finite fields

While the examples ${𝔽}_p$ may be familiar if you've seen modular arithmetic before, there are other finite fields out there! Short of walking through the whole standard construction here (again, consult an algebra textbook if you want to read in detail), let me summarize the salient points here:

• Every finite field has prime characteristic, i.e. there is a unique prime number $p$ such that it contains ${𝔽}_p$.
• The additive group of a finite field forms a finite dimensional vector space over ${𝔽}_p$. In particular that means that a finite field must have $p^d$ elements, where $d$ is the dimension as a vector space over ${𝔽}_p$.
• Every finite field can be constructed by adjoining a root of an irreducible monic polynomial over ${𝔽}_p$ to ${𝔽}_p$. If this polynomial is $g(x)$ and it has degree $d$, we think about this construction of adjoining a root as the quotient ${𝔽}_p[x]/(g(x))$, and the standard choice of representatives for the $p^d$ elements are the polynomials with degree $<d$. The element $x$ plays the role of a root of $g(x)$ in this quotient ring.
• Let's say that $g(x)=x^d+h(x)$ for some $h(x)$ of degree $<d$. Multiplication can be performed by multiplying the representative polynomials and repeatedly applying the relation $x^d=-h(x)$ to reduce the result back down to a polynomial of degree $<d$.

To be very concrete about it, let's talk about the smallest field which isn't one of the ${𝔽}_p$, the field with four elements. Our only choice for irreducible polynomial of degree $2$ over ${𝔽}_2$ is $x^2+x+1$. The four elements of our field are $0,1,x,x+1$. Addition is done mod $2$. The interesting piece of multiplication is $x^2$, which is equal to $x+1$: using our reduction rule we have that $x^2=-x-1$ and since everything happens mod $2$ we also have that $-1=1$ and so we get that $x^2=x+1$. To do another example:

Implementing finite field arithmetic on a computer

Finite fields of size $2^d$ are particularly amenable to being represented on computers. Indeed, an interesting everyday application of finite fields are QR codes: every QR code uses arithmetic in the field with $2^8$ elements as the basis for the mathematics it uses to detect and correct errors. Specifically QR codes use Reed-Solomon codes over the field with $2^8$ elements! Let's work through some of the details about how one might exploit the mathematics of finite fields to implement them on a computer.

Representing elements

There are three useful points of view on the elements of a finite field of size $2^d$:

• As a polynomial of degree $<d$, $a_0+a_{1}x+\dots +a_{d-1}{x}^{d-1}$ with coefficients in ${𝔽}_2$.
• As a string of $d$ bits $a_0,a_1,\dots ,a_{d-1}$.
• As an (unsigned) integer in the range $[0,2^d)$, $a_0+2a_1+\dots +2^{d-1}{a}_{d-1}$.

Regardless of which of these viewpoints we use at any given time, it is very easy to store elements of a field with $2^d$ elements a length $d$ strings of bits. Especially when $d=8$, a finite field element is nothing other than a single byte!

Implementing addition

Addition is straightforward: it is just the XOR operation! When we add polynomials we're just adding mod $2$ in each degree separately; as bit-strings this is taking the XOR in each component; this is the XOR of unsigned integers. We don't need any special work to implement addition on a computer!

Implementing multiplication

Multiplication is more more involved. Notice that addition doesn't depend on the choice of defining polynomial $g(x)$, while multiplication does. In principle we can multiply by computing the polynomial product and then repeatedly applying the reduction rule $x^d=-h(x)$ to any terms of degree $\ge d$ until we're left with one of our representatives of degree $<d$. This sounds fiddly, can we do better?

One approach we could take is to simply store the entire $2^d\times 2^d$ multiplication table: we'd have fast computations, at the prohibitive cost of having to store a $2^{2d}$ table. There are a few optimizations we could make (storing only half the table since multiplication is commutative, skipping rows which can easily be computed with additions or shifts) but these don't change the basic quadratic scaling of the space required.

There is another strategy that works in practice for some values of $d$ which is still table-based. We make use of another fact about finite fields: their multiplicative group is cyclic, we can choose some element $\alpha$ such that every non-zero element of the field is a power of $\alpha$.² After picking such an $\alpha$, we precompute two tables:

• A $\log$ table which takes the "logarithm", converting any non-zero element $y$ of the finite field into the $m$ such that $y={\alpha }^m$. This table has size $2^d-1$.
• An $\exp$ table which "exponentiates", taking an integer $n$ and returning the finite field element ${\alpha }^n$. In principle this table only needs to have size $2^d-1$ as well, but in order to save one operation in our eventual multiplication algorithm it is convenient to double the size of the table, so that it can take as inputs any integer $\le 2(2^d-1$)$ and return $\alpha$ raised to that integer.

Using these tables there is an efficient algorithm for multiplying in the field of size $2^d$ for small values of $d$ (i.e. where $2^d$ storage is reasonable)! To multiply elements $y$ and $z$ we:

• Use our $\log$ lookup to find $m,n$ so that $y={\alpha }^m$, $z={\alpha }^n$.
• Do a normal integer addition $m+n$. If our $\exp$ table only went up to $255$ this value might overflow that and we'd need to conditionally subtract off $255$; if we take the double size $\exp$ table we don't need this extra step.
• Use our $\exp$ lookup table with $m+n$ to get $w={\alpha }^{m+n}=yz$.

So we can multiply in our finite field with a single integer addition and 3 table lookups!

Further directions

Here I've given a very concrete description of how one can implement finite field arithmetic purely in software. In practice, some CPUs come with specialized instructions for performing finite field multiplication in these fields with $2^d$ elements, and more clever thinking and use of the underlying math goes into the design of those!³

Some visualizations

Once we have finite field arithmetic up and running on a computer, we can start generating some visualizations. For any finite field the addition table is not very exciting: addition works like $({𝔽}_p{)}^d$. The multiplication table is where the interesting business happens. This makes sense from the polynomial quotient construction perspective: if we think of the elements of our finite field as polynomials of degree $<d$ over ${𝔽}_p$, then addition doesn't increase the degree past the maximum degree of the summands, so we never encounter the defining equation.

Let's look at the multiplication table of ${𝔽}_{256}$, since $2^8=256$ is quite possibly the most computer-amenable finite field.

Figure 1: multiplication table of the finite field with 256 elements.

Here we've used the irreducible polynomial $x^8+x^4+x^3+x^2+1$ to define our field. Remember our three ways of representing elements in a finite field of size $2^8$:

• polynomials of degree $<8$ with ${𝔽}_2$ coefficients,
• bit strings of length $8$ (i.e. bytes!),
• integers in the range $0,1,\dots ,255$. The bit-string definition lets us translate easily between the other two definitions: a bit-string is simply a record of the coefficients of a polynomial, or it can be viewed as an unsigned integer.

In the multiplication table image above pixels are coloured according to the integer value of the field element, from dark to light, $0$ to $255$. Hence the first row of pixels is all black ($0$) and the second row is a gradient ($0$ through $255$).

This is a natural colouring of pixels to use from the integer perspective on our bytes. But from the polynomial perspective, there's less of a direct relationship with "size". Why should the $x^7$ coefficient contribute more to the colour of the pixel than the $x^3$ coefficient, or any other?

Here's that same multiplication table, but now we've split the colouring into two channels: the bottom half of the byte (the 4 bits which are coefficients of $1$ through $x^3$) contributes to the green channel (scaled up by a factor of 16 so they lie in the same range as the top half of the byte), and the top half of the byte (coefficients of $x^4$ through $x^7$) contribute to the "purple" channel (directly to blue, $1/2$ of the value to red, for aesthetic reasons).⁴

Figure 2: 2-coloured multiplication table of the finite field with 256 elements.

It looks different! The patterns formed by the bottom 4 bits have a seeming periodicity to them, with the image looking like it breaks into a $16\times 16$ grid. The reason we don't have a completely regular $16$-fold pattern is that the wraparound of the defining equation introduces some "noise" in those lower order bits.

Even that visualization introduced an artificial distinction between the high and low coefficients. Here's that same idea, but smoothly interpolating through which set of 4 consecutive bits are in the green and purple channels.

Figure 3: Animated multiplication table of the finite field with 256 elements.

We can see lots of patterns, and it's really cool to see the implied periodicity move from $16$ (when the bottom 4 bits are the green channel) down through powers of $2$ until there's no repetition (when the top $4$ bits are the green channel), back to implied $128$-fold periodicity (alternating black and green when the lowest order bit contributes the most to the green channel).

Next time

It is true that for any prime power size $p^d$ there is a finite field of size $p^d$. The typical proofs are non-constructive, in that one shows that a degree $d$ irreducible polynomial over ${𝔽}_p$ must exist, without actually writing one down explicitly. In the next post I want to talk about a couple of ways of directly constructing families of finite fields. Until next time!