7
$\begingroup$

I am currently struggling with the determination the order of a point on an elliptic curve.
We had to do the following exercise:

$C = V(y^2+x^3-1)$ and $P = (0,1)$. Now Wikipedia told me that I can calculate the sum of two point with the following formulas:

Let $P=(x_P,y_P), Q=(x_Q,y_Q)$. Then $S=P+Q=(X_S,y_S)$
with $x_S=m^2-x_P-x_Q$ and $y_S=-y_P+s(x_P-x_S)$, where $m = \frac{y_P-y_Q}{x_P-x_Q}$.
So then I get $P+P = (0,-1)= -P$ so that $P+P+P=\infty$.

Now my question is, how this formula works. Because it does not depend anyhow on the formula of the elliptic curve right? So for any elliptic curve my point $P=(0,1)$ has the order $3$? This seems very weird to me.

(I also don't see where the formula for the addition of two points comes from.)

I would be very happy if someone could explain me how this works, and if you know good literature about elliptic curves.

Best, Luca

$\endgroup$
5
  • 3
    $\begingroup$ Do you know the geometric interpretation of adding points? I would recommend "Rational points on elliptic curves" from J Silverman and J Tate. $\endgroup$
    – Kaladin
    Mar 8, 2014 at 14:46
  • 3
    $\begingroup$ Read Silverman's "The Arithmetic of Elliptic Curves", III.2 .Excellent book, btw. $\endgroup$
    – DonAntonio
    Mar 8, 2014 at 14:47
  • $\begingroup$ Only what I read at Wikipedia... In class we discussed elliptic curves quite superficially. Thanks for the book recommendations! $\endgroup$
    – Luca
    Mar 8, 2014 at 14:50
  • $\begingroup$ Indeed "The Arithmetic of Elliptic Curves" is an excellent book. $\endgroup$
    – Kaladin
    Mar 8, 2014 at 14:51
  • 2
    $\begingroup$ The dependence on the elliptic curve comes from the fact that $P=(0,1)$ lies on the curve. For all such curves, $3P=\mathcal{O}$. $\endgroup$
    – TonyK
    Mar 8, 2014 at 18:30

1 Answer 1

18
$\begingroup$

Instead of following blindly Wikipedia's formulas, it is best to understand how to calculate $P+Q$, or $P+P$, given an elliptic curve. Let us assume for simplicity that the curve is given by $E:y^2=x^3+Ax+B$, and $P,Q\in E$.

  • In order to find $P+Q$, first find the equation of the line $L$ through $P$ and $Q$, find the third point $R$ of intersection of $L$ and $E$. Then $P+Q+R=\mathcal{O}$, so that $R=-(P+Q)$. In this case $-(x_0,y_0)=(x_0,-y_0)$, so we can find $P+Q$ as $-R$.

  • In order to find $P+P$, first find the tangent line $L$ to $E$ at $P$, and find the third point $R$ of intersection of $L$ and $E$. Then, $2P+R=\mathcal{O}$, and so $2P=-R$.

In your case, $E: y^2=x^3+1$ and $P=(0,1)$. The tangent line is $y=1$, and it turns out that this line has a triple point of intersection with $E$, thus $R=P$. In particular, $2P=-R=-P$, and so $3P=\mathcal{O}$.

Another example with the same curve $E$: let $P=(2,3)$ and $Q=(0,1)$. The line through $P$ and $Q$ is $y=x+1$, and the third point of intersection is $R=(-1,0)$. Since $R=-R$, we obtain $P+Q=(-1,0)$.

Finally, here is a picture of $P=(2,3)$, $2P$, $3P$, $4P$, and $5P$, which shows that $6P=\mathcal{O}$.

enter image description here

$\endgroup$
4
  • 2
    $\begingroup$ Thank you so much! This is just a perfect answer :) It helped me a lot! $\endgroup$
    – Luca
    Mar 9, 2014 at 1:50
  • 3
    $\begingroup$ By the way, since you asked for references on elliptic curves... the books by Silverman, and Silverman and Tate are excellent, so I would start there. But you may also find this one useful amazon.com/Elliptic-Modular-L-functions-Student-Mathematical/dp/… $\endgroup$ Mar 10, 2014 at 1:53
  • $\begingroup$ Ref: Alvaro's answer: Looks like there is a typo;'4P' should be replaced with '-2P' $\endgroup$ Jan 7, 2018 at 23:40
  • 2
    $\begingroup$ @user1864863 Not really. You are correct in that the point marked as $4P$ was first introduced when doubling $P$, and thus was $-2P$ at the time. But, the example was carefully tailored to have $6P=0$, and, not surprisingly, later that point reappeared as $4P$. As the example was about listing the points $P,2P,3P$ et cetera, the latter role was more important. Mind you, yours war clearly a comment to Álvaro's answer, and should get posted as such. I moved it there, because you have not earned enough rep to comment everywhere. Hop to it. $\endgroup$ Jan 8, 2018 at 6:13

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .