4
$\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$
  • 2
    $\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 '14 at 14:46
  • 3
    $\begingroup$ Read Silverman's "The Arithmetic of Elliptic Curves", III.2 .Excellent book, btw. $\endgroup$ – DonAntonio Mar 8 '14 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 '14 at 14:50
  • $\begingroup$ Indeed "The Arithmetic of Elliptic Curves" is an excellent book. $\endgroup$ – Kaladin Mar 8 '14 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 '14 at 18:30
9
$\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$
  • 1
    $\begingroup$ Thank you so much! This is just a perfect answer :) It helped me a lot! $\endgroup$ – Luca Mar 9 '14 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$ – Álvaro Lozano-Robledo Mar 10 '14 at 1:53
  • $\begingroup$ Ref: Alvaro's answer: Looks like there is a typo;'4P' should be replaced with '-2P' $\endgroup$ – user1864863 Jan 7 '18 at 23:40
  • $\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$ – Jyrki Lahtonen Jan 8 '18 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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