9
$\begingroup$

In an introductory text, I found that point addition for elliptic curves can be made plausible as follows:

Given two Points, P, Q, the sum is defined as the point on the curve I get by connecting P with Q with a straight line. This line intersects the curve on a third point. After reflecting y I get the sum P+Q.

However, taking the points R and Q on the attached figure $y^2=x^3-\frac{29}{10}x +1$, where is the third point?

Should it be the point at infinity? That cannot be from my point of view, because $P+Q=\infty$ would imply $P = -Q$ which is not the case.

See also:

http://demonstrations.wolfram.com/AdditionOfPointsOnAnEllipticCurveOverTheReals/ The Snapshot 1 is the curve I talk about. The following is stated below:

For two points P and Q on an elliptic curve, the addition is defined as follows. Draw the line through P and Q to intersect the curve in a third point; then reflect that point in the axis.

Point Addition on ellipic curves

$\endgroup$

closed as off-topic by cygnusv, fkraiem, otus, e-sushi Nov 23 '16 at 14:00

  • This question does not appear to be about cryptography within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ I'm voting to close this question as off-topic because it belongs to Math.SE $\endgroup$ – cygnusv Nov 21 '16 at 9:21
  • $\begingroup$ It is also unclear; what are the equation of the curve and the coordinates of the points? $\endgroup$ – fkraiem Nov 21 '16 at 9:27
  • $\begingroup$ I added the equation and a linkto wolfram, where point addition is explained. $\endgroup$ – michael Nov 21 '16 at 9:41
  • $\begingroup$ Math are the foundations of cryptography. Elliptic curve arithmetics are especially relevant. This may also belong to Math.SE, but definitely has its place here. $\endgroup$ – Flavien Nov 21 '16 at 14:25
  • $\begingroup$ In your drawing, you have a tangent at $P$, and in that construction this would actually represent $P + P = R$. Not sure what that has to do with $R+Q$ at all. $\endgroup$ – tylo Nov 21 '16 at 15:37
12
$\begingroup$

I think this is on-topic for cryptography, as this is a basic elliptic-curve related question that anyone interested in ECC will come across. Moreover, it is easily answered.

Although on the picture it seems that there is no third intersection point in the plane, there is one. Note that not the whole curve can be fit into this picture, since at some point we cut off the rest of the $x$ and $y$-axis. What remains unknown is what happens when $x$ becomes larger. Well, what happens is that slope of $E$ keeps increasing (resp. decreasing), going towards infinity (resp negative infinity). You can see this by considering the function $y(x)=\sqrt{x^3-\frac{29}{10}x+1}$, and always taking the positive (resp. negative) root. The derivative will go to infinity (resp. negative infinity) as $x$ goes to infinity.

Therefore if you want to continue the drawing of this curve, you have to extend the rightmost part by making it more and more vertical. If you also extend your line, you will see that they will intersect.

$\endgroup$
  • $\begingroup$ oh...so easy! By looking at the graph I thought that the curves are downward-concave for large x. Of course this is wrong... $\endgroup$ – michael Nov 21 '16 at 13:51
  • $\begingroup$ I think you must mean more and more vertical. $\endgroup$ – TonyK Nov 21 '16 at 17:12
  • $\begingroup$ Looking at the top part of the graph only - if the line becomes more and more vertical then its slope increases; since its slope inside the picture is clearly greater than the slope of the line PQ, how can it not continue diverging from PQ while becoming "more and more vertical"? $\endgroup$ – immibis Nov 22 '16 at 9:34
  • 2
    $\begingroup$ The picture is a bit confusing. The question is about the line $QR$, where $Q$ is the green dot and $R=(x_3,y_3)$. This intersects $E$ in $Q$, $R$ and some point on $E$ which has negative $y$-coordinate (and nowhere else). The line going through $P$ does not intersect $E$ in any other point than shown on the picture. This is a so-called tangent line at $P$. We think of it as intersecting twice at $P$, and once at the other point we see in the picture (and nowhere else) $\endgroup$ – CurveEnthusiast Nov 22 '16 at 10:41
  • $\begingroup$ @immibis: look at the bottom part of the graph instead. $\endgroup$ – TonyK Nov 22 '16 at 17:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.