Linear algebra over field extensions

20 Aug, 2025

A common occurrence in succinct proofs is the need to work in two different finite fields. In general, we work mostly over a base field $𝐅$ (I will mostly call this the "little field") and over some extension field ${𝐅}^{\prime }$ (ditto "big field") which is a field that is also a superset of the base field ${𝐅}^{\prime }\supseteq 𝐅$. (Technically, the extension ${𝐅}^{\prime }$ need not be an actual superset of $𝐅$; rather, it needs to have a subset that is equivalent/isomorphic to $𝐅$, we will make use of this later.)

Most of the operations in a given succinct proof that uses codes (e.g., in Ligero/ZODA/Ligerito) will be done over the base field and a few (mostly involving random linear combinations) will be over the "big field" . As we will see, most of these operations will take the form of something like the following: let $G\in {𝐅}^{m\times n}$ be a matrix in the "little field" and $x\in {𝐅}^{\prime n}$ a vector over the "big field", then we want to compute $Gx\in {𝐅}^{\prime m}$.

The tl;dr will be that it's all linear algebra in the end and we can simply perform $G{y}_i$ for some $y_1,\dots ,y_k\in 𝐅$ in the little field and pack the elements back together to get the result $Gx$. More specifically, since ${𝐅}^{\prime }$ is a field extension, then ${𝐅}^{\prime }\simeq {𝐅}^k$. Set $x\leftrightarrow (y_1,\dots ,y_k)$ where $y_1,\dots ,y_k\in 𝐅$, then $Gx\leftrightarrow (G{y}_1,\dots ,G{y}_k)$.

First attempt

One way of dealing with this is to first define the field extension ${𝐅}^{\prime }$ and then construct a subset $𝐅\subseteq {𝐅}^{\prime }$ of this field ${𝐅}^{\prime }$ that (a) contains $\{0,1\}$ and (b) is closed under multiplication and addition—in other words, $𝐅$ itself is a field. Since the little field is literally a subset of the big field $𝐅\subseteq {𝐅}^{\prime }$ in the proper sense of the word "subset", the operations can easily be performed since any subfield operation in $𝐅$ is just the same as operating over ${𝐅}^{\prime }$.

This is slightly annoying for two reasons. Number one is that ${𝐅}^{\prime }$ is often "large" in the sense that representing an element of the big field $\alpha \in {𝐅}^{\prime }$ often takes far more bits than representing an element of the little field $\beta \in 𝐅$. A concrete example from ZODA, e.g., is that $𝐅$ has $2^{16}$ elements and so an element can be represented by a 16-bit integer while ${𝐅}^{\prime }$ has $2^{128}$ elements and so requires a 128-bit integer to represent. While asymptotically this doesn't matter, in practice it's very important: in a standard ARM register, which is 64 bits, we can fit 4 "little field" elements and only half of a "big field" element, which kills performance if we represent every "little field" element using the "big field" representation.

Slight improvement

One obvious version of this is to "compress" the representation of $𝐅$: simply represent elements in the little field $𝐅$ using 16-bit integers and then "upcast" them on the fly to their 128-bit representation in ${𝐅}^{\prime }$ during computation.

This is fine and, indeed, is what we do (for now) implicitly in CryptoUtilities.jl but it's a little annoying: the conversion actually takes a nontrivial amount of operations since the mapping from the "compressed" representation of $𝐅$ to the "big field" representation in requires 16 "big field" additions.

(There's also some secondary annoyance since we would like the representations to be "consistent" in that multiplication in the "compressed" representation should correspond to multiplication in the "big field" representation, but that's a different story for a later day. See, e.g., here for how we deal with this.)

General construction

Another way to construct this pair of fields $𝐅$ and ${𝐅}^{\prime }$ is in "reverse". In particular, we can define ${𝐅}^{\prime }$ as a degree $k$ extension of $𝐅$ by setting

where $f$ is an irreducible polynomial over $𝐅$ of degree $k$. (Funnily enough, $f$ itself won't be used anywhere else in this construction, it just matters that one exists, which we know a-priori.)

This means that an element of the big field ${𝐅}^{\prime }$ and a $k$-vector over the little field $𝐅$ are equivalent in that one can be mapped to the other and vice versa. That is,

in the obvious way: $x\in {𝐅}^{\prime }$ is a polynomial of degree $<k$, so interpret the coefficients as a $k$-vector, or, conversely, the $k$-vector can be interpreted as a polynomial of degree less than $k$, which gives the bijective mapping. Note that $0\in 𝐅$ is the zero polynomial in ${𝐅}^{\prime }$, or, equivalently, the zero vector in ${𝐅}^k$. (Exercise: what should the 1 element be in ${𝐅}^{\prime }$ and therefore in ${𝐅}^k$ using this map?) Most importantly, note that this map is linear in the little field $𝐅$ and preserves that structure.

In general, given an element $\beta \in {𝐅}^{\prime }$ we will write its "tilde" version $\tilde{\beta }\in {𝐅}^k$ to be its version as a $k$-vector.

Breaking it down

The first question to ask then is, given two elements, $\alpha \in 𝐅$ in the little field and $\beta \in {𝐅}^{\prime }$ in the big field, what is $\alpha \beta$? Since $\beta \in {𝐅}^{\prime }$ then set $\tilde{\beta }\in {𝐅}^k$ to be the corresponding $k$-vector. It is not hard to show that $\widetilde{\alpha \beta }=\alpha \tilde{\beta }$; in other words, multiplication of a big field element by a little field element is just scalar multiplication of the underlying vector representation of the big field element.

Now, we can ask the next question: given a vector in the little field $x\in {𝐅}^n$ and a scalar in the big field $\beta \in {𝐅}^{\prime }$, what is the (big field) ${𝐅}^{\prime n}$ vector $\beta x$? Well, from before, note that $\tilde{\beta }\in {𝐅}^k$, and we know the $i$th entry of $\beta x$ should be equal to $\beta x_i$, which we know from before. This, in turn, is equivalent in the vector representation of the big field to $x_i\tilde{\beta }$, which is a $k$-vector over $𝐅$. Finally, define the matrix representation of a vector $y\in {𝐅}^{\prime n}$ in the big field to be the matrix $\tilde{y}\in {𝐅}^{n\times k}$ over the small field where the $i$th row of $\tilde{y}$ is the $k$-vector representation of the $i$th element $\widetilde{(y_i)}\in {𝐅}^k$. A little work shows that $\beta x$ is then, in this matrix representation:

Finally, we can put all of this together for the general case. Given a matrix $G\in {𝐅}^{m\times n}$ in the little field and a vector $x\in {𝐅}^{\prime n}$ in the big field, we'd like to compute $Gx\in {𝐅}^{\prime m}$ (which is a vector in the big field, representable as an $m\times k$ matrix over the little field). Of course, we know that, by definition

where $g_i\in {𝐅}^m$ is the $i$th column of $G$ (in the little field) and $x_i$ is a scalar (in the big field). We can use our previous scalar-vector product representation to note that

and add these together to get

In other words, applying any linear operation whose elements are always in the little field to a vector in the big field is equivalent to applying the linear operation to each column of the matrix representation of the big-field vector.

This means that, if we have an efficient procedure to compute $Gz$ for any vector $z$ in the little field, we can simply use the efficient procedure as a black box to compute $Gx$ when $x$ is in the big field by applying it to each column of the matrix representation of the big-field vector $x$.