The point at infinity

As I explained in an earlier post, a first pass at the definition of an elliptic curve is the set of points satisfying

y^2 = x^3 + ax + b.

There are a few things missing from this definition, as indicated before, one being the mysterious "point at infinity." I gave a hand-waving explanation that you could get rid of this exceptional point by adding an additional coordinate. Here I'll describe that in more detail.

Projective coordinates

You could add another coordinate z that's a sort of silent partner to x and y most of the time. Instead of pairs of points (x, y), we consider equivalence classes of points (x, y, z) where two points are equivalent if each is a non-zero multiple of the other [1]. It's conventional to use the notation (x : y : z) to denote the equivalence class of (x, y, z).

In this construction, the equation of an elliptic curve is

y^2z = x^3 + axz^2 + bz^3.

Since triples are in the same equivalence class if each is a multiple of the other, we can usually set z equal to 1 and identify the pair (x, y) with (x : y : 1). The "point at infinity" corresponds to the equivalence class (0 : 1 : 0).

Programming hack

From a programming perspective, you could think of z as a finiteness flag, a bit that is set to indicate that the other two coordinates can be taken at face value.

Projective space

This three-coordinate version is called projective coordinates. Textbooks usually start out by defining projective space and then say that an elliptic curve is a set of points in this space. But if you're focused on the elliptic curve itself, you can often avoid thinking of the projective space it sits in.

One way to think of projective space is that we add a dimension, the extra coordinate, then subtract a dimension by taking equivalence classes. By doing so we almost end up back where we started, but not quite. We have a slightly larger space that includes a couple "points at infinity," one of which will be on our curve.

Alternating tools

It's inconvenient to carry around an extra coordinate that mostly does nothing. But it's also inconvenient to have a mysterious extra point. So which is better? Much of the time you can ignore both the point at infinity and the extra coordinate. When you can't, you have a choice which way you'd rather think of things. The point at infinity may be easier to think about conceptually, and projective coordinates may be better for doing proofs.

Concrete example

Let's get concrete. We'll look at the curve

y^2 = x^3 + x + 1

over the integers mod 5. There are nine points on this curve: (0, 1), (2, 1), (3, 1), (4, 2), and a. (You could replace -1 with 4 and -2 with 3 if you'd like since we're working mod 5.)

In the three-coordinate version, the points are (0 : 1 : 1), (2 : 1 : 1), (3 : 1 : 1), (4 : 2 : 1), and (0 : 1 : 0).

Related posts

• What is an elliptic curve?
• Naming elliptic curves used in cryptography
• Addition on Curve1174

[1] We leave out (0, 0, 0). It doesn't exist in the world we're constructing, i.e. projective space.