2
$\begingroup$

How do you add two points P and Q on an elliptic curve over a finite field $\Bbb F_{p}$. For example: adding the points $(1,4)$ and $(2,5)$ on the curve $y^2 = x^3+2x+2$ over $\Bbb F_{11}$. I know one way involves drawing a straight through the two points P and Q and getting a third point R (P+Q) which means using a straight line equation and the elliptic curve equation. Any insights?

$\endgroup$
  • 5
    $\begingroup$ Take Silverman's book, or any other one where the addition law for the elliptic group is explained. It seems to be pretty lonhg to develop it here. $\endgroup$ – DonAntonio May 5 '13 at 22:13
2
$\begingroup$

Consider the case of the curve $y^2 = x^3 + a x + b$ on $\mathbb{R}$ for starters. Let $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ be different points on the curve. You can check that if $s = (y_2 - y_1)/(x_2 - x_1)$, then $x_3 = s^2 - x_1 - x_2$ and $y_3 = y_1 + s (x_3 - x_1)$ then $(x_3, y_3)$ is on the curve and $(x_3, -y_3)$ is collinear with $P$ and $Q$. A computer algebra system like maxima is helpful here.

Adding a point to itself involves a tangent to the curve, so $s = (3 x_1^2 + a) / 2 y_1$ and $x_3 = s^2 - 2 x_1$ and $y_3 = y_1 + s (x_3 - x_1)$.

The same formulas are valid on any field, as long as its characteristic isn't 2 or 3.

$\endgroup$
  • $\begingroup$ The first two sentences are very clear. The third sentence is not, and totally loses me. Could you break that paragraph down into a clearer progression? I don't know what s is, or where you got the two equations immediately thereafter. Moreover the sentence is grammatically weird, you wrote "You can check that if ... then .. and .. then..." Then and then doesn't make sense! Are x3 and y3 coordinates of the point you're terming s? $\endgroup$ – temporary_user_name May 1 '16 at 0:01
  • $\begingroup$ x3 and y3 are the coordinates of the point that is P+Q. But if P=Q, you would have a division by 0 so you will use the tangent line to find the sum ! Imagine that your a summing P and Q with Q getting closer and closer to P, you end up with a tangent like with derivatives $\endgroup$ – Romain B. Nov 19 '17 at 13:36

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.