As I explained in an earlier post, a first pass at the definition of an elliptic curve is the set of points satisfying
y² = x³ + 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²z = x³ + axz² + bz³.
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).
NB: A finite projective plane has multiple points at infinity, but only one is on our curve.
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 “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² = x³ + x + 1
over the integers mod 5. There are nine points on this curve: (0, ±1), (2, ±1), (3, ±1), (4, ±2), and ∞. (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
[1] We leave out (0, 0, 0). It doesn’t exist in the world we’re constructing, i.e. projective space.
Aren’t there typically many projective points at infinity, one of which is on an elliptic curve? I.e. (a:b:0) where not both a and b are zero.
Yes, there are multiple points at infinity in the projective space, but only one on the elliptic curve.