Intersecting Elliptic Curves with Lines

We want to do some function similar to multiplication of numbers, but using an elliptic curve. We claim that points of an elliptic curve is a good substitute for the “numbers”. The idea is to draw straight lines on top of the curve.

Formulation

Suppose we have an elliptic curve

$y^2 = x^3 + a x + b$

similar to the one below:

standard2

Now we draw a straight line on it to find its intersection. How many points are we going to find?

There seems to be many different cases. For vertical lines on the left side of the curve, there will be no intersection at all. If we move towards the elliptic curve, we eventually see one or two intersections. If we instead rotate clockwise the vertical line with no intersection, we immediately get one intersection somewhere with very large $y$ (because the square root of the cubic function is still a curve of 1.5-th power in $x$ , which grows faster than any straight line that is not vertical).

Then we continue to turn it, and it eventually hit the close component (the somewhat circular part of the curve) and get a second intersection. Continuing to rotate the line, we get 3 intersections.

There can never be more than 3 intersections, because we can easily eliminate $y$ in the simultaneous equations of the cubic curve and the straight line. It gives a cubic equation, so we have at most 3 $x$ ‘s which satisfies the simultaneous equations. Putting it back to the straight line, each gives a single $y$ .

But that is still too many cases. We can instead say that the curve and the line meet at either 1 or 3 points, using the following two tricks:

We count multiplicity. A tangent counts as 2 intersections, and a point of inflection counts as 3.
We consider the limiting case, a point infinitely far in the $y$ direction, to be a point on the curve. To take care of this, we consider an “infinite point at a direction” as a point, and the standard curve contains the “vertical direction”.

The second trick looks very funny, but it is in fact very well-formed. It is called projective geometry: we can extend the coordinate system containing $(x, y)$ pairs by adding a $z$ component, our usual interpretation would put $z = 1$ . Then we “homogenize” the equations, by multiplying a power of $z$ to make all terms to be the same total degree. E.g., the above curve becomes $y^2z = x^3 - xz^2 + 0.2z^3$ , so that all terms have total degree 3. Two points are considered the same point if they have the same ratios (i.e., $(x, y, z) = (ax, ay, az)$ ). With this, the “infinite point of the vertical direction” is simply $(0, 1, 0)$ , and can easily be verified to be on the curve above.

But below we will continue to use the somewhat sloppy language of “point of infinity in the vertical direction”, or in brief “the point of infinity”. It is just one point that we have to use this treatment, which does not warrant complicating all our formulas.

The third intersection: explicit formula

So we have either 1 intersection or 3. If we are given 2 points on the curve and draw a line between them, there are already 2 intersections, so there must be a third. Early mathematicians found that if the original two points have rational x and y coordinates, and the curve has rational coefficients, the third intersection must also have rational coordinates. Let’s make it explicit, by calculating where is the third point. The resulting formula will be very useful to us soon.

Suppose $(x_1, y_1)$ and $(x_2, y_2)$ are points on the elliptic curve:

$E:\quad y^2 = x^3 + ax + b$ .

There are a few cases to consider. First, $x_1$ and $x_2$ may be points opposite to each other. In such case the third intersection is the point of infinity.

Then, we consider the case where $x_1$ is different from $x_2$ . We want to find the third intersection $(x_3, y_3)$ . In such case, we can calculate the slope $s = (y_2 - y_1) / (x_2 - x_1)$ . The line defined by the two points is thus:

$L:\quad y - y_1 = s(x - x_1)$ .

To solve it with the curve $E$ , we move $y_1$ to the right, and substitute the resulting formula of $y$ into $E$ .

$(s(x-x_1)+y_1)^2 = x^3 + ax + b$ .

This equation should have 3 roots. Since $x_1$ and $x_2$ are points on both $E$ and $L$ , two of them should be $x_1$ and $x_2$ . The equation should thus be the same as $(x-x_1)(x-x_2)(x-x_3) = 0$ . To find $x_3$ , all we need is to make the coefficient of $x^3$ to be 1. Then the $x^2$ coefficient would be $-x_1 - x_2 - x_3$ . In the above formula, we simply move everything to the right, and notice that the $x^2$ coefficient is $-s^2$ . This gives us $x_3$ :

$x_3 = s^2 - x_1 - x_2$ .

Putting it back to the equation of $y$ we get $y_3$ as well.

$y_3 = s(x_3 - x_1) + y_1$ .

What if $(x_1, y_1)$ and $(x_2, y_2)$ are the same point? Our rule of multiplicity says that in such case, the line should be a tangent at $(x_1, y_1)$ . The formula for $x_3$ and $y_3$ above still works, except that we need to use the slope of this tangent as $s$ . To find the slope, we differentiate $E$ with respect to $x$ :

$\displaystyle \frac{2y\,dy}{dx} = 3x^2 + a$ .

So the formula for $s$ is thus:

$\displaystyle s = \frac{dy}{dx} = \frac{3x_1^2 + a}{2y_1}$ .

Now it should be clear why we always find rational third intersection if $x_1$ , $x_2$ , $y_1$ , $y_2$ , $a$ and $b$ are all rational. (We can argue about it without the explicit formula, but having it perhaps makes it clearer.)

But we still have some corner cases which must also be catered for. In particular, one or both of the original points may be the point of infinity. Our rule says that the point of infinity means the vertical direction. In our standard form, if we have one of the point being the point of infinity, the other point simply have $y$ mirrored about the $x$ axis. So the third intersection of the line through the point of infinity and $(x_1, y_1)$ would be $(x_1, -y_1)$ . If both points are the point of infinity, the third point is also the point of infinity.