Elliptic Curves Over Finite Fields

Learn the basic theory of elliptic curves over finite fields in this lesson.


So far, we suggested that EE be an elliptic curve over any field K\mathbb{K}. In this section, we introduce the basic theory of elliptic curves over finite fields, which is an important case since such kinds of curves are used to build cryptographic systems. However, we just consider curves over finite fields Fp\mathbb{F}_{p} with p>3p>3 prime. Under this condition, we can consider without loss of generalization the curve EE in the short Weierstrass form

y2=x3+Ax+B(1),y^{2}=x^{3}+A x+B\quad\quad\quad (1),

where A,BFpA, B \in \mathbb{F}_{p} and the discriminant is Δ=16(4A3+27B2)0\Delta=-16\left(4 A^{3}+27 B^{2}\right) \neq 0.

A very important verdict is that the addition formulas and the group law we attained in the last lesson also hold over finite fields. Since there are only finitely many pairs of coordinates (x,y)(x, y) with x,yFpx, y \in \mathbb{F}_{p}, the group

E(Fp)={(x,y)Fp×Fp:y2=x3+Ax+B}{O}.E\left(\mathbb{F}_{p}\right)=\left\{(x, y) \in \mathbb{F}_{p} \times \mathbb{F}_{p}: y^{2}=x^{3}+A x+B\right\} \cup\{\mathcal{O}\}.

is finite as well.

Examples of elliptic curves over Fp\mathbb{F}_{p}

In the very first step, we want to determine how elliptic curves are acting over finite fields Fp\mathbb{F}_{p}, where pp is a prime p>3p>3. For our first examples, we look to very small groups E(Fp)E\left(\mathbb{F}_{p}\right) and how these groups are constructed. For this, we need the following definition:

Quadratic residue

Let Fp\mathbb{F}_{p} be a finite field. An element uFp=Fp\{0}u \in \mathbb{F}_{p}^{*}=\mathbb{F}_{p} \backslash\{0\} is called a quadratic residue if the equation x2=ux^{2}=u has a solution in Fp.\mathbb{F}_{p} . Otherwise, uu is called a quadratic nonresidue.

Example 1

Let F=Z11\mathbb{F}=\mathbb{Z}_{11}. Then, we can calculate x2x^{2} for every xZ11x \in \mathbb{Z}_{11}^{*}, as shown in the table given below.

Get hands-on with 1200+ tech skills courses.