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


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, i.e. lines such as \(Y = m X + b\). It is very easy to find all the solutions of such an equation (over any given 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 understood well. 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: this is the case just before things begin to get really hard, yet is simple enough to yield a rich area of mathematics. The term "elliptic curves" refers to the study of these equations, usually about the structure of the set of all solutions to a given equation over a particular field. We write \(E(K)\) to mean the solutions of the equation \(E\) over the field \(K\).

The theory splits into two branches depending on whether finite or infinite fields are considered. We shall take the finite fields path, as that is where the cryptography applications lie, though some of the material here is applicable to both situations.

We briefly state a couple of results from the other path:

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\).

Ben Lynn blynn@cs.stanford.edu 💡