Fields of order pk – Public-Key Cryptography

7.6.2 Fields of order pk

Are there any other finite fields than 𝔽p? It seems that the requirements that the order of the field must be a prime number is unavoidable, but it is actually possible to construct fields of order pk, if we leave the known terrain of numbers and turn to other, more abstract objects as field elements. For example, one might arrange the elements of 𝔽p in vector-like fashion, but it is difficult to find a multiplication operation that maps vector pairs on vectors and is invertible.

The way ahead is to look at polynomials of degree ≤ k − 1 with coefficients ai ∈𝔽p:

Here, we have no intention of plugging in any values for the variable X. Instead, we are using these polynomials as mathematical objects of their own.

Let’s define 𝔽k[X] to be the set of all polynomials of degree ≤ k − 1 with coefficients in 𝔽p:

First, we note that 𝔽k[X] has pk elements, because for each of the k coefficients there are p possibilities. For example, if we take p = 2 and k = 2, then 𝔽2[X] has the following four elements:

By using the + operation from the underlying field 𝔽p, we can easily define a + operation on 𝔽k[X]:

so that (𝔽k[X],+) forms an abelian group with the 0 – polynomial as neutral element.

But if we try to do same thing with the ⋅ operation, we run into trouble, because the product of two polynomial of degree ≤ k − 1 can have a degree ≥ k. Analogously to 𝔽p, we need to do the multiplication modulo some polynomial M of degree k. This means, we first carry out the ordinary polynomial multiplication and divide the result by M, with some remainder polynomial r ∈𝔽k[X]. This remainder polynomial we define to be the product of p and q in 𝔽k[X].

For example, let’s consider 𝔽2[X] again and let M = X2 + 1. Then,

We can compute (X2 + X) : (X2 + 1) using long division in 𝔽2[X] and get the remainder r = X + 1 = p3(X). So we see that p2(X) ⋅ p3(X) = p3(X).

So we have found a ⋅ operation for 𝔽k[X]. One can show that ⋅ is associative and p(X) = 1 is a neutral element, if we take 1 to be the multiplicatively neutral element in 𝔽p. However, we are not home free yet, because we will not always be able to find multiplicative inverses for the elements of 𝔽k∗[X] = 𝔽k[X] ∖{0}.

Take, for example, p3 = X + 1 in 𝔽2[X]. If we look for an inverse element with respect to multiplication modulo M = X2 + 1, we get the following results (if you want to check them for yourself, bear in mind that −1 = 1 in 𝔽2[X]) :

Analogously to the arithmetic in 𝔽p, in order to construct multiplicative inverses, we need to do the arithmetic modulo some prime element. That is, the result of every operation is taken modulo that prime element. Here, the prime elements are the irreducible polynomials, that is, polynomials that cannot be written as a product of two polynomials of degree one.

For example, our previous polynomial M = X2 + 1 is not irreducible, because in 𝔽2, we have

On the other hand, M = X2 + X + 1 cannot be written as a product of two polynomials of a smaller degree in 𝔽2. To see this, assume that

By comparing coefficients, we see that a1b1 = 1, which means a1 = b1 = 1. Analogously, we get a0 = b0 = 1. But in 𝔽2, this means a1b0 + a0b1 = 0, which is a contradiction. Hence X2 + X + 1 is irreducible over 𝔽2.

Using M = X2 + X + 1, we can now set up a multiplication table for the three elements of 𝔽2∗[X] mod M as shown in Table 7.2.

⋅ mod M	1	X	X + 1
1	1	X	X + 1
X	X	X + 1	1
X + 1	X + 1	1	X

 Table 7.2: Multiplication table for 𝔽2∗[X] mod (X2 + X + 1)

Most importantly, there is a 1 in every row of the table, meaning that every element has a multiplicative inverse. So 𝔽2∗[X] forms a group with respect to multiplication modulo M, and we have succeeded in constructing a field with 22 = 4 elements (we must not forget to include the zero polynomial in the field). In general, it can be shown that for any prime p and degree k there are always irreducible polynomials M of degree k over 𝔽p. This means that, given a prime number p and a positive integer k, we can always construct fields of order pk. There are at least three different notations for finite fields:

• If the irreducible polynomial M that is used to construct the field is given, it is denoted as 𝔽p[X]∕M
• Alternatively, we can write 𝔽pk without stating the polynomial
• Finally, you often see GF(pk), where GF stands for Galois Field, after the French mathematician Evariste Galois (1811-1832).