Elliptic curves: point at infinity

Setting aside the reasoning why we are building an algebraic system using points of elliptic curves (we will get into that later on), we omitted some bad things that can happen when applying the rules for point addition and doubling. We did this on purpose as it would be too confusing for some readers. But now the time has come and we can look at these problematic cases to find something new: the point at infinity.

When trying to sum two points of the elliptic curve in simple Weierstrass form[1] which are respective negatives, the straight line crossing the two does not intersect the elliptic curve in any other point - as can be seen in Picture 1. Also it means that the slope of the line cannot be calculated as it would require us to divide by zero, because $P_x=Q_x$: $d=\frac{Q_y-P_y}{0}$

Picture 1: adding points $P\approx[1.48,2.46]$ and $Q=-P\approx[1.48,-2.46]$ on elliptic curve $y^2=x^3-2x+2$ over $\mathbb{R}$. When doubling a point, similar problem arises at $P_y=0$: $d=\frac{3x^2+a}{0}$

Picture 2: doubling the point $P\approx[-2.27,0]$ on elliptic curve $y^2=x^3-2x+2$ over $\mathbb{R}$. In both of these cases we say that the resulting point lies at infinity and we typically label it $O$. This name was not chosen ad libitum; it comes from the fact that if you do not work on euclidean plane but you warp the space in a way that all points at infinity collapse into one, the line would actually cross the curve at this point[2]. And for all practical purposes - when working with elliptic curves (in simple Weierstrass form at least) we also put a rule for given elliptic curve $E$ such that: $\forall P\in E:\quad P+O=P$ With this simple rule, our set of points on the elliptic curve becomes an algebraic closure - that is, all operations on points in this set (including the point at infinity) produce results from the very same set of points. This is very important feature, which we will use later to actually do some cryptography with these points.

When working with rational points of the elliptic curve over given finite field, the situation is similar. When performing addition, we can easily see that trying to sum two points which are negative to each other, the straight line crosses only these two points and therefore the result of adding these together is the point at infinity $O$. You can see such situation in Picture 3.

Picture 3: point addition of points $P=[18,5]$ and $Q=[18,18]$ on elliptic curve $y^2=x^3-2x+2$ over $\mathrm{GF}(23)$. And actually when performing the point doubling operation, there are two cases when the doubling operation does not produce any rational point as a result. First is for $P_x=0$ - that is the same as on elliptic curves over $\mathbb{R}$ - but this time we can see that there is some other point the line would cross. The problem is, this point is negative point of the original one. Therefore on $\mathrm{GF}(p)$ the result of such doubling operation is also the point at infinity $O$ as can be seen in Picture 4.

Picture 4: Doubling of point $P=[0,5]$ on elliptic curve $y^2=x^3-2x+2$ over $\mathrm{GF}(23)$. When trying to double a point with $P_y=0$ - the situation is similar as the slope would be infinite and therefore the "tangent" line is equidistant to the Y axis as can be seen in Picture 5. Again, the result of such doubling operation is $O$, our point at infinity.

Picture 5: Doubling of point $P=[9,0]$ on elliptic curve $y^2=x^3-2x+2$ over $\mathrm{GF}(23)$. If you look at the Video 1, you can see all of the above at once and in motion. Especially understanding that over a finite field, the point at infinity $O$ is not lying within a given finite field, is really easy this way.

Video 1: Cases of point addition and doubling which lead to a result at the point at infinity. As you can see in the video, creating an algebraic closure from the set of points of the elliptic curve by introducing the point at infinity is not a rocket science - rather it is pretty easy to grasp. Isn't it?

I am really happy you made it this far, because this is basically the end of the hard part. When creating a discrete-logarithm-based cryptography product, you now "only" build on these foundations and create basic key exchange or digital signature schemes pretty easily. And we will get there eventually. See you next week!

References

1. Wikipedia contributors. (2018, March 24). Weierstrass's elliptic functions. In Wikipedia, The Free Encyclopedia. Retrieved 13:55, March 27, 2018, from https://en.wikipedia.org/w/index.php?title=Weierstrass%27s_elliptic_functions&oldid=832144866

2. Wikipedia contributors. (2017, August 10). Point at infinity. In Wikipedia, The Free Encyclopedia. Retrieved 13:55, March 27, 2018, from https://en.wikipedia.org/w/index.php?title=Point_at_infinity&oldid=794811144