elliptic curve over nonprime finite field $\mathbb{F}_{p^n}$

Question

I am currently trying to conceptualize what an elliptic curve over the finite field $\mathbb{F}_{p^n}$ looks like where $p$ is an odd prime.

I have never taken a course on field theory so I am still trying to understand what a nonprime finite field is. On wikipedia https://en.wikipedia.org/wiki/Finite_field#Non-prime_fields it states a way to explicitly construct these fields.

But now my very basic question is these constructions involve polynomials, so how do we use this in the elliptic curve equation?

Answer 1

It might help you to think about the complex numbers, normally if we want define an equation whose coefficients are complex numbers we write it like $$y^2 = x^3 + (2+i) x + (1-i)$$ Here $i$ is the square root of $-1$ the only element we add to $\mathbf R$ to get $\mathbf C$, so $i$ satisfies the polynomial $x^2+1$. But we write complex numbers as a sum of a real number and a real number times $i$. We could write the relationship between $\mathbf C$ and $\mathbf R$ as $\mathbf C = \mathbf R [x]/(x^2+1)$.

You can think about this exactly the same in the finite field case, except that the polynomial our generator of the field extension satisfies might be more complicated than $x^2+1$. For instance $\mathbf F_{4} = \mathbf F_2[x]/(x^2+x+1)$ then we have an element $\alpha \in \mathbf F_4$ satisfying $\alpha^2 + \alpha +1 =0$ and so $\alpha^2 = -\alpha - 1$ and our field consists of elements of the form $c + d \alpha$ for $c,d\in \mathbf F_2$. So an equation for an elliptic curve could be $y^2 + (\alpha +1)y= x^3 + 1$.

Answer 2

There are polynomials at two layers.

LAYER 1:

This layer describes the elements of the non-prime field: For example, for the prime $p=5$ and $n=3$, the elements of the field of of order $p^3$ are given by polynomials of degree upto 2 ( 1 less than 3) with coefficients in the prime field of order 5.

There is way of adding them and multiplying them remaining within the set, and satisfying all conditions that define a field. The elements are not number and not exactly polynomials either (rather their equivalence classes). As elements can only be 'polynomials' of degree a most 2, multiplication might yield higher degree polynomial outside the set: then we use a 'mod' arithmetic, that is polynomial division with remainder, yielding a polynomial of degree less than 3 as the 'product'. Let us agree to denote elements of these field by polynomials $h(t),k(t)$ etc.

LAYER 2:

In this layer there is a specific polynomial (for each elliptic curve) of degree 3, call it $f(X)=X^3+aX+b$. The elliptic curve (excluding the point at infinity) consists of pairs of elements from the field, $(h(t), k(t))$ such that $k(t)^2 = h(t)^3 + a h(t) + b$. The point is simply denoted $(h(t), k(t))$.

As familiarity breeds contempt soon one starts writing $x, y$ for elements of the non-prime field, not bothering to give a special notation for them as polynomials.