On an elliptic curve over a finite field, why does the line(s) connecting two points also cross the third point with suitable integer coordinates?

64 Views Asked by At

It's true by the field's definition, that the points could add up to get to a third point with the corresponding coordinates. But how do you prove it?

For example, in the example of y^2 = x^3 -7x+10 (mod 19), (graph at https://andrea.corbellini.name/2015/05/23/elliptic-curve-cryptography-finite-fields-and-discrete-logarithms/) (2, 2) is on the graph. How do you prove that (2,2), added by any other point on that graph, like (3,4), would also land on a point with corresponding integer coordinates within the field?

1

There are 1 best solutions below

1
On BEST ANSWER

Let's first assume that the two points have distinct $x$-coordinates. That means that the line that goes through those points can be written as $y=mx+c$. Insert this into the equation for the curve. You get a cubic in $x$. You know two roots of this cubic (the $x$-coordinates of the two points).

The third root is given by Vieta's formulas, and in particular it necessarily exists in the integers modulo 19. Once you have the $x$-value, the $y$-value is given by $mx+c$ from before.

If the two given points have the same $x$-value, then you have a vertical line, which intersects the curve at infinity (which is to say $0$).

Using the two points $(2,2)$ and $(3,4)$, we get $y=2x-2$. Inserting that into $y^2=x^3-7x+10$ yields $$ (2x-2)^2=x^3-7x+10\\ 0=x^3-4x^2+x+6 $$ By Vieta's formula, the sum of the three roots is $4$. We already have $2$ and $3$, so the final one must be $-1\equiv_{19} 18$. The $y$-value is $2(-1)-2=-4\equiv_{19}15$. And indeed, we see from the graph in your link that $(18,15)$ is on the curve.