As I explained in an earlier post, a first pass at the definition of an elliptic curve is the set of points satisfyingy² = 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 coordinatesYou 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 .
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 isy²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).
Programming hackFrom 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 spaceThis 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 toolsIt’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 exampleLet’s get concrete.
We’ll look at the curvey² = x³ + x + 1over 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).
By the way, there are 27 points in the projective space our curve lives in.
These are (x : y : 1) for all values of x and y, and the two “infinite” points (0 : 1 : 0) and (1 : 0 : 0).
Note that for all non-zero a, (a : 0 : 0) = (1 : 0 : 0) and (0 : a : 0) = (0 : 1 : 0) since non-zero multiples are in the same equivalence class.
This may make it seem like projective space is asymmetric, that the third coordinate is special.
But it’s only our description that’s asymmetric.
We could describe the same set of points as (1: y : z), (0 : 1: 0), and (0 : 0 : 1), or for that matter (x : 1 : z), (1 : 0 : 0), and (0 : 0 : 1).
Related postsWhat is an elliptic curve?Naming elliptic curves used in cryptographyAddition on Curve1174 We leave out (0, 0, 0).
It doesn’t exist in the world we’re constructing, i.