Robert's Mistakes

# Elliptic curves

Feb 13, 2014

...are best known for their applications in cryptography. They are also the beginning of a long story about uncovering a landscape of highly -complicated- interesting structures. First appearance goes back to Diophantus of Alexandria, who lived some time in the AD 200's. There's a simple geometrical approach to get at them, but first, let's look at what a short answer usually looks like:

The following algebraic equation is the most important way to get an elliptic curve:

$y^2 = x^3 + A*x + B$

What is its meaning? You can also look at pictures like, for example, the second one below, also from wikipedia. They further have a rather general definition to offer:

an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point $O$.

http://en.wikipedia.org/wiki/Elliptic_curve

Huh? Let's ask Mathworld. It gives two definitions, here's the "formal" one:

an elliptic curve over a field is a nonsingular cubic curve in two variables, with a rational point

And here's the "informal" one:

an elliptic curve is a type of cubic curve whose solutions are confined to a region of space that is topologically equivalent to a torus.

http://mathworld.wolfram.com/EllipticCurve.html

Are these even about the same object? What are they, really? Keep on reading!

An Elliptic curve $E$ has the property that most lines meet it in exactly three points. Some don't, but we can fix this: First, classify those problematic lines into finitely many types. The tribe says, we should then extend our number space by exactly that many points. In our example, we add one artificial point at infinity. So, in the end, we get a gadget where every line intersects a curve in exactly three points.

Why is three points interesting? Because that gives us a group! Given two points, we can "add" those and get a third one. We may conveniently write an equation relating all points on a line to zero:

$a + b + c = 0 \textrm{ whenever a, b, c lie on a line}$

Let's go hunting for new points using just $a$ and $b$! Based on the above, it seems natural to label our first new point with a formal sum and an extra minus sign to keep the balance. Looks just like before, doesn't it!?:

$a + b -(a+b) = 0$

Easy enough. But there are degenerate cases! This one means, if a line is tangent, say in $b$, we double count $b$:

$a + b + b = 0$

When adding points exactly above one another, we have to throw in our "zero" point at infinity. Yes, nomenclature sucks and folks really do write zero for infinity in this case.

$a + b + 0 = 0$

And so on. This group is associative.

The animation shows a fixed elliptic curve (including a fixed point $O$). Given three further points $a, b$ and $c$ on the curve we can construct the remaining points. Observe that the central point lies on the line from $a$ to $-(b+c)$ as well as on the line from $-(a+b)$ to $c$.

It is also commutative, and with associativity that makes it an abelian group. So it's pretty close to what we can do with numbers.

Note, that there's a bug in the animation. It is cropped short on the left side. The sign of the point -(a+b) is not supposed to change! Also note, that the points $a, b, c$ are the ones that get moved.

The points on a line form the dihedral group $D_3$, the symmetry of a triangle! Adding $b$ to $a$ gives us $c$. And adding $c$ to $a$ gives us $b$ again. In such a triangular miniverse, a point is its own negative!

What a peculiar group!

Let's once again widen our perspective and remember that parameter $K$, which is supposed to be a field, a numberlike space. Until here, we assumed that $K$ is the real numbers object $\R$. But you can plug in any other field into the formula. Most are interested in elliptic curves over the finite fields $F_n$ (it's what the cryptologists do) and field extensions over the rationals $\Q$. But one can define them over the complex numbers $\C$, too!

In case you wonder, i wrote a bit about field extensions here:

An elliptic curve has a Legendre normal form if the field $K$ has characteristic other than 2 or 3. The number fields $\Q$, $\R$ and $\C$ have characteristic $0$, so they all have a unit $1$:

$y^2 = x * (x-1) * (x-λ)$

That's a cubic curve intersecting the x axis in $0$, $1$ and $λ$. We don't really need two parameters $A$, $B$ in these cases. One is enough!

Of course, all of the intuition I talked above can be expressed in precise formulas. For example, to compute $-(a+b)$ based on $a$ and $b$. But these formulas need to handle the point at infinity and the tangent lines as special cases and the result looks a bit patchy. But there's another and in that respect better representation :

Edwards curve is a coordinate system for some elliptic curves. Using it, we can often get away with a single formula.

http://en.wikipedia.org/wiki/Edwards_curve

Another, earlier representation, on a torus, can be related with the complex, periodic Weierstrass ℘-function. That's a fancy P, isn't it? And look at the first image, it gives nice pictures too!

http://en.wikipedia.org/wiki/Weierstrass's_elliptic_functions

This mathoverflow question asked for the history of elliptic curves and provoked some interesting links to expository papers.

http://math.stackexchange.com/questions/156650/history-of-elliptic-curves