Polynomials and Elliptic Curves over Extension Fields
Polynomial Basis Representation in Extension Fields
For a field $\mathbb F_p$, extension fields are of the form $\mathbb F_{p^k}$.
Let’s first look at Binary extension fields i.e. extension fields $\mathbb F_{2^k}$ where $p = 2$.
Each element of $\mathbb F_{2^k}$ can be represented as a polynomials & each of these polynomials have their coefficients in the field $\mathbb F_2$ = {0,1}. The degree of the polynomial is less than or equal to $k  1$. Each element $A(x)$ in $\mathbb F_{2^k}$ would be of the form $a_{k1}t^{k1} +a_{k2}t^{k2} +…+ a_{2}t^{2} +a_{1}t + a_0$ with $a_i \in \mathbb F_2 = \lbrace 0,1 \rbrace$
Let’s take $\mathbb F_{2^4}$  here the polynomials will be of the form $a_{3}t^3 + a_{2}t^2 + a_{1}t + a_0$ with each coefficient $a_i$ being equal to either 0 or 1. Since each coefficient of the polynomial is either 0 or 1, it’s similar to a bit & all the coefficients of one polynomial together can be considered as a bitstring or a vector space.
For e.g.
$0$ is $0000$ i.e. $0t^3 + 0t^2 + 0t^1 + 0t^0 = 0$
$1$ is $0001$ i.e. $0t^3 + 0t^2 + 0t^1 + 1t^0 = 1$
$2$ is $0010$ i.e. $0t^3 + 0t^2 + 1t^1 + 0t^0 = t$
….
$5$ is $0101$ i.e. $0t^3 + 1t^2 + 0t^1 + 1t^0 = t^2 + 1$
….
$10$ is $1010$ i.e. $1t^3 + 0t^2 + 1t^1 + 0t^0 = t^3 + t$
and so on & so forth.
So the 16 elements of $\mathbb F_{2^4}$ are
\[\left[ \begin{matrix} 0 & t^2& t^3 & t^3 +t^2 \\ 1 & t^2 +1 & t^3 +1 & t^3 +t^2 +1 \\ t & t^2 +t & t^3 +t & t^3 +t^2 +t \\ t +1 & t^2 +t +1 & t^3 +t +1 & t^3 +t^2 +t +1 \end{matrix} \right]\]corresponding to the polynomial basis representations of
\[\left[ \begin{matrix} 0 & 4 & 8 &12 \\ 1 & 5 & 9 & 13 \\ 2 & 6 & 10 & 14 \\ 3 & 7 & 11 & 15 \\ \end{matrix} \right]\]So, the finite field $\mathbb F_{2^k}$ can be viewed as bitstring or a vector space over its subfield $\mathbb F_2$. The 16 polynomials in $\mathbb F_{2^4}$ can be viewed as the bit representations of all the numbers {0, 1, …., 15} & the polynomials corresponding to them.
Group Operations
Addition
Addition of field elements is the usual addition of polynomials, with coefficient addition performed modulo 2 (which is also the same as XORing of the bitstrings)
For e.g. in $\mathbb F_{2^4}$, $(t^2 + t + 1) + (t^3 + t + 1) = t^3 +t^2 + (t + t) + (1 + 1)$
Now, $t + t = 2t \bmod 2 = 0$ and $1 + 1 = 2 \bmod 2 = 0$
So
$(t^2 + t + 1) + (t^3 + t + 1) = t^3 + t^2$
Multiplication
For a field $\mathbb F_{2^k}$, an irreducible binary polynomial P(t) of degree k is chosen (such a polynomial etists for any k and can be efficiently found). Multiplication of field elements (which are polynomials of degree $k1$ or lesser) is done modulo the irreducible polynomial.
For e.g. the irreducible polynomial for the Extension field $\mathbb F_{2^4}$is $t^4 + t + 1$
Let’s multiply the elements $(t^3 + t + 1) * (t+1)$
This gives us $t^4 + t^3 + t^2 + 1$. We now have reduce this mod the irreducible polynomial.
i.e $t^4 + t^3 + t^2 + 1 \bmod t^4 + t + 1$
Doing polynomial long division we get a remainder $t^3 + t^2 t$
In $\bmod 2$, $t$ is the same as $+t$, so this can be written as $t^3 + t^2 + t$.
So we get $(t^3 + t + 1) * (t+1) = t^3 + t^2 + t$
We can check both our addition & multiplication operations in SageMath
sage: F.<t> = GF(2^4) # Define our extension field
sage: F.modulus() # Irreducible polynomial
t^4 + t + 1
sage: Flist = F.list()
sage: Flist
[0,
t,
t^2,
t^3,
t + 1,
t^2 + t,
t^3 + t^2,
t^3 + t + 1,
t^2 + 1,
t^3 + t,
t^2 + t + 1,
t^3 + t^2 + t,
t^3 + t^2 + t + 1,
t^3 + t^2 + 1,
t^3 + 1,
1]
sage: Flist[7]
t^3 + t + 1
sage: Flist[10]
t^2 + t + 1
sage: Flist[10] + Flist[7] # Add (t^2 + t + 1) + (t^3 + t + 1)
t^3 + t^2
sage: Flist[4]
t + 1
sage: Flist[7]*Flist[4] # (Multiply t^3 + t + 1) * (t + 1)
t^3 + t^2 + t
The bitstring way of visualizing Extension fields works well for Binary Fields (extensions of $\mathbb F_2$). However, for Extension Fields $\mathbb F_{p^k}$ with $p \gt 2$, it’s much simpler to think of the extension field as the Quotient of a Polynomial Ring, so let’s first do the same for $\mathbb F_{2^4}$. It can be constructed as the Quotient of $\mathbb F_2(t)/\langle t^4 + t + 1 \rangle$  this is the Polynomial ring of $\mathbb F_2[x]$ quotiented by an ideal generated by an irreducible polynomial of degree $4$ in the Ring.
sage: R.<t> = PolynomialRing(GF(2))
sage: Q.<t> = R.quotient(t^4 + t + 1)
sage: for i in Q:
....: print(i)
....:
0
1
t
t + 1
t^2
t^2 + 1
t^2 + t
t^2 + t + 1
t^3
t^3 + 1
t^3 + t
t^3 + t + 1
t^3 + t^2
t^3 + t^2 + 1
t^3 + t^2 + t
t^3 + t^2 + t + 1
Extension fields where $p > 2$
Extension fields of $\mathbb F_p$ where $p > 2$ are also similar. With $p=2$, each element $A(x)$ in $\mathbb F_{2^k}$ would be of the form $a_{k1}t^{k1} +a_{k2}t^{k2} +…+ a_{2}t^{2} +a_{1}t + a_0$ with $a_i \in \mathbb F_2 = \lbrace 0,1 \rbrace$. For a general $p$, the $a_i$s would be in $F_p$ instead of $F_2$.
Use of $\mathbb F_{2^8}$ in AES
In AES, the extension field $\mathbb F_{2^8}$ is used with $t^{8} + t^{4} + t^{3} + t + 1$ as the irreducible polynomial. One byte is 256 bits (i.e. $2^8$). 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.
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 coordinates 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 = t^3$ (i.e. the bitstring [1000])
$a_6 = t^3 + 1$ (i.e. the bitstring [1001]))
So the Curve Equation is $E: y^2 + xy = x^3 + {t^3}x^2 + (t^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.
\[\left[ \begin{matrix} (0 , t^3 + t + 1) & (t + 1 , t^3 + t^2 + t + 1) & (t^3 , t^3 + 1) & (t^3 + t^2 , t^3 + t^2) \\ (1 , 0) & (t^2 + 1 , 0) & (t^3 + 1 , t^2 + t) & (t^3 + t^2 + t + 1 , t^2) \\ (1 , 1) & (t^2 + 1 , t^2 + 1) & (t^3 + 1 , t^3 + t^2 + t + 1) & (t^3 + t^2 + t + 1 , t^3 + t + 1) \\ (t , t^3 + t^2 + 1) & (t^2 + t + 1 , t^3 + t + 1) & (t^3 + t + 1 , t) \\ (t , t^3 + t^2 + t + 1) & (t^2 + t + 1 , t^3 + t^2) & (t^3 + t + 1 , t^3 + 1) \\ (t + 1 , t^3 + t^2) & (t^3, 1) & (t^3 + t^2 , 0) \end{matrix} \right]\]Using the group operations specified above, let’s see how point addition & point doubling is done.
Addition
$P = E(t, t^3 + t^2 + t + 1)$
$Q = E(t^3 + t^2, t^3 + t^2)$
The irreducible polynomial is $t^4 + t + 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.<t> = GF(2^4)
sage: F1.polynomial()
t^4 + t + 1
sage: x1 = F1(t)
sage: y1 = F1(t^3 + t^2 + t + 1)
sage: x2 = F1(t^3 + t^2)
sage: y2 = F1(t^3 + t^2)
sage: λ = (y1 + y2)/(x1 + x2)
sage: a = F1(t^3)
sage: b = F1(t^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
t^3 + t + 1
sage: y3
t
So $2P = E(t^3 + t + 1, t)$
We used the group law calculations to do the above to understand it better. But everything can be done using Sagemath’s inbuilt EllipticCurve object as shown below
sage: F1.<t> = GF(2^4)
sage: E1 = EllipticCurve(F1, [1, t^3, 0, 0, t^3 + 1])
sage:
sage: Elist = E1.points()
sage: P = Elist[5]
sage: P
(t : t^3 + t^2 + t + 1 : 1)
sage: Q = Elist[19]
sage: Q
(t^3 + t^2 : t^3 + t^2 : 1)
sage: P + Q
(1 : 1 : 1)
sage: 2*P
(t^3 + t + 1 : t : 1)