Elliptic Curves Over Finite Fields

Introduction

So far, we suggested that $E$ be an elliptic curve over any field $\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 $\mathbb{F}_{p}$ with $p>3$ prime. Under this condition, we can consider without loss of generalization the curve $E$ in the short Weierstrass form

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

where $A, B \in \mathbb{F}_{p}$ and the discriminant is $\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)$ with $x, y \in \mathbb{F}_{p}$, the group

$$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 $\mathbb{F}_{p}$

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

Quadratic residue

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

Example 1

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