0
$\begingroup$

enter image description here

How can one derive the underlined formulas that are used in point addition of elliptic curves?

The text is taken from https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication.

I assume that $\lambda$ is the slope and that then $\lambda(x_p-x_r)$ is the addition in the $y$ direction. But why do they subtract $y_p$ instead of adding it? And why is it $\lambda(x_p-x_r)$ and not $\lambda(x_q-x_p)$? As for $x_r$, I am lost.

$\endgroup$
4
$\begingroup$

You may be confusing the third point, say $S$, of intersection of $E$ and the line through $P$ and $Q$ with the point $P + Q = R$. Determining $S$ is just the first step in determining $R$. $R$ is, in turn, the third point of intersection of $E$ and line through $S$ and the zero point $O$. Wikipedia, as is traditional, chooses $O$ to be the point at infinity $\, 0:1:0 \,$ in the projective plane. With that choice for the zero point, the line through $S$ and $O$ is vertical, so, because $E$ is symmetric with respect to the $x$-axis (because $y$ appears only as $y^2$ in the equation for $E$), we just need to change the sign of the $y$-coordinate of $S$ to get $R$.

We now derive the Wikipedia formulas based on the two steps described above. The equation of the line through $P$ and $Q$ is $$y = y_p + \lambda (x - x_p).$$ Substitute that expression for $y$ into $y^2 = x^3 + ax + b$ to get $$x^3 - \lambda^2x^2 +(a + 2\lambda^2 x_p - 2\lambda y_p)x + b - (\lambda x_p - y_p)^2 = 0.$$ The three solutions to that cubic equation give the $x$-coordinates $x_p, x_q, x_s$ of the three points of intersection of the line with $E$. From Vieta's first formula, we see that the sum of those $x$-coordinates is $\lambda^2$ so that $x_p + x_q + x_s = \lambda^2$. When we reflect $S$ over the $x$-axis, the $x$-coordinate does not change, so $x_r = x_s$. Thus, $$x_r = \lambda^2 - x_p - x_q.$$ Using the equation of the line, \begin{align} y_s & = y_p + \lambda (x_s - x_p)\\ & = y_p + \lambda (x_r - x_p) \end{align} When we reflect $S$ over the $x$-axis, the sign of the $y$-coordinate changes, i.e., $y_r = -y_s$. Thus, $$y_r = \lambda (x_p - x_r) - y_p.$$

$\endgroup$

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.