Elliptic Curves

Most of the material is from lectures given by John Cannon back in 1999.

  • Ian Blake, Gadiel Seroussi and Nigel Smart, "Elliptic Curves in Cryptography", Cambridge University Press

  • Neal Koblitz, "Algebraic Aspects of Cryptography", Springer

  • Joseph Silverman, "The Arithmetic of Elliptic Curves", Springer

Overview

The term elliptic curves refers to the study of solutions of equations of a certain form. The connection to ellipses is tenuous. (Like many other parts of mathematics, the name given to this field of study is an artifact of history.)

In the beginning, there were linear equations, \(a X + b Y = c\), which are easy to solve over any field.

Conics, which are given by equations where each term has combined degree at most two, such as \(X^2 + 2X Y + 4Y^2 = 3\), are more complex, but are still well-understood. In fact, it can be shown that in the real projective plane, every conic can be affinely transformed into one of the following five curves:

  1. \(X^2 = 0\) : a double line

  2. \(X^2 + Y^2 = 0\) : a single point

  3. \(X^2 - Y^2 = 0\) : two lines

  4. \(X^2 + Y^2 + Z^2 = 0\) : the empty set

  5. \(X^2 + Y^2 - Z^2 = 0\) : a unit circle

Cubic equations (where each term has combined degree at most three) such as \(Y^2 + X Y = X^3 + 1\) are where things are most interesting: increase the degree and things get really hard; decrease the degree and the results are trivial. The term "elliptic curves" refers to the study of these equations. We write \(E(K)\) to mean the solutions of the equation \(E\) over the field \(K\).

Pythagoreas

We wish to find all Pythagorean triples, that is, the integer solutions to \(x^2 + y^2 = z^2\).

Dividing by \(z^2\) shows this is the same as finding all rational solutions to \(X^2 + Y^2 = 1\), the unit circle.

One solution is \((-1, 0)\). Suppose \((X, Y)\) is another rational point on the curve and consider the line from \((-1, 0)\) to \((X, Y)\). Its slope:

\[ t = \frac{Y}{X+1} \]

must also be rational.

Conversely, for any rational \(t\), using algebra, the line \(Y = t(X + 1)\) and the curve \(X^2 + Y^2 = 1\) intersect at \((-1, 0)\) and:

\[ \left(\frac{1-t^2}{1+t^2}, \frac{2t}{1+t^2}\right) \]

Write \(t = m/n\) for integers \(m, n\), and we can say the Pythagorean triples are precisely:

\[ \{ n^2 - m^2, 2 n m , n^2 + m^2 | m, n \in \mathbb{Z} \} \]

To recap, we drew lines through a point on the curve and found where they intersected the curve again.

An elliptic curve

We wish to find the rational solutions to \(Y^2 = X^3 - 2X\).

Suppose we knew a solution \((X_0, Y_0)\) with \(Y_0 \ne 0\). By implicit differentiation, the tangent line at a point \((X_0, Y_0)\) is given by:

\[ Y = \frac{3 X_0^2 - 2}{2 Y_0} (X - X_0) + Y_0 \]

Where else does this line intersect our curve? Substituting this expression for \(Y\) into the equation defining our curve and using \(Y_0^2 = X_0^3 - 2 X_0\) yields a cubic in \(X\) with constant term:

\[ -\frac{X_0^2(X_0^2 + 2)^2}{4(X_0^3 -2 X_0)} \]

Since \(X_0\) is a root of multiplicity 2 of this equation, the other root must be:

\[ X_1 = -\frac{(X_0^2 + 2)^2}{4(X_0^3 -2 X_0)} \]

which is rational, and \(Y_1\) can be found by substituting \(X_1\) into the equation of the tangent line, so must also be rational.

For example, the tangent line at \((-1,1)\) intersects the curve again at \(\left(\frac{9}{4}, \frac{21}{8}\right)\). The tangent line at this point intersects the curve again at \(\left(\frac{12769}{7056}, \frac{900271}{592704}\right)\). Exercise: prove that iterating this process produces distinct points.

Instead of a tangent line through one known rational point, we can find where the chord through two known rational points intersects the curve again. For example, the chord through \((2, -2)\) and \(\left(\frac{9}{4}, \frac{21}{8}\right)\) intersects the curve at \((338, 6214)\).

To recap, we drew lines through one or two points on the curve and found where they intersected the curve again.

It turns out that for any cubic curve of genus 1, we can construct every rational point by using chords and tangents starting from a fixed set of points. Or more succinctly:

Theorem [Mordell]: On a rational elliptic curve, the group of rational points is a finitely-generated abelian group.

Theorem [Mazur]: Write \(E(\mathbb{Q}) = \mathbb{Z}^{(r)} \times \mathrm{Tor}(E(\mathbb{Q}))\). Then either

\[ \mathrm{Tor} (E(\mathbb{Q})) \cong \mathbb{Z} / m\mathbb{Z} \]

where \(m = 1, 2, ..., 10, 12\), or

\[ \mathrm{Tor} (E(\mathbb{Q})) \cong \mathbb{Z} / m\mathbb{Z} \times \mathbb{Z} / 2\mathbb{Z} \]

where \(m = 2,4,6,8\).

Elliptic curves over finite fields

The theory splits into two branches depending on whether \(K\) contains the rationals. The above results come from the \(\mathbb{Q} \subseteq K\) path.

From now, we focus on finite fields, as that is where the cryptography applications lie, though some of our material is applicable to both.


Ben Lynn blynn@cs.stanford.edu 💡