Finite fields: an interesting construction

27 Nov, 2025

In the last post I introduced some facts about finite fields and we played around with the field with $2^{8}$ elements. This post will assume a bit more background about finite fields, but as always the key facts are: for each prime number $p$ and integer $d \geq 1$ there is a unique up to isomorphism field with $p^{d}$ elements, and that field can be constructed as $𝔽_{p} [x] / (g (x))$ where $g (x)$ is a degree $d$ irreducible polynomial.

Today's we'll look at a seemingly bewildering alternative construction of field of size $2^{2^{n}}$ , and figure out how it relates to the more standard polynomial quotient construction.

Conway's construction

In his book On Numbers and Games Conway gave the following construction of finite fields $C_{n}$ of size $2^{2^{n}}$ .

Elements: the elements of $C_{n}$ are the natural numbers $0, 1, 2, \dots, 2^{2^{n}} - 1$ .

Addition: for $x \neq y$ , the sum of $2^{x}$ and $2^{y}$ is just the natural number $2^{x} + 2^{y}$ . The sum of $2^{x}$ with itself is $0$ . In other words, natural numbers are added by taking the XOR of their base 2 expansions.

Multiplication: is defined by determining the products of $2$ -powers of $2$ , i.e. $2^{2^{x}}$ times $2^{2^{y}}$ . If $x \neq y$ then the product is defined to be the natural number $2^{2^{x} + 2^{y}}$ . Note that this is actually guaranteed to be less than $2^{2^{n}}$ if the original elements are distinct and less than $2^{2^{n}}$ ! The product of $2^{2^{x}}$ with itself is defined to be the natural number $\frac{3}{2} 2^{2^{x}}$ where we interpret the multiplication and division in that formula with normal rational number arithmetic, i.e. it is $2^{2^{x}} + 2^{2^{x} - 1}$ . Assuming ring axioms (associativity, commutativity, distributivity) this defines multiplication for all elements of $C_{n}$ by writing a natural number in its binary expansion, and also taking binary expansions of the powers appearing in the powers of 2.

As a particular example: the field $C_{2}$ has $2^{2^{2}} = 16$ elements, the integers $0$ through $15$ . Multiplication is determined using binary expansions and the rules $2 \times 2 = 3$ and $4 \times 4 = 6$ !

If you've taken a more textbook route to learning about finite fields (as I had!) then this construction seems bonkers! It is not even obvious that these operations produce a field. How can this possibly work? The more targeted question, since every finite field can be realized through the quotient construction, how does this construction relate to the more usual one with quotients of polynomial rings?

Artin-Schreier polynomials

In a field $F$ of characteristic $p$ , the Artin-Schreier polynomial associated to an element $a$ is $x^{p} - x - a$ . These polynomials turn out to be easy to understand compared to general polynomials and thus useful for many constructions.

Lemma: if $b$ is a root of the Artin-Schreier polynomial $x^{p} - x - a$ , then $b + 1, b + 2, \dots, b + p - 1$ are all roots of that polynomial.

Proof: the key here is to think about the function $x^{p} - x$ as a linear map, since we're in a field of characteristic $p$ . Note that this map is linear because taking $p$ -th powers (Frobenius!) is linear in characteristic $p$ . By Fermat's Little Theorem we know that $x^{p} = x$ for any $x$ in $𝔽_{p}$ (i.e. $x = 0, 1, 2, \dots, p - 1$ ). Therefore for any $i$ in $𝔽_{p}$ we have that

(b + i)^{p} - (b + i) = b^{p} + i^{p} - b - i = b^{p} - b = a .

In particular, this concrete understanding of the roots of Artin-Schreier polynomials allows us to prove their irreducibility in many cases.

Lemma: an Artin-Schreier polynomial $x^{p} - x - a$ is irreducible over $𝔽$ if and only if it has no roots in $𝔽$ .

Proof: one direction is immediate, if $x^{p} - x - a$ has any root in $𝔽$ then the above lemma gives us a complete factorization into linear terms.

Let's suppose that $x^{p} - x - a$ factors as $f (x) g (x)$ over $𝔽$ , where each of $f (x)$ and $g (x)$ has degree $< p$ . If $f (x)$ has degree $d$ , the coefficient of $x^{d - 1}$ in $f (x)$ is (up to a minus sign) a sum of the roots of $f (x)$ , which are a subset of the roots of $x^{p} - x - a$ . By the previous lemma we know those roots are of the form $b + i$ for $i$ in $𝔽_{p}$ , so their sum is of the form $d b + j$ for some $j$ in $𝔽_{p}$ . Since $f (x)$ has coefficients in $𝔽$ by assumption and $1 \leq d < p$ we deduce that $b$ itself is in $𝔽$ .

Polynomial realization of Conway's construction

Conway's construction has immediate inclusions $C_{n} \subset C_{n + 1}$ for all $n$ . Since increasing $n$ by one squares the size of the field, it is reasonable to want to directly construct $C_{n + 1}$ as a quadratic extension of $C_{n}$ , i.e. construct it by adjoining a root of an irreducible quadratic polynomial to $C_{n}$ .

Let's do this with Artin-Schreier polynomials. We're looking for an irreducible quadratic polynomial $x^{2} + x + a$ where $a$ is in the field $C_{n}$ (note that $+$ and $-$ are the same since we're in characteristic $2$ ). We know from above that this polynomial is irreducible when $a$ is not of the form $x^{2} + x$ , i.e. when this polynomial has no roots in $C_{n}$ .

The map $x^{2} + x$ from $C_{n}$ to itself is linear over $𝔽_{2}$ , and the kernel of this linear map is the $1$ -dimensional subspace ${0, 1}$ . By rank-nullity that means the image has size $2^{2^{n - 1}}$ , so in particular there are lots of elements which aren't in the image of this map and so could be used to make irreducible quadratic Artin-Schreier extensions.

Moreover, we can directly pin down which elements aren't in the image. The basic idea is to look at the highest degree terms in the binary expansion of $x^{2} + x$ . The square of $2^{n}$ will be of the form $2^{n}$ plus lower degree terms. We'll write $2^{n}$ as a product of $2^{2^{n_{i}}}$ , square each term individually to get a product of $(2^{2^{n_{i}}} + 2^{2^{n_{i}} - 1})$ and expand. Note that in squaring an $x = \sum x_{i} 2^{i}$ we get $\sum x_{i} (2^{i})^{2}$ since squaring is linear in characteristic $2$ (Frobenius again!). So the highest degree term in the binary expansion of $x^{2}$ is the same as that of $x$ itself, and these cancel out in the sum $x^{2} + x$ . In particular if we take an element of $C_{n}$ having the highest bit set, i.e. an element $\geq 2^{2^{n} - 1}$ , we are guaranteed that it is not in the image of the map $x^{2} + x$ on $C_{n}$ .

So we can build a quadratic extension $C_{n + 1}$ of $C_{n}$ by adjoining a root of the quadratic polynomial $x^{2} + x + a$ for any $a$ in $C_{n}$ which is $\geq 2^{2^{n} - 1}$ . Conway's construction uses the choice of the "smallest" (in the normal integer sense) value of $a$ . To create $C_{n + 1}$ we're adding to $C_{n}$ an element which satisfies $x^{2} + x + 2^{2^{n} - 1} = 0$ . Looking back at our definition of the multiplication operation this is exactly the element $2^{2^{n}}$ of $C_{n + 1}$ : it satisfies $(2^{2^{n}})^{2} = 2^{2^{n}} + 2^{2^{n} - 1}$ .