Part 2: Elliptic curve over finite fields

In a previous post in our series on elliptic curves (Part 1: What Are Elliptic Curves) we introduced elliptic curves and showed what they look like in the Cartesian plane when defined over the real numbers. Its is mandatory to have read the Part 1 of the series to understand this one. As explained, there are multiple algebraic equations that can define an elliptic curve. In this article, we will focus on the reduced Weierstrass equation when discussing elliptic curves.

Why integers and not real numbers ?

In modern cryptography, we prefer working with integers, mainly because they can easily represent real-world data such as text, and because they include prime numbers, which are the foundation of many hard mathematical problems essential to ensuring computational security. Furthermore, integers are straightforward to represent in computers using bits unlike real numbers, which are more complex to handle in digital systems.

In this article, we will explain how elliptic curves can be defined over finite fields of integers, and what operations can be performed on them.

From real numbers to integers fields

When we speak of elliptic curves over the real numbers, we mean that the coordinates of each point (x,y) on the curve are real-valued. To work in the integer setting, we restrict these coordinates to a finite set of integers, namely, those in a finite field.

Finite fields $F_p = Z/pZ$

We define $F_p = Z/pZ$ where :

• $Z$ is the set of all integers

• $p$ a prime number

• $F_p = Z/pZ$ is the set of integers modulo $p$, i.e., ${0,1,2,…,p−1}$

This set of numbers have some properties listed below:

• $F_p = Z/pZ$ contains exactly p elements.

• Every non-zero element has a multiplicative inverse in $F_p = Z/pZ$. In other words, for every $a \in F_p = Z/pZ, a \neq 0$, there exists an element $a^{-1} \in F_p$ such that $a.a^{-1} \equiv 1 \; \text{mod}\; p$.

• Arithmetic operations — addition, subtraction, multiplication, and division — are all performed modulo p.For example if $l = x+y$, this actually means:

$$l = x+y\; \text{mod}\; p$$

In practice, we often omit the $\text{mod}\; p$ notation, but it's always understood to be applied.

• $F_p = Z/pZ$ is a field, meaning it satisfies all the properties of a mathematical field: it has no zero-divisors, and every non-zero element has an inverse. This ensures that all basic arithmetic operations are well-defined and can be reversed (except for division by zero, which is never allowed).

Elliptic curves over $F_p = Z/pZ$

It is quite straightforward to adapt elliptic curves to the setting of finite fields, specifically $F_p = Z/pZ$. Here's how we proceed:

1. Define the finite field $F_p = Z/pZ$, where $p$ is a prime number.

2. Take the coefficients $a, b \in F_p$ and use the reduced Weierstrass :

$$y^2 = x^3 + ax + b \; (\text{mod} \; p)$$

Ensure that the discriminant $\Delta = 4a^3 + 27b^2 ≠ 0 \; (\text{mod} \; p)$.

1. Consider the set of all pairs $(x, y) ∈ F_p × F_p$ that satisfy this equation.

We can now state the formal definition:

Let $F_p = Z/pZ$ with $p ≥ 5$ a prime number. An elliptic curve $E$ over $F_p$ is defined by the equation:

$$y^2 \equiv x^3 + ax + b \; (\text{mod} \; p)$$

where $a, b ∈ F_p$, and $\Delta \neq 0\; (\text{mod p})$ This ensures that the curve is non-singular.

The set of all solutions is completed by adding a special point called the point at infinity, usually denoted by $O$, which acts as the identity element in the group of points on the curve.

The image below show how different curve representations are depending on the field.

On the left the curve $y^2 = x^3 -3x +1$ plotted over real numbers and on the right the same curve, but with points restricted to the finite field $F_p.$

Final thougths

As you've seen, moving from the real numbers to finite fields changes the visual and mathematical nature of elliptic curves. We go from smooth, continuous curves to sets of discrete points scattered in a bounded space. The number of points on such a curve is finite. In fact, it's always less than or equal to $p^2+1$.

The key idea is that we can define a group structure over the set of points on an elliptic curve defined over $F_p$​. This group supports:

• Addition of points,

• Scalar multiplication (repeated addition),

• And the ability to find inverses (with respect to the group operation).

These operations form the basis of elliptic curve cryptography. In the next part of this series, we'll explore exactly how these operations work and how they lead to hard problems that form the backbone of ECC, such as the Elliptic Curve Discrete Logarithm Problem (ECDLP).