EC Cryptography Tutorials - Herong's Tutorial Examples - v1.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/
Table of Contents