EC Cryptography Tutorials - Herong's Tutorial Examples - Version 1.00, by Dr. Herong Yang
Algebraic Solution for Distinct Points
This section provides an algebraic solution for calculating the addition operation of two distinct points on an elliptic curve.
Case 3: P and Q are two distinct points.
Let m be the slope of the straight line passing through P, the line can be expressed as the following equation: y = m(x - xP) + yP The other intersection, -R, of the line and the curve must satisfy the line equation and the curve equation: -yR = m (xR - xP) + yP (1) (-yR)2 = (xR)3 + a(xR) + b (2) Note that -yR in equation (2) can be replaced by the right hand side of equation (1): (m(xR - xP) + yP)2 = (xR)3 + a(xR) + b Regrouping terms will result a cubic equation for xR: (xR)3 - m2(xR)2 + (a - 2m(yP) + 2m2(xP))(xR) + b - (m(xP)-yP)2 = 0 We know that a cubis equation has 3 roots and their sum is the negation of the coefficient of the second term based on Vieta's first formula, see Vieta's formulas at wikipedia.org: xP + xQ + xR = m2 (7) Rearrange terms of equations (1) and (7) gives us the simpliest way to calculate, R: xR = m2 - xP - xQ (8) yR = m(xP - xR) - yP (9) The slope of the line, m, can be determined by the other point, Q, on the line: yP - yQ m = --------- (10) xP - xQ
Now we can calculate R = P + Q with equations (8), (9) and (10) with any given distinct points, P and Q.
By the way, proof of Vieta's formulas can be found in "Cubic Equations" by Arkajyoti Banerjee and Ayush G Rai at https://brilliant.org/wiki/cubic-equations/
Last update: 2019.
Table of Contents