2

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?

toga
  • 23

1 Answers1

2

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.

Arthur
  • 199,419