Adding points on an elliptic curve

It's actually fairly easy to derive the formulas for adding points on an elliptic curve. Here's how to do it.

Suppose that we have three points

P1 = (x1,y1)

P2 = (x2,y2)

and

P3 = P1 + P2 = (x3,y3)

on the elliptic curve

y2 = x3 + ax + b

First, let's assume that P1 != P2. Let m be the slope of the line through the points P1 and P2 so that

m = (y2y1) / (x2x1)

From the point-slope form of a line we have that

yy1 = m(xx1)

so that

y = m(xx1) + y1

and that

y2 = (m(xx1) + y1)2

= m2(xx1)2 + 2my1(xx1) + y12

We also have that

y2 = x3 + ax + b

so that we have that

x3 + ax + b = m2(xx1)2 + 2my1(xx1) + y12

or that

x3 + ax + bm2(xx1)2 + 2my1(xx1) + y12 = 0 (∗)

This polynomial has three roots: x1, x2 and x3, so we can also write it as

(xx1)(xx2)(xx3) = 0

or

x3 – (x1 + x2 + x3)x2 + … = 0 (∗∗)

Equating the coefficients for x2 in (∗) and (∗∗) we see that

m2 = – (x1 + x2 + x3)

Solving this for x3 gives us that

x3 = m2x1x2

Now because (x3,y3) is on the line defined by

yy1 = m(xx1)

we have that

y3y1 = m(x3x1)

or that

y3 = m(x3x1) + y1

This gives that

m = (y2y1) / (x2x1)

x3 = m2x1x2

y3 = m(x3x1) + y1

If P1 = P2 then we find m in a different way. In this case we have

y2 = x3 + ax + b

so that

2yy′ = 3x2 + a

so that

y′ = (3x2 + a) / (2y)

so that we want

m = (3x12 + a) / (2y1)

but everything else is the same. We can then write

m = (3x12 + a) / (2y1)

x3 = m2 – 2x1

y3 = m(x3x1) + y1

Leave a Reply

Your email address will not be published. Required fields are marked *