Towers of Binary Fields

A crash course on our basic datatypes

Binius uses key mathematical objects called towers of binary fields. These are integral to everything we do. In this page, we explain them in some mathematical detail. This page should be viewed as a mathematical counterpart to the datatypes page in our frontend site area.

We recall from that page that our fundamental datatypes are bitstrings of power-of-two width. Under the hood, these power-of-two-width binary strings actually represent elements of algebraic objects called binary towers. These towers $\mathcal{T}_\iota$ are mathematical sets called fields. Indeed, each tower $\mathcal{T}_\iota$ is isomorphic as a field to $\mathbb{F}_{2^{2^\iota}}$ , the field of order $2^{2^\iota}$ . Importantly, though, we construct these fields in a special way, which gives them a "nested" structure and makes everything work nicely.

Background

Here, we sketch a bit of mathematical background, though we can't even pretend to be comprehensive.

Fields

A field is a set equipped with addition and multiplication operations, which satisfy the associative, commutative and distributive laws. It also contains additive and multiplicative identities 0 and 1. Finally, every nonzero element is invertible. This is obviously an absurdly abbreviated definition, and there is a huge amount to say about these objects. For our purposes now, we leave it at this.

Field extensions

Here, we sketch algebraic extensions, working throughout in characteristic 2. Let's start with the simplest possible field, $\mathbb{F}_2$ —the field with just the elements $0$ and $1$ , equipped with the XOR and AND operations. Given some extension degree $k$ , it is a classical technique to construct the field extension $\mathbb{F}_{2^k} \mathbin{/} \mathbb{F}_2$ . Usually, the way we do this is by fixing a degree- $k$ irreducible polynomial $f_k(X) \in \mathbb{F}_2[X]$ . Our field is then given as the quotient ring $\mathbb{F}_{2^k} \cong \mathbb{F}_2[X] \mathbin{/} \left( f_k(X) \right)$ ; that is, as the set of univariate polynomials over $\mathbb{F}_2$ modulo the ideal generated by the irreducible polynomial $f_k(X)$ . Concretely, elements of this ring can be represented as polynomials over $\mathbb{F}_2$ of degree less than $k$ . Addition is just componentwise $\mathbb{F}_2$ -addition (i.e., XOR). To multiply two elements, we multiply them as binary polynomials, and then reduce the result modulo $f_k(X)$ .

In practice, we will represent elements of the ring $\mathbb{F}_2[X] \mathbin{/} \left( f_k(X) \right)$ as $k$ -bit binary strings, by writing down their coefficients. In slightly fancier terms, this amounts to picking an $\mathbb{F}_2$ -basis for this ring (here, we're simultaneously viewing it also as $\mathbb{F}_2$ -vector space). Which basis? Well, the obvious one: the set of monomials $1, X, X^2, \ldots , X^{k - 1}$ .

Towers of Extensions

In Binius, we take a different approach. Starting as before with $\mathcal{T}_0 \coloneqq \mathbb{F}_2$ , we take just a degree- $2$ extension:

\begin{equation*}\mathcal{T}_1 \coloneqq \mathcal{T}_0[X_0] \mathbin{/} \left( X_0^2 + X_0 + 1 \right).\end{equation*}

As a field, $\mathcal{T}_1$ is clearly just $\mathbb{F}_{2^2} = \mathbb{F}_4$ .

On the other hand, blackboxing the definition of $\mathcal{T}_1$ —i.e., forgetting for now that it's in its own right a quotient ring—we can repeat this process:

\begin{equation*}\mathcal{T}_2 \coloneqq \mathcal{T}_1[X_1] \mathbin{/} \left( X_1^2 + X_0 \cdot X_1 + 1 \right).\end{equation*}

We state without proof for now that $X_1^2 + X_0 \cdot X_1 + 1$ is irreducible over $\mathcal{T}_1$ . Thus, $\mathcal{T}_2$ is also a field—namely, isomorphic to $\mathbb{F}_{2^4}$ .

What do elements of $\mathcal{T}_2$ look like? Well, they look like linear polynomials, say $\alpha_0 + \alpha_1 \cdot X_1$ , in $X_1$ , where each coefficient is itself a $\mathcal{T}_1$ -element (that is, a a linear polynomial in its own right in the indeterminate $X_0$ , with coefficients in $\mathcal{T}_0 = \mathbb{F}_2$ ).

For example, let's say that $\alpha_0 = 1 + X_0$ and $\alpha_1 = X_0$ . Thus, we have:

\begin{equation*}\alpha = \alpha_0 + \alpha_1 \cdot X_1 = \left( 1 + X_0 \right) + \left( X_0 \right) \cdot X_1.\end{equation*}

By expanding and rearranging, we can express everything as a two-variate polynomial in $X_0$ and $X_1$ :

\begin{equation*}\alpha = 1 + X_0 + X_0 \cdot X_1.\end{equation*}

Of course, this thing is multilinear (each indeterminate only appears with exponent at most 1). Moreover, every polynomial that arises in this way will be too.

We can continue this process by writing, for each $\iota \geq 2$ ,

\begin{equation*}\mathcal{T}_\iota \coloneqq \mathcal{T}_{\iota - 1}[X_{\iota - 1}] \mathbin{/} \left( X_{\iota - 1}^2 + X_{\iota - 2} \cdot X_{\iota - 1} + 1 \right).\end{equation*}

In this way, we get a chain, or tower, of extensions $\mathcal{T}_0 \subset \cdots \subset \mathcal{T}_\iota$ , and so on.

Elements of $\mathcal{T}_\iota$ look like linear polynomials over $\mathcal{T}_{\iota - 1}$ —whose coefficients are themselves polynomials over $\mathcal{T}_{\iota - 2}$ , and so on. Unwinding this process, we get a kind of recursive, tree-like composition of elements. At the bottom of the tree are the bits. Indeed, this also shows that $\mathcal{T}_\iota$ has an $\mathbb{F}_2$ -basis given by the multilinear monomials in the indeterminates $X_0, \ldots , X_{\iota - 1}$ (there are $2^\iota$ such monomials). We will call this the multilinear monomial basis.

Relative Bases

There is a further very important idea hidden here. To explain it, we fix two different tower subfields $\mathcal{T}_\iota \subset \mathcal{T}_\tau$ . Elements of $\mathcal{T}_\tau$ look like linear polynomials over $\mathcal{T}_{\tau - 1}$ , whose coefficients are linear polynomials over $\mathcal{T}_{\tau - 2}$ , and so on. We can perform the same unwinding we just did above, but stop at the intermediate height $\mathcal{T}_\iota$ . In this way, we can express each given $\mathcal{T}_\tau$ -element as a multilinear polynomials in the indeterminates $X_\iota, \ldots , X_{\tau - 1}$ , whose coefficients come from $\mathcal{T}_\iota$ . We thus see that the multilinear monomials in $X_\iota, \ldots , X_{\tau - 1}$ give us a basis for $\mathcal{T}_\tau$ over its nontrivial subfield $\mathcal{T}_\iota$ . (This is a generalization of what we just did above, in which the ground field can be something intermediate, as opposed to $\mathbb{F}_2$ itself.) We will also refer to this as the multilinear monomial basis of $\mathcal{T}_\tau$ over $\mathcal{T}_\iota$ .