A Field $E$ is an extension field of a field $F$ if $F \subseteq E$ and the operations of $F$ are those of $E$ restricted to $F$ i.e.

• Every element in the smaller field $F$ is also in the larger field $E$ . The field $F$ is fully contained in the field $E$.
• If you add or multiply two elements from the smaller field $F$, you get the exact same result whether you use $F$’s rules or $E$’s rules

This post is restricted to Finite Extension Fields. Finite Extension Fields are Prime Power Extension Fields. i.e. for a prime $p$ & an integer $n > 1$, $\mathbb F_{p^n}$ is an extension of $\mathbb F_p$.

Let $\mathbb F_p$ be a field where $p$ is a prime number & let $\mathbb F_p[x]$ be its Polynomial Ring. A polynomial $f(x) \in \mathbb F_p[x]$ of degree $\ge 2$ is called irreducible if it cannot be factored into two or more non-constant polynomials of smaller degree with coefficients in $\mathbb F_p$. Even if $f(x)$ has no root in $\mathbb F_p$, we can construct an extension field of $\mathbb F_p$ that contains a root $\alpha$ of $f(x)$.

Constructing an Extension Field

Adjoining a root

Let’s consider the field $\mathbb F_2$ - the corresponding Polynomial Ring is $\mathbb F_2[x]$.

$f(x) = x^4 + x + 1$ is an irreducible polynomial of degree $4$ in $\mathbb F_2$.

$\mathbb F_2$ doesn’t contain the root of the irreducible polynomial. However, we can construct an extension field of $\mathbb F_2$ that contains a root $\alpha$ of this polynomial. Let’s find the smallest extension field that contains this root.

Let $\alpha$ be the root of this polynomial in an extension field of $\mathbb F_2$. If $\alpha$ is a root, then $f(\alpha) = 0$ i.e. $\alpha^4 + \alpha + 1 = 0$.

Let’s write out the Polynomial Ring $\mathbb F_2[\alpha]$. All polynomials will be of the form $f_0 + f_1 \alpha + f_2 \alpha^2 + f_3 \alpha^3 + f_4 \alpha^4 + f_5 \alpha^5 + …$ where $f_n \in \mathbb F_2$ i.e. all the $f_n$s can only be $0$ & $1$

Polynomials:

Degree 0: $0$ & $1$

Degree 1: $\alpha,\alpha+1$

Degree 2: $\alpha^2, \alpha^2 + 1, \alpha^2 + \alpha, \alpha^2 + \alpha + 1$

Degree 3: $\alpha^3, \alpha^3 + 1, \alpha^3 + \alpha, \alpha^3 + \alpha + 1, \alpha^3 + \alpha^2, \alpha^3 + \alpha^2 + 1, \alpha^3 + \alpha^2 + \alpha, \alpha^3 + \alpha^2 + \alpha + 1$

Degree 4: $\alpha^4,\alpha^4 + 1, \alpha^4 + \alpha, \alpha^4 + \alpha + 1, \alpha^4 + \alpha^2, ….$

Now, since $\alpha^4 + \alpha + 1 = 0$, $\alpha^4 = \alpha + 1$ (because in $\mathbb F_2, -1$ is the same as $1$)

The first element of degree $4$,

$\alpha^4 = \alpha^3 \cdot \alpha = (\alpha+1)\cdot \alpha = \alpha^2 + \alpha$ (which is already in our list of degree $2$ elements)

The next element of degree $4$,

$\alpha^4 + 1 = \alpha^2 + \alpha + 1$ (already in our degree $2$ list)

This way, we can reduce all elements of degree $4$ and above to existing elements of up to degree $3$ or below

So our extension field $\mathbb F_{2^4}$ has a total of 16 elements

$\mathbb F_{2^4} = \lbrace 0, 1, \alpha, \alpha + 1, \alpha^2, \alpha^2 + 1, \alpha^2 + \alpha, \alpha^2 + \alpha + 1, \alpha^3, \alpha^3 + 1, \alpha^3 + \alpha, \alpha^3 + \alpha + 1, \alpha^3 + \alpha^2, \alpha^3 + \alpha^2 + 1, \alpha^3 + \alpha^2 + \alpha, \alpha^3 + \alpha^2 + \alpha + 1 \rbrace$

Likewise, we can construct $\mathbb F_{2^3}$ by adjoining the root $x^3 + x + 1$

$ \mathbb F_{2^3} = \lbrace 0, 1, \alpha, \alpha+1, \alpha^2, \alpha^2+1, \alpha^2+\alpha, \alpha^2+\alpha+1 \rbrace$

Quotienting

Any of these extensions can also be represented by a different notation

E.g.

$\mathbb F_{2^3} \cong \mathbb F_2[x]/\langle x^3 + x + 1 \rangle$

To understand why this notation makes sense, let’s look at Quotient Rings & cosets

Consider the ring $\mathbb Z = \lbrace \cdots,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, \cdots \rbrace$

$\langle 4\rangle $ is an Ideal of the ring $\mathbb Z$ which can be generated by the generator $4$ - if you multiply every element of $\mathbb Z$ by 4, you will get $\langle 4 \rangle$

$\langle 4\rangle = 4 \mathbb Z = \lbrace 4\cdot r \mid r \in \mathbb Z \rbrace = \lbrace \cdots, -12, -8, -4 , 0, 4, 8, 12, \cdots \rbrace$

An ideal partitions the original ring into equivalence classes called cosets. E.g., $\langle 4 \rangle$ partitions $\mathbb Z$ into 4 equivalence classes or cosets.

Now let’s consider the sets

$4 \mathbb Z + 1 = \lbrace -11, -7, -3, 1, 5, 9, 13, \cdots \rbrace $

$4 \mathbb Z + 2 = \lbrace -10, -6, -2, 2, 6, 10, 14, \cdots \rbrace $

$4 \mathbb Z + 3 = \lbrace -9, -5, -1, 3, 7, 11, 15, \cdots \rbrace $

And of course,

$4\mathbb Z + 0 = 4\mathbb Z = \lbrace \cdots, -12, -8, -4 , 0, 4, 8, 12, \cdots \rbrace$

Note that except for $4\mathbb Z + 0$ i.e. $ 4\mathbb Z$ (the ideal), the other 3 are sets and not rings

Any element of $\mathbb Z$ can be considered to be part of only one of these cosets. Consider 2 elements $a,b \in \mathbb Z$, they belong to the same coset if $a - b \in \langle 4 \rangle$

Any element like $-7, -3,1, 5,9, 13$ which belongs to the same coset can be denoted as $[1] = 1 + \langle 4 \rangle$ -

Likewise we have $[0], [2], [3]$

Each of these sets are considered an equivalence class called a coset, these 4 cosets form a quotient ring denoted by

$\mathbb Z /4 \mathbb Z = \lbrace [0], [1], [2], [3]\rbrace$

It’s also denoted as $\mathbb Z/\langle 4 \rangle = \mathbb Z/ 4 \mathbb Z$

For brevity, the equivalence class symbol is also omitted occasionally

$\mathbb Z/\langle 4 \rangle = \mathbb Z/ 4 \mathbb Z = \lbrace 0, 1, 2, 3\rbrace$

Now, let’s do something similar for constructing extension fields. Consider the Polynomial Ring $\mathbb{F}_2[x]$, which consists of all polynomials with coefficients from the field $\mathbb{F}_2 = \lbrace 0, 1\rbrace$

$\mathbb{F}_2[x] = \lbrace 0, 1, x, x+1, x^2, x^2+1, x^2+x, x^2+x+1, x^3, \cdots\rbrace$

$\langle x^3 + x + 1 \rangle$ is an Ideal of the ring $\mathbb{F}_2[x]$ which can be generated by the generator $x^3 + x + 1$

The ideal $\langle x^3 + x + 1 \rangle$ is generated by multiplying every polynomial in $\mathbb{F}_2[x]$ by $x^3 + x + 1$

$\langle x^3 + x + 1 \rangle = \lbrace (x^3 + x + 1) \cdot r(x) \mid r(x) \in \mathbb{F}_2[x] \rbrace$

$\langle x^3 + x + 1 \rangle = \lbrace 0, x^3 + x + 1, x\cdot(x^3 + x + 1), (x+1)\cdot(x^3 + x + 1), \cdots \rbrace$

As we saw in the $4\mathbb Z$ case, an ideal partitions the original ring into equivalence classes called cosets

Because the generator has a degree of 3, polynomial long division guarantees that every polynomial leaves a remainder of degree 2 or less. There are 8 such remainders. So $\langle x^3 + x + 1 \rangle$ partitions $\mathbb{F}_2[x]$ into $2^3 = 8$ equivalence classes or cosets.

Now let’s consider the 8 sets (none of these are subrings except the ideal itself):

$\langle x^3 + x + 1 \rangle + 0 = \lbrace 0, x^3+x+1, x^4+x^2+x, \cdots\rbrace$

$\langle x^3 + x + 1 \rangle + 1 = \lbrace 1, x^3+x, x^4+x^2+x+1, \cdots\rbrace$

$\langle x^3 + x + 1 \rangle + x = \lbrace x, x^3+1, x^4+x^2, \cdots\rbrace$

$\langle x^3 + x + 1 \rangle + (x + 1) = \lbrace x+1, x^3, x^4+x^2+1, \cdots\rbrace$

$\langle x^3 + x + 1 \rangle + x^2 = \lbrace x^2, x^3+x^2+x+1, x^4+x, \cdots\rbrace$

and so on …

Each of these cosets is of the form $I + r(x)$

where the Ideal we are quotienting by is $I = \langle x^3 + x + 1 \rangle$. Since the ideal is of degree 3, the remainder $r(x)$ has to be of degree 2 or lesser.

So $r(x) = a_0 + a_1x + a_2x^2$ where $a_i \in \mathbb F_2$ i.e. $\lbrace 0,1\rbrace$

Writing this is very cumbersome, so we use a map

$\phi: \mathbb F_2[x]/I \rightarrow \mathbb F_2[\alpha]$

$\phi(I + r(x)) = r(\alpha)$

$r(\alpha) = a_0 + a_1\alpha + a_2\alpha^2$ where $a_0, a_1, a_2 \in \mathbb F_2$ i.e. $\lbrace 0,1\rbrace$

Applying this mapping to all 8 cosets yields the explicit elements of the field:

$\mathbb F_2[x] / \langle x^3 + x + 1 \rangle \cong \mathbb F_{2^3} = \lbrace 0, 1, \alpha, \alpha+1, \alpha^2, \alpha^2+1, \alpha^2+\alpha, \alpha^2+\alpha+1 \rbrace$

Enumerating Elements (Polynomial basis)

Writing out all polynomials by permuting the coefficients $f_0, f_1, …$ etc can be done quickly using a radix representation.

We know $\mathbb F_{2^4}$ has 16 elements, so consider the numbers $ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ,10, 11, 12, 13, 14, 15 $

Since $\mathbb F_{2^4}$ is an extension field of $\mathbb F_2$, we take the base $2$ representation of the $16$ numbers & use that as coefficients of the polynomial basis representation of the elements

$0$ is $0000$ i.e. $0\alpha^3 + 0\alpha^2 + 0\alpha^1 + 0\alpha^0 = 0$

$1$ is $0001$ i.e. $0\alpha^3 + 0\alpha^2 + 0\alpha^1 + 1\alpha^0 = 1$

$2$ is $0010$ i.e. $0\alpha^3 + 0\alpha^2 + 1\alpha^1 + 0\alpha^0 = \alpha$

….

$5$ is $0101$ i.e. $0\alpha^3 + 1\alpha^2 + 0\alpha^1 + 1\alpha^0 = \alpha^2 + 1$

$\cdots$

$10$ is $1010$ i.e. $1\alpha^3 + 0\alpha^2 + 1\alpha^1 + 0\alpha^0 = \alpha^3 + \alpha$

and so on & so forth.

We will end up with the same set of elements as before.

Likewise $\mathbb F_{3^2}$ can be written out using the base 3 representations of $ 0, 1, 2, 3, 4, 5, 6, 7, 8$ - i.e. $\lbrace 0, 1, 2, \alpha, \alpha + 1, \alpha+2, 2\alpha, 2\alpha +1, 2\alpha+2\rbrace$

Group Operations

Addition

Addition of field elements in an extension field $\mathbb F_{p^n}$ is the usual addition of polynomials, with coefficient addition performed modulo $p$.

E.g., in $\mathbb F_{2^4}$, $(\alpha^2 + \alpha + 1) + (\alpha^3 + \alpha + 1) = \alpha^3 +\alpha^2 + (\alpha + \alpha) + (1 + 1)$

Now, $\alpha + \alpha = 2\alpha \bmod 2 = 0$ and $1 + 1 = 2 \bmod 2 = 0$

So

$(\alpha^2 + \alpha + 1) + (\alpha^3 + \alpha + 1) = \alpha^3 + \alpha^2$

Multiplication

When we multiply 2 elements of an extension field, it’s done modulo the irreducible polynomial used to construct the extension.

Let’s take $\mathbb F_{2^4} \cong \mathbb F_2[x]/\langle x^4 + x + 1\rangle$

Multiplying 2 elements $e_1(\alpha)$ & $e_2(\alpha)$ is done as $e_1(\alpha) \cdot e_2(\alpha) \pmod {\alpha^4 + \alpha + 1}$

Let’s multiply the elements $(\alpha^3 + \alpha + 1) * (\alpha+1)$

This gives us $\alpha^4 + \alpha^3 + \alpha^2 + 1$. We now have to divide this with the irreducible polynomial (modulus)

i.e $\alpha^4 + \alpha^3 + \alpha^2 + 1 \pmod {\alpha^4 + \alpha + 1}$

Doing polynomial long division we get a remainder $\alpha^3 + \alpha^2 -\alpha$

In $\bmod 2$, $-\alpha$ is the same as $+\alpha$, so this can be written as $\alpha^3 + \alpha^2 + \alpha$.

So we get $(\alpha^3 + \alpha + 1) * (\alpha+1) = \alpha^3 + \alpha^2 + \alpha$

We can get to the same answer using the substitution trick we used earlier.

$\alpha^4 + \alpha + 1 = 0 $, so $\alpha^4= \alpha + 1$

Substituting this in the product of the 2 elements $\alpha^4 + \alpha^3 + \alpha^2 + 1$ we get $ \alpha + 1 + \alpha^3 + \alpha^2 + 1 = \alpha^3 + \alpha^2 + \alpha$ which is the same remainder we got by long division

Isomorphism

There are multiple irreducible polynomials of the same degree in the Polynomial ring $\mathbb F_p[x]$. So $\mathbb F_{p^n}$ can be constructed by quotienting by different irreducible polynomials.

Let’s construct two extension fields of $\mathbb F_2$ using two different irreducible polynomials $(x^3 + x^2 + 1)$ and $(x^3 + x + 1)$

Field A : $\mathbb F_{2^3} \cong \mathbb F_2[x]/\langle x^3 + x^2 + 1 \rangle $

Field B : $\mathbb F_{2^3} \cong \mathbb F_2[x]/\langle x^3 + x + 1 \rangle$

Both fields have the same set of 8 elements when written in polynomial basis

$ \lbrace 0, 1, \alpha, \alpha^2, \alpha + 1, \alpha^2 + \alpha, \alpha^2 + \alpha + 1, \alpha^2 + 1\rbrace$

Let’s multiply 2 elements

$(\alpha + 1).(\alpha^2 + 1) = \alpha^3 + \alpha^2 +\alpha + 1$

But to complete the operation we need to modulo $\alpha^3 + \alpha^2 + \alpha +1$ with the irreducible polynomial in each of the 2 extensions

• In $\mathbb F_2[x]/\langle x^3 + x^2 + 1 \rangle$,

$\qquad\qquad \alpha^3 + \alpha^2 + 1 = 0 $, so $\alpha^3 = \alpha^2 + 1 $

$\qquad\qquad$ so $\alpha^3 + \alpha^2 + \alpha + 1\pmod {\alpha^3 + \alpha^2 + 1} = \alpha^2 + 1 + \alpha^2 + \alpha + 1 = \alpha $

$\qquad\qquad$ i.e. $(\alpha + 1).(\alpha^2 + 1) = \alpha $

• In $\mathbb F_2[x]/\langle x^3 + x + 1 \rangle$,

$\qquad\qquad \alpha^3 + \alpha + 1 = 0 $, so $\alpha^3 = \alpha + 1 $

$\qquad\qquad$ so $\alpha^3 + \alpha^2 + \alpha + 1\pmod {\alpha^3 + \alpha + 1} = \alpha + 1 + \alpha^2 + \alpha + 1 = \alpha^2 $

$\qquad\qquad$ i.e. $(\alpha + 1).(\alpha^2 + 1) = \alpha^2 $

So even though the elements look the same, they aren’t actually identical extension fields. However, they are isomorphic fields. If we call the 2 fields, Field A and Field B, there exists a bijective map $\phi:\space$ Field $A$ $\rightarrow$ Field $B$ that preserves both addition and multiplication. This means if $e_1\cdot f_1=g_1$ in Field A, then $\phi(e_1)\cdot \phi(f_1)=\phi(g_1)$ in Field B. The labels change, but the underlying structure remains identical.

Primitive Polynomials

There may be multiple irreducible polynomials of a particular degree in a Polynomial Ring. However, all of them aren’t primitive polynomials. A primitive polynomial is an irreducible polynomial whose root can generate all elements of the extension field.

We used $x^4 + x + 1$ for constructing $\mathbb F_{2^4}$.

$x^4 + x +1$ other than being an irreducible polynomial is also a primitive one. If $\alpha$ is the root of this polynomial, then $\alpha^4 + \alpha + 1 =0 $

So, $\alpha^4 = -\alpha -1= \alpha + 1$ (because $-1 \bmod 2 \equiv 1$ )

So, $\alpha^4 = \alpha+1$

We can write out the list of elements of $\mathbb F_{2^4} = \lbrace 0, 1, \alpha, \alpha^2, \alpha^3, \alpha^4, \alpha^5, \alpha^6, \alpha^7, \alpha^8, \alpha^9, \alpha^{10}, \alpha^{11}, \alpha^{12}, \alpha^{13}, \alpha^{14} \rbrace$

Now, we know $\alpha^4 = \alpha+1$

So,

$\alpha^5 = \alpha^4 \cdot \alpha = (\alpha+1)\cdot \alpha = \alpha^2 + \alpha$

$\alpha^6 = \alpha^5 \cdot \alpha = (\alpha^2 + \alpha) \cdot \alpha = \alpha^3 + \alpha^2$

$\alpha^7 = \alpha^6 \cdot \alpha = (\alpha^3 + \alpha^2)\cdot \alpha =\alpha^4 + \alpha^3 = \alpha+1 + \alpha^3 = \alpha^3 + \alpha + 1$

We continue this way, till we get

$\alpha^{14} = \alpha^3 + 1$

So,

$\mathbb F_{2^4} = \lbrace 0, 1, \alpha, \alpha^2, \alpha^3, \alpha + 1, \alpha^2 + \alpha, \alpha^3 + \alpha^2, \alpha^3 + \alpha + 1, \alpha^2 + 1, \alpha^3 + \alpha, \alpha^2 + \alpha + 1, \alpha^3 + \alpha^2 + \alpha, \alpha^3 + \alpha^2 + \alpha + 1, \alpha^3 + \alpha^2 + 1, \alpha^3 + 1 \rbrace$

Let’s try this for $\mathbb F_{3^2}$

$\mathbb F_{3^2} = \lbrace 0, 1, \alpha, \alpha^2, \alpha^3, \alpha^4, \alpha^5, \alpha^6, \alpha^7\rbrace$

The irreducible degree 2 polynomial in $\mathbb F_3$ is $x^2 + 2x + 2$

So $\alpha^2 + 2\alpha + 2 = 0$

$\alpha^2 = -2\alpha -2 = \alpha + 1 $ (because $-2 \bmod 3 \equiv 1$ )

So $\mathbb F_{3^2} = \lbrace 0, 1, \alpha, \alpha^2, \alpha^3, \alpha^4, \alpha^5, \alpha^6, \alpha^7\rbrace$

$\alpha^2 = \alpha +1$

$\alpha^3 = \alpha^2 + \alpha = \alpha + 1 + \alpha = 2\alpha + 1$

$\alpha^4 = 2\alpha^2 + \alpha = 2\alpha + 2 + \alpha = 2$

$\alpha^5 = 2\alpha$

$\alpha^6 = 2\alpha^2 = 2\alpha + 2$

$\alpha^7 = 2\alpha^2 + 2\alpha = 2\alpha + 2 + 2\alpha = \alpha + 2$

$\alpha^8 = \alpha^2 + 2\alpha = \alpha+1 + 2\alpha = 1$

So,

$\mathbb F_{3^2} =\lbrace 0,1, \alpha, \alpha + 1, 2\alpha + 1, 2, 2\alpha, 2\alpha + 2, \alpha + 2\rbrace$

This way of writing out the elements works only you are quotienting the root of a primitive polynomial.

All irreducible polynomials of degree $2$ & $3$ in $\mathbb F_2[x]$ are primitive.

However, from degree $4$ on, this may not be true. There are $3$ degree $4$ irreducible polynomials in $\mathbb F_2[x]$ but only 2 of them are primitive polynomials - $x^4+ x + 1$ & $x^4 + x^3 + 1$. The 3rd $x^4 + x^3 + x^2 + x + 1$ isn’t primitive. When we construct $\mathbb F_{2^4}$ by adjoining the root of non-primitive polynomials, we will still end up with 16 elements & it will also be an extension field $\mathbb F_{2^4}$ but the root will not generate all the elements, it will only generate a cyclic subgroup of the field before repeating.

Let’s construct $\mathbb F_{2^4}$ by adjoining the root of $x^4 + x^3 + x^2 + x + 1$ - let’s say the root is $\beta$ (I am using a diff label just for differentiating between the root of a primitive & non-primitive polynomial - you can use $\alpha$ also if you want).

Since $\beta$ is a root, $\beta^4 + \beta^3 + \beta^2 + \beta + 1 = 0$

So, $\beta^4 = \beta^3 + \beta^2 + \beta + 1$.

Now let’s try the powers $\lbrace 0, 1, \beta, \beta^2, \beta^3, \beta^4, \beta^5, \beta^6, \beta^7, \beta^8, \beta^9, \beta^{10}, \beta^{11}, \beta^{12}, \beta^{13}, \beta^{14} \rbrace$

$\beta^4 = \beta^3 + \beta^2 + \beta + 1$

$\beta^5 = \beta^4 \cdot \beta = \beta^4 + \beta^3 + \beta^2 + \beta = \beta^3 + \beta^2 + \beta + 1 + \beta^3 + \beta^2 + \beta = 1$

Likewise

$\beta^6 = \beta$,

$\beta^7 = \beta^2$

$\beta^8 = \beta^3$

$\beta^9 = \beta^3 + \beta^2 + \beta + 1$

$\beta^{10} = 1$ & so on

So it generates only 5 elements of the field which form a subfield of $\mathbb F_{2^4}$. The multiplicative order of the root of a primitive polynomial is $p^n - 1$ i.e. $15$ in this case. Whereas the order of $\beta$ is 5.

The extension fields constructed by adjoining the root of a primitive polynomial and the root of a non-primitive polynomial ($\alpha$ & $\beta$ respectively in our examples) are isomorphic. There are multiple maps, one of the maps maps $\beta$ to $\alpha^3$. Both $\alpha^3$ & $\beta$ have a multiplicative order of 5 in their respective fields. $x^4 + x^3 + x^2 + x + 1$ is the minimal polynomial of $\alpha^3$ - we discuss minimal polynomials in the next section

Minimal Polynomials

We took an irreducible polynomial in the Polynomial Ring of the base field & used it to construct the extension field. We now go the opposite way. We take an element of an extension field & find its minimal polynomial in the Polynomial Ring of the base field.

Every element of an extension field ($\mathbb F_{p^n}$) is the root of infinitely many polynomials in $\mathbb F_p[x]$. Among all of them, there is exactly one monic irreducible polynomial of the smallest degree. It is called the minimal polynomial of that element. For any element $\beta$ in $\mathbb F_{p^n}$, the minimal polynomial $M(x)$ is the least degree monic polynomial in $\mathbb F_p[x]$ for which $M(\beta) = 0$

In the previous section, we saw that the minimal polynomial of the element $\alpha^3$ of $\mathbb F_2[x]/\langle x^4 + x + 1 \rangle$ was $x^4 + x^3 + x^2 + x + 1$ which is of degree 4 - i.e. same as the degree of the irreducible polynomial used to construct the field. This isn’t always so. It can be of any degree which divides the degree of the extension field - i.e. for the elements of $\mathbb F_{2^4}$, the minimal polynomial can be of degree 1, 2 or 4 since all of them divide 4, the degree of the extension.

$\mathbb F_2[x]/\langle x^4 + x + 1 \rangle = \lbrace 0, 1, \alpha, \alpha + 1, \alpha^2, \alpha^2 + 1, \alpha^2 + \alpha, \alpha^2 + \alpha + 1, \alpha^3, \alpha^3 + 1, \alpha^3 + \alpha, \alpha^3 + \alpha + 1, \alpha^3 + \alpha^2, \alpha^3 + \alpha^2 + 1, \alpha^3 + \alpha^2 + \alpha, \alpha^3 + \alpha^2 + \alpha + 1 \rbrace$

You can find the minimal polynomial of any of these elements using conjugates.

For any element $\beta$, its conjugates are $\beta$,$\beta^p, \beta^{p^2},\beta^{p^3}, \beta^{p^4}, \cdots $ - i.e. you get it by repeatedly raising to the $p$th power. Also, $\alpha^{15} = 1$, i.e. the powers of $\alpha$ cycle after $\alpha^{15}$. So you can take conjugates till a conjugate repeats.

We can construct the minimal polynomial of any element $\beta$ by using its conjugates.

For $\alpha^3$, the conjugates are $\alpha^3, \alpha^6, \alpha^{12}, \alpha^9$ (it cycles after this). So the minimal polynomial of $\alpha^3$ is $(x - \alpha^3) \cdot (x - \alpha^6) \cdot (x - \alpha^{12})\cdot (x- \alpha^9)$. If you multiply these, you will end up with $x^4 + x^3 + x^2 + x + 1$ which we already know is the minimal polynomial of $\alpha^3$. It’s also the minimal polynomial of $\alpha^6$, $\alpha^9$ and $\alpha^{12}$ because they share the same conjugates.

Let’s try finding the minimal polynomial for a different element $\alpha^2 + \alpha$.

For convenience, I have denoted $\alpha$ as $a$ in sage.

sage: R.<x> = PolynomialRing(GF(2))
sage: F16.<a> = GF(16, modulus = x^4 + x + 1)
sage: b = a^2 + a
sage: b.multiplicative_order()
3
sage: b, b^2, b^4
(a^2 + a, a^2 + a + 1, a^2 + a)

As you see, it cycles after the 2nd element itself, this is because its order is 3

sage: (x - b) * (x - b^2)
x^2 + x + 1

So the minimal polynomial of $\alpha^2 + \alpha$ is $x^2 + x + 1$

Use of $\mathbb F_{2^8}$ in AES

AES uses the extension field $\mathbb F_{2^8}$ constructed using the irreducible polynomial $x^{8} + x^{4} + x^{3} + x + 1$ over $\mathbb F_2$ - i.e $\mathbb{F}_{2}[x]/\langle x^{8}+x^{4}+x^{3}+x+1\rangle $

One byte is 8 bits. It can represent $2^8 = 256$ different values. If 2 bytes have to be multiplied, each byte is represented as a polynomial (the bits of the byte form the coefficients of the polynomial) of degree 7 or less. After multiplying the 2 polynomials, they are reduced modulo the irreducible polynomial of degree 8, which results in a polynomial of degree 7 or lesser which will again fit in a byte, thereby providing closure.

Polynomials in Extension Fields

The irreducible polynomials discussed earlier were in the base field - for e.g., $x^4+ x + 1$ which is the irreducible polynomial we used to generate $\mathbb F_{2^4}$ is a polynomial in $\mathbb F_2[x]$ - all its coefficients are in $\mathbb F_2$. Likewise the AES irreducible polynomial is also in $\mathbb F_2[x]$.

We can also have polynomials in the Polynomial Ring of the extension field i.e. polynomials whose coefficients are from the extension field.

for e.g., the polynomial $x^6 + (\alpha^2+1)x^4 + x^3 + (\alpha^2+\alpha+1)x + (\alpha+1)$ is in $\mathbb F_{2^3}[x]$. For convenience, sometimes this polynomial is also written as $x^6 + 5x^4 + x^3 + 7x + 3$ though it’s not absolutely correct.

Elliptic Curves over Extension Fields

Elliptic Curves over Finite fields (including ones over Extension Fields) have 2 algebraic structures involved.

• When an Elliptic curve is defined over a Field $\mathbb F_p$ or $\mathbb F_{p^k}$, then the coordinates of the equation of the curve are elements of the field - this field is also called the underlying Field.

• The points on the curve form a separate Group - the operation of the group is addition of points in the group. The x & y co-ordinates of the points in this group are elements from Field $\mathbb F_p$ or $\mathbb F_{p^k}$ though.

Let’s look at Elliptic Curves over Extension fields using this curve $E: y^2 + xy = x^3 + a_2x^2 + a_6$ over the extension field $\mathbb F_{2^k}$. (This curve equation is in the long Weierstrass form $E:y^2+a_1 xy+a_3 y=x^3+a_2 x^2+a_4 x+a_6$ with $a_1 = 1, a_3 = 0$ and $a_4 = 0$)

Group Operations

Point Addition

Let $P = (x_1, y_1)$ and $Q = (x_2, y_2) \in E(\mathbb F_{2^k})$, where $P \ne \pm Q$.

Then $P + Q = (x_3, y_3)$, with

$x_3 = \lambda^2 + \lambda + x_1 + x_2 + a$

$y_3 = \lambda (x_1 + x_3)+ x_3 + y_1$

with $\lambda = \frac {y_1 + y_2}{x_1 + x_2}$

Point Doubling

$P + P = 2P = (x_3, y_3)$

$x_3 = \lambda^2 + \lambda + a$

$y_3 = {x_1}^2 + \lambda x_3 + x_3$

with $\lambda = x_1 + \frac {y_1}{x_1}$

Negative

$P = (x, y)$

$-P = (x, x + y)$

Construction

Let’s construct this curve over $\mathbb F_{2^4}$.

$E: y^2 + xy = x^3 + a_2x^2 + a_6$

Let,

$a_2 = \alpha^3$ (i.e. the bitstring [1000])

$a_6 = \alpha^3 + 1$ (i.e. the bitstring [1001])

So the Curve Equation is $E: y^2 + xy = x^3 + {\alpha^3}x^2 + (\alpha^3 + 1)$

The x & y coordinates of each point on the Curve are also in the field $\mathbb F_{2^4}$. So x & y can be represented using polynomial basis representation.

The Elliptic Curve Group has 22 points including the Point at Infinity.

Using the group operations specified above, let’s see how point addition & point doubling is done.

Addition

$P = E(\alpha, \alpha^3 + \alpha^2 + \alpha + 1)$
$Q = E(\alpha^3 + \alpha^2, \alpha^3 + \alpha^2)$

The irreducible polynomial is $\alpha^4 + \alpha + 1$.

We want to add $P + Q$. Let’s use the Group Law formulas to add the points.

We have 2 polynomial basis representations here - the coordinates of the Elliptic Curve equation are represented as polynomials & the x & y coordinates of the Curve points are also individually represented as polynomials.

sage: F1.<α> = GF(2^4)
sage: F1.polynomial()
α^4 + α + 1
sage: x1 = F1(α)
sage: y1 = F1(α^3 + α^2 + α + 1)
sage: x2 = F1(α^3 + α^2)
sage: y2 = F1(α^3 + α^2)
sage: λ = (y1 + y2)/(x1 + x2)
sage: a = F1(α^3)
sage: b = F1(α^3 + 1)
sage: x3 = λ^2 + λ + x1 + x2 + a
sage: y3 = λ*(x1 + x3)+ x3 + y1
sage: x3
1
sage: y3
1

So we get $P + Q = E(1,1)$

Doubling

Next is Doubling i.e. $2P$

sage: λ = x1 + y1/x1
sage: x3 = λ^2 + λ + a
sage: y3 = x1^2 +λ*x3 + x3
sage: x3
α^3 + α + 1
sage: y3
α

So $2P = E(\alpha^3 + \alpha + 1, \alpha)$

We used the group law calculations to do the above to understand it better. But everything can be done using Sagemath’s in-built EllipticCurve object as shown below

sage: F1.<α> = GF(2^4)
sage: E1 = EllipticCurve(F1, [1, α^3, 0, 0, α^3 + 1])
sage:
sage: Elist = E1.points()
sage: P = Elist[5]
sage: P
(α : α^3 + α^2 + α + 1 : 1)
sage: Q = Elist[19]
sage: Q
(α^3 + α^2 : α^3 + α^2 : 1)
sage: P + Q
(1 : 1 : 1)
sage: 2*P
(α^3 + α + 1 : α : 1)