Elliptic Curves In a Finite Field

Elliptic curves over finite fields are fundamental mathematical structures with implications in various areas of cryptography and number theory (Washington, L. C., 2008, pp-95-98, Section 4.1).

An elliptic curve can be defined by a cubic equation, in the form:

y^2 = x^3 + Ax + B

where A and B are constant coefficients that ensure the curve is non-singular, meaning it has no cusps or self-intersecting points - nonsingular (Washington, L. C., 2008, p23, Definition 2.4).

When these curves are considered over a finite field - such as the set of integers modulo a prime number p, denoted as:

F_p​

they exhibit algebraic and geometric properties that are crucial for applications such as encryption, digital signatures, and secure communications. The discrete nature of finite fields adds layers of complexity and security, making elliptic curves ideal for cryptographic systems that require both efficient computations and robust security measures. This setting provides the groundwork for exploring advanced mathematical concepts while offering practical benefits for real-world cryptographic applications.

When exploring elliptic curves in a finite field, we generally use the elliptic curve in its Weierstrass form (at least for simplified analysis of the process) (Washington, L. C., 2008, pp-9-11, Section 2.1).

As such we are guaranteed that the point on the elliptic curve will be symmetrical across the x-axis, as explored in this site's article on elliptic curves defined in the field of Real numbers.

The value and importance of that will become clear presently.

Finding Points on a Curve in a Finite Field

What we are trying to find is:

Values for y^2 (mod p) that are equal to one of the values of the cubic x^3 + Ax + B (mod p), where both x and y are integers, and A and B are constants. Only the values generated by:

0 <= x, y < p (where x, y are integers)

need be considered, due to the properties of finite fields, and the repeating groups created within them. These symmetries will also be explored visually, below.

Visualising These Solutions

NOTE: with all the animations below, please consider using the "full screen" option (the icon, like the one to the left, that looks like the corners of a square, above the progress bar, at the bottom, on the right-hand side). It will assist in being able to see the available details in the animation.

Below is an animation that explores (by cycling through different values for p), the solutions to y^2 = x^3 + x + 1 (mod p):

OF NOTE:

1. BLUE: The equation for the elliptic curve is written in blue text, in the top left of the graph. The graph of this curve, when defined in the field of Real numbers is indicated on the graph in faint blue dots.

2. RED: The maximum and minimum values for x and y being used for these calculations is indicated by red dashed lines on the graph. The specific Prime Modulus being used to generate these results is indicated in red text, just outside the box creates by the red range lines. It changes over time, and steps up through the first 25 prime numbers, slowly.

3. GREEN: Due to the symmetrical nature of an elliptic curve in the Weierstrass form, the values for x at y = Y is the same as the value for x at y = -Y (where Y is a value in the field in which E, the elliptic curve, is defined). That is: (x, y) = (x, -y) for all x, y in F. As such, there is a symmetry to the solutions between 0 and p-1. The line of reflection, for this symmetry is shown by a green dotted line, and specified in green text.

   1. All prime numbers, except 2, are odd. As such, the line of symmetry never has any value directly on it (as it does not sit at an integer point) except in the case of p = 2. The one exception to this symmetry is when y = 0, at which point there is only one value, not its reflection (which would be at p-0 = p). This can be understood in 2 ways. In an infinite field, for and elliptic curve in the Weierstrass form, y = 0, is the point of intersection with the x-axis, and therefore there is no reflection across the x-axis, just one value for x. In a finite field, we consider y = 0 as being part of the field, but not y = p - as 0 <= x, y < p (where x, y are integers).

4. Also, due to the aforementioned symmetry and the fact that 1 is a square number, there will ALWAYS be a solution to the equation y^2 = x^3 + x + 1, when x = 0 and y = 1 (because x^3 + x + 1 = 1, when x = 0). Therefore, the solution is there, throughout the animation, along with its "partner", at x = 0 and y = p - 1.

   1. In fact, if B is a square number, for any elliptic curve in the Weierstrass form, there will be a persistent (i.e. always present) solution to that equation, at x = 0 and y = sqrt{B}.

Making alterations

One question that might arise is: what happens if we keep the prime modulus the same but alter the underlying elliptic curve?

To this end, the following 3 animations do just this.

First, while keeping p = 97 and B = 0, we cycle through 11 values for A, starting with simply y^2 = x^3.

NOTE: the full equation for the elliptic curve, at any time (both drawn and written out), can still be seen in BLUE. However, at this resolution the graph of the real solutions to the elliptic curve does not move much.

Now, while keeping p = 97 and A = 0, we cycle through 11 values for B, starting with y^2 = x^3 again.

The real solutions to the elliptic curve change a little bit more obviously, close to the origin, under this translation.

Now, while still keeping p = 97, we cycle through a wider set of values (-10 to 10) for both A and B at the same time, starting with y^2 = x^3 again. This is included, to give a wider view of just how varied the solutions to these equations are, from small, stepwise changes, and to give an indication (visually, at least) that those changes appear to be unpredictable, and not obvious in nature.

Taking a closer look

While the given above is useful for visualising how points in the graph are solutions to the equation, as p increases - let's now take a closer, a more "zoomed-in" view, to look at some lower values of p. This helps to resolve more detail and see what is happening, at a basic level, more clearly.

Specifically, let's look at the solutions listed in Washington, L. C., 2008, p. 95, Example 4.1, for:

y^2 = x^3 + x + 1 (mod 5)

(0, 1), (0, 4), (2, 1), (2, 4), (3, 1), (3, 4), (4, 2), (4, 3)

As seen here:

And, the solutions listed in Washington, L. C., 2008, p. 96, Example 4.2, for:

y^2 = x^3 + 2 (mod 7)

(0, 3), (0, 4), (3, 1), (3, 6), (5, 1), (5, 6), (6, 1), (6, 6)

As seen here:

To show the solutions listed in Washington, L. C., 2008, p. 96, Example 4.2, for:

y^2 + xy = x^3 + 1 (mod 2)

(0, 1), (1, 0), (1, 1)

We need to add some coefficients to the equation. To makes it clear we will switch to a_x notation, as commonly used for the more general form of the elliptic curve equation.

...

TODO: finish this page...