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 it’s 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[x]$​, we can construct an extension field of $\mathbb F_p[x]$​ 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$

Quotienting

There is another notation to denote the same field.

$\mathbb F_{2^4} = \mathbb F_2[\alpha]/\langle \alpha^4 + \alpha + 1 \rangle$

To understand why this notation is used, 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 | 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. for 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 = \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$

Consider the Polynomial Ring $\mathbb{F}_2[\alpha]$, which consists of all polynomials in the variable $\alpha$ with coefficients from the field $\mathbb{F}_2 = \lbrace 0, 1\rbrace$

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

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

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

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

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

As we saw in $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 \alpha^3 + \alpha + 1 \rangle$ partitions $\mathbb{F}_2[\alpha]$ 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 \alpha^3 + \alpha + 1 \rangle + 0 = \lbrace 0, \alpha^3+\alpha+1, \alpha^4+\alpha^2+\alpha, \cdots\rbrace$

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

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

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

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

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

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

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

Any element of $\mathbb{F}_2[\alpha]$ can be considered to be part of only one of these cosets. Consider 2 polynomials $f(\alpha), g(\alpha) \in \mathbb{F}_2[\alpha]$, they belong to the same coset if $f(\alpha) - g(\alpha) \in \langle \alpha^3 + \alpha + 1 \rangle$

Any polynomial like $\alpha^3$ or $\alpha^4+\alpha^2+1$ reduces to a remainder of $\alpha+1$ and can be denoted as $[\alpha+1] = (\alpha+1) + \langle \alpha^3 + \alpha + 1 \rangle$. Likewise we have $[0], [1], [\alpha], [\alpha+1], [\alpha^2], [\alpha^2+1], [\alpha^2+\alpha], [\alpha^2+\alpha+1]$. Each of these sets is considered an equivalence class called a coset; these 8 cosets form a finite quotient ring denoted by:

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

Like before, the $[]$ notation of denoting a coset is sometimes omitted for brevity

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$.

for 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[\alpha]/\langle \alpha^4 + \alpha + 1\rangle$

Multiplying 2 elements $f(\alpha)$ & $g(\alpha)$ is done as $f(\alpha) \cdot g(\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 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 both 2 different irreducible polynomials $(x^3 + x^2 + 1)$ and $(x^3 + x + 1)$

Field A $: \mathbb F_2[\alpha]/\langle \alpha^3 + \alpha^2 + 1 \rangle $

Field B $: \mathbb F_2[\alpha]/\langle \alpha^3 + \alpha + 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[\alpha]/\langle \alpha^3 + \alpha^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[\alpha]/\langle \alpha^3 + \alpha + 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$:Field A $\mapsto$ 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 contructing $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 if it’s a primitive polynomial. All irreducible polynomials of degree $2$ & $3$ in $\mathbb F_2[\alpha]$ are both irreducible & primitive.

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

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

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

Now let’s try the powers $\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$

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

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

Likewise

$\alpha^6 = \alpha$,

$\alpha^7 = \alpha^2$

$\alpha^8 = \alpha^3$

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

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

So it generates only 5 elements of the field each thrice

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}[\alpha]/\langle \alpha^{8}+\alpha^{4}+\alpha^{3}+\alpha+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 it’s coefficients are in $\mathbb F_2$. Likewise the AES irreductible 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 polynomail basis representation.

The Elliptic Curve Group has 22 points. These are the 21 elements excluding 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)