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

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?

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

• Thank you for your very clear answer! I just have one clarification question- so by saying $\alpha^2 = -\alpha - 1$ you're basically just establishing if we add or multiply $\alpha_1, \alpha_2 \in \mathbb{F}_4$ then we get back something of the form $c + d\alpha$? – quietkid Apr 18 at 5:47
• @quietkid yes exactly. If we had a degree 3 extension like $\mathbf F_{5^3}$ it would be $\alpha^3 = ...$ instead but multiplying two things of the form $a+b\alpha + c \alpha^2$ gives you something of the same form again – Alex J Best Apr 18 at 6:32

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.

• Thank you very much! I never considered elliptic curves like this before. If you don't mind me asking, what do you mean by " The elements are not number and not exactly polynomials either (rather their equivalence classes)."? – quietkid Apr 18 at 5:53
• Normally when we say a curve, we mean set of points whose $x$ and $y$ co-ordinates are ordinary numbers satisfying some condition (for example, in a circle it could be $x^2+y^2= 25$). Here they are from a finite field whose elements are not numbers. In mod $17$ arithmetic $12+8$ is $7$ So 12, 8 are not numbers. In numbers (positive) addition will yield a bigger result. Same way multiplication of two polynomials normally would yield a polynomial of higher degree, here it can be less. Please go ahead learn finite field theory keeping in mind what I have said. – P Vanchinathan Apr 18 at 6:07
• The example given in the above comment must be taken for mod 13 arithmetic, and not in mod 17 which is an error. – P Vanchinathan Apr 18 at 23:32