Extension Fields

Some time ago, I started a series on the algebraic structure behind ZK-Snarks. My focus was to explain why the group elements in the pairing libraries are represented the way they are. In the previous posts, I introduced groups, fields, elliptic curves and the general structure of pairings. In this post, I expand on the first post, and introduce you to Extension Fields.

The final parts of this series have been harder to write, because the matter is more complex and I’ve tried many different approaches on how to divide and sequence it. I believe in a modular approach, where I can dedicate small-ish posts to whittle down at the complexity of the whole thing, a bit like Michelangelo sought to deliver a magnificent shape from the brute rock by chiseling a bit at a time, to produce his wonderful statues. The difficulty is in finding where to limit the shape of what I want to explain in each post.

This one is an upgrade on the previous post about fields and groups, and delves on extension fields. These are a considerable move in abstraction up from the simpler notion, but they are still only a building piece in a pairing construction. So, let me take my time to go about them and try to make this approachable.

Order of Finite Fields

In my introduction to finite fields, I deliberately kept the discussion short and incomplete, for simplicity. Now is the time to give some more detail. Recall the concept of field order, which is nothing more than the number of elements in the field’s set. Despite the simplicity of this definition, it has a profound influence in the nature of the field and how its elements can be represented.

You see, you can’t have a finite field of any size. Fields can only exist if their order is:

• prime, in which case the field is called a prime field;
• the power of a prime, in which case the field is called an extension field.

In the simpler case, an element can be represented as an integer greater or equal than 0 and less than the field’s order: {0, 1, ..., p-1}.

If the order is not a prime number, then it must be the power of a single prime. You can have a field with 16 = 24 or 1331 = 113 elements, but not1000. When a finite field has a non-prime (ie ‘composite’) order its elements can be represented as polynomials, and the field is called an extension field.

I’ll go into more details below, but for now keep this intuition:

a single number can be seen as a polynomial with only the constant term, for example

f(x) = 7 + 0x + 0x^2 + ... = 7

A polynomial can be seen as an extension of the concept of a number.

Elements of Extension Fields Are Polynomials

The order of an extension field can be written pm, for a prime p and an integer m > 1. The value p is the field’s characteristic, and m is its degree. The polynomials representing each member all must have degree smaller than m, and so each can be represented by a vector with m coordinates (for variable exponents 0 to m-1). For example, for p = 5 and m = 4, a field element could be any polynomial of the form

f(x) = a0 + a1x + a2x2 + a3x3.

And now you can, if you wish, represent every element (a scalar) in the field 𝔽p inside the field 𝔽pm by simply creating a vector with m entries, and then setting the first of these to the value of the scalar. That is, still using the previous example field, the element a of 𝔽p is the same as [a, 0, 0, 0] in 𝔽pm. In this sense, the original field is a sub-field of the new one, and the new one is its extension. And I stress that this means that all elements of the field 𝔽p are also members of 𝔽pm .

Prime Fields

It is an interesting fact of field theory that there is a single field of any given size. You may be able to represent the elements in many different ways (for example, for 𝔽3 you can use the standard numbers {0,1,2} but you could as well choose to use {12, 25, 998} if you were so inclined. It doesn’t matter: whatever you do, if you still have a field, then all you have done was to give different names to your elements.

If in a representation of the field x + y = z, in any other representation of the same field with names new_x, new_y, new_z for x, y, z you will still have absolutely the same relation: new_x + new_y = new_z. We say there is an isomorphism between the representations: the ‘different’ fields have the same form, only the names are different.

The consequence of this is that we can identify a field by just giving its size. A prime field is often represented 𝔽p , where p is a prime. The elements of this field can be represented by the numbers 0 to p-1, and the field operations are simply the addition and multiplication modulo p. The value p is called the modulus of the field. To give an example, if the field modulus is 11, then

All (mod 11):

5 + 7  = 12  = 12 - 11  = 1
6 - 10 = -4  = -4 + 11  = 7
3 * 7  = 21  = 21 - 11  = 10

9 * -8 = -72 = -72 + 77 = 5
9 * -8 = 9 * (-8 + 11) = 9 * 3 = 27 = 27 - 22 = 5

5 * 9  = 45 = 45 - 44 = 1 ==> 1/5 = 9
4 / 5  = 4 * 9 = 36 = 36 - 33 = 3
3 * 5  = 15 = 15 - 11 = 4

If you are not comfortable with modular arithmetics, try studying the above examples. They contain examples of all the basics you need.

Extension Fields

Extension fields look much more complicated, but there are parallels with prime fields that can make them easier to understand.

1. First of all, we have to consider two parameters: the characteristic of the field, p, and the degree d. The order of the field is then pd, and the field is denoted 𝔽pd.
2. The elements of the field can no longer be represented by single numbers. Instead, they can be represented as polynomials over a free variable (for example z) where the coefficients are elements in 𝔽p (the prime field with size equal to the characteristic) and the polynomial has degree less than d.
3. Extension fields also have a modulus, but instead of a number it is now an irreducible polynomial of degree d:some f(z). The operations of the field are now addition and multiplication of polynomials, reduced modulo f(z).

Irreducible polynomials act like prime numbers, in that they cannot be factored into polynomials of lower degrees inside the field. An example is x2 + 1, which you can’t factor while keeping your coefficients in 𝔽p for many primes p > 2. Interestingly, for p = 2 you can use the fact that 1 = -1 and rewrite

x2 + 1 = x2 - 1 = (x - 1) (x + 1) = (x - 1)2

but you can find similar factorizations whenever p = a2 + 1.

Also like prime numbers, they can be factors of other polynomials, and we use them in the same way to reduce the result of an operation in the field. As I said above, to represent a polynomial, we can just list the coefficients of the polynomial in an array (fair warning, I tend to use this name interchangeably with list and vector), and omit the variable.

A Small Example

For an example, let’s look at the extension field: 𝔽23.

This field has 8 elements, all of which must be of degree smaller than 3. The polynomials therefore are represented by 3 coefficients only, each of them a member of 𝔽2, that is, either 0 or 1.

Since each coefficient can take only 1 of 2 possible values, we can have at most 23 = 8 polynomials. Here they are, in vector and long form:

[0,0,0]: 0       [0,0,1]: x2 
[1,0,0]: 1       [1,0,1]: x2 + 1
[0,1,0]: x       [0,1,1]: x2 + x
[1,1,0]: x + 1   [1,1,1]: x2 + x + 1

Operating in Extension Fields

Polynomials can be added and multiplied. To add, you simply sum the coefficients for each position, which is easy to do in vector notation. To multiply, you can just apply long multiplication as learned in high school, by simply applying the distributivity property (which conveniently all fields must have). For example, in 𝔽54 , and with modulus equal to the irreducible polynomial x4 + x + 1:

(3x3 + x) * (x2 + 2) = 
(3x3 + x) * x2 + (3x3 + x) * 2 = 
3x5 + x3 + 6x3 + 2x =
3x5 + 2x3 + 2x.

This is still not the final result. Remember the polynomials in this field must have degree less than 4. This means we must replace it by the remainder of its division by the modulus polynomial, which is

(3x5 + 2x3 + 2x) / (x4+x+1) = 2x3 - 3x2 - x

since

(3x5 + 2x3 + 2x) = 3x * (x4+x+1) + 2x3 - 3x2 - x.

This reduction is probably the hardest part to understand, once you get over the fact that you are treating whole polynomials (or vectors) as if they were numbers. But this also gives you a clue for doing the modulo reduction. The remainder of a division a / b is just what is left if you successively subtract b from a until you can do it no more. You can do the same with polynomials: ultimately, you subtract the irreducible polynomial from your original element until you can do it no more. When this happens, you’ll be guaranteed that the remainder is a polynomial with a legal degree, that is, smaller than d.

In practice, there are more efficient methods to do this division and get the remainder, but they are not in scope for this post.

In fact, this is a nice place to stop. I’ve covered how extension fields are similar to prime fields, and how their elements can be represented in a way that includes its prime sub-field. This will be useful for when I write about actual pairing implementations, and describe the groups they operate on.

Until then, have fun and don’t get lost in complex fields.