Cybernetica

Menu

Elliptic Curve Cryptography - Elliptic Curves (Part 1)

In this post, the focus is on elliptic curves. We’ll talk about commutative groups, operations on the points of an elliptic curve, intersection and tangent methods, neutral and opposite elements, and much more.

A major part of the history of mathematics, including elliptic curves, dates back to Ancient Greece, where Apollonios studied conic sections and wrote an 8-part monograph about them. During the next two thousand years, that monograph contained most of the knowledge of mankind in this field. But some questions remained, that even Apollonios could not answer. One of those was the problem of the exact length of the arc of an ellipse. The mathematical methods for solving this problem were not developed until the 17th to 19th century.

During that process, the study of polynomial equations of the form

(1)

where p is a cubic polynomial, was reached. Through lots of terminological hassle, the curves defined in formula (1) started to be called elliptic curves. The most confusing thing is that the ellipse itself is not an elliptic curve. Writing down all these historical twists would lead us way off track, but if you are in to it, I suggest a comprehensive article by Rice and Brown1.

As is the case with many other powerful mathematical tools, elliptic curves emerge on several independent occasions. Often, they can be seen in solving Diophantine equations, which, yet again, takes us back to Ancient Greece2.

Let’s take a brief look at the task of so called congruent numbers problem (the interested reader can find a more elaborate treatment in the article by Keith Conrad3).

Definition 1 A positive integer n is called congruent if we can find a right-angled triangle with rational number side lengths and having an area equal to n.

Looking at a Pythagorean triangle with side lengths 3, 4, and 5, we can see that 6 is a congruent number, but so are 5 (thanks to a triangle with side lengths 20/3, 3/2, and 41/6) and 7 (thanks to a triangle with side lengths 35/12, 24/5, and 337/60). On the other hand, it is possible to prove, that, for example, number 1 is not congruent4.

So, we are looking for rational solutions a, b, and c for the system of equations

(2)

where n is a fixed integer, which congruence we want to determine. The equations of system (2) can be interpreted in three-dimensional space as equations of surfaces, intersecting along a curve on which we are looking for points with rational coordinates. With an appropriate change of the variable, we can convert the equation of that curve to y2 = x3 - n2x. More precisely, the following theorem applies

Theorem 1 In case of a positive integer n, the following sets are in one-to-one correspondence

.

The correspondence can be given using the following maps:

The claim of this Theorem can be verified by elementary replacement of variables, and is left as an excercise to the reader.

How to come up with an idea that we are looking for a curve with an equation of the form y2 = x3 – n2x? There is reasoning behind that, so let’s take a look at the following conversions using system (2):

We can see, that rational squares

form an arithmetic sequence with a differene n. As x = (c/2)2, their product (x – n) x (x + n) = x3 – n2x must also be a square of some rational number y.

Note that the correspondence in Theorem 1 will maintain the rationality of the solutions. Therefore, it is enough to search for rational points on elliptic curves with the equation y2 = x3 – n2x, to find triangles that provide congruent numbers. It turns out that this kind of a curve has something really special about it – it enables forming of a third triangle from the two already known right-angled triangles with the same area.

We’ll take a closer look at it and continue this topic in our next post. Stay tuned!

Written by Jan Willemson

1 Adrian Rice and Ezra Brown. Why ellipses are not elliptic curves. Mathematics Magazine, 85(3):163–176, 2012. https://www.maa.org/sites/default/files/pdf/upload_library/2/Rice-2013.pdf.
2 Although, Diophantos did not have the necessary mathematical apparatus nor terminology for his reserach, in his masterpiece „Arithmetica“ he describes several solutions, which have, in later research, been acknowledged as the method of elliptic curves. More information can be found in a spectacular book by Isabella Bashmnakova (Isabella Grigoryevna Bashmakova. Diophantus and Diophantine equations. American Mathematical Society, 1997.).
3, 4 Keith Conrad. The congruent number problem. The Harvard College Mathematics Review, 2:58–74, 2008. https://kconrad.math.uconn.edu/blurbs/ugradnumthy/congnumber.pdf.