1

Can it so happen that "adding" two points of Elliptic Curve (over finite field) never "hits" any third point of that curve? For example Y^2 = X^3 - 6*X + 7 over GF19 looks like this, (unless there is mistake):

Elliptic curve example over GF19

Taking two leftmost points P = (0, 11) and Q = (3, 15) it seems the tangent gradient is k = (15 - 11) * inv(3 - 0) where inv(3) seems to be 13, and thus k = 4 * 13 = 14. The "line" between these points is Y = 14 * X + 11, right?

Seemingly it never got to any other of the marked points except these two. Or perhaps I'm doing something wrong, or coefficients A, B, P should be chosen with some special rule to make points addition "more lucky"?

Rodion Gorkovenko
  • 161
  • 3
    By plugging in $y=14x+11$ into $y^2=x^3-6x+7$ you get the cubic equation $$p(x)=x^3+13x^2+9x\equiv x(x^2-6x+9)=0.$$ Hence the polynomial $p(x)$ factors over $GF(19)$ as $$p(x)=x(x-3)^2.$$ So the third point is $x=3$ as three is a double root. In other words, the line $y=14x+11$ is the tangent of the elliptic curve at $Q$. – Jyrki Lahtonen May 09 '23 at 06:37
  • 2
    For the purposes of elliptic curve addition this means that $P+Q+Q=0$. In other words $P+Q=-Q=(3,4)$. You might have figured out this right away, if you had applied the point doubling formula to $Q$. You would the similarly calculate that $[2]Q=-P=(0,8)$. – Jyrki Lahtonen May 09 '23 at 06:38
  • 3
    I'm fairly sure we have covered similar examples on the site earlier. Therefore I'm reluctant to post this as an answer. Anyway, I have upvoted your question, for it has good context, and you explained the situation very well. I (or someone else) will promote the comment to an answer, if we cannot find a good duplicate target. – Jyrki Lahtonen May 09 '23 at 06:39
  • 2
    For example here we similarly see from prof. Lubin's answer how a double root arises in case of a tangent. – Jyrki Lahtonen May 09 '23 at 06:48
  • 1
    A similar situation is described here. Though there the situation is even more special as the line happens to be horizontal. But for the purposes of elliptic curve arithmetic slope zero is not really a special case. – Jyrki Lahtonen May 09 '23 at 06:51
  • 3
    And here. None of these questions is similar enough to call this a duplicate, but there are more to be checked out. – Jyrki Lahtonen May 09 '23 at 06:57
  • 1
    One more. – Jyrki Lahtonen May 09 '23 at 07:12
  • @JyrkiLahtonen thanks a lot for details and examples! not sure if converting these ideas to proper answer will really harm :) I'm sure I googled a bit before asking and there were no close search results (perhaps no close keyword set) so your explanations could be pretty useful for others. – Rodion Gorkovenko May 09 '23 at 07:28
  • You can convert them to an answer if you like, since @JyrkiLahtonen hasn't done so and has indicated he's not likely to do so. – kodlu May 11 '23 at 14:31

0 Answers0