Adding Points on an Elliptic Curve

Draw a line through two points on the curve. It meets the curve once more. Reflect that point across the x-axis, and you have the sum.

Elliptic curvesPoint additiondemo

Objectives

Add two points on y^2 = x^3 + ax + b with the chord rule, and double a point with the tangent rule.
Explain why P + (−P) needs the point at infinity O, and why O acts like zero.
Recognize a singular curve from 4a^3 + 27b^2 = 0, and say why it is not used.

33%

Draw a line through two points, find where it meets the curve again, and reflect.

y^2 = x^3 + ax + b, with 4a^3 + 27b^2 ≠ 0

The picture

the curve

The two axes use different scales, so the picture fits. Lines stay straight and the tangent still touches the curve.

The curve

Curve: y^2 = x^3 + ax + b. An elliptic curve is the set of points (x, y) on it, plus one extra point O, the point at infinity. On this page x and y are real numbers, so the curve can be drawn. The example is y^2 = x^3 − x + 1 (a = −1, b = 1). Change a and b.

-1

4a^3 + 27b^2

4 × (-1)^3 + 27 × 1^2 = 23 → positive: one piece

The curve is its own mirror image across the x-axis. If (x, y) is on the curve, then (x, −y) is too, because y and −y have the same square. For a point P = (x, y), the mirror point (x, −y) is written −P.

Add two points

For distinct points P and Q, draw their line. Reflect its third intersection R across the x-axis to get P + Q. For 2P, use the tangent at P. A vertical line gives P + (−P) = O.

two worked examples

which sum to draw

x of P

-1.000

P is on the

x of Q

0.000

Q is on the

Where the curve has a gap, the x sliders jump across it, because no point of the curve has an x there.

The line through P and Q meets the curve at exactly one more point, R. Reflect R across the x-axis to get P + Q.

The points of the addition and their coordinates, to three decimals.
Point	Shape	x	y
P	circle	-1.000	1.000
Q	square	0.000	1.000
R	hollow diamond	1.000	1.000
P + Q	triangle	1.000	-1.000

the arithmetic, to three decimals

slope s = (y_Q − y_P) / (x_Q − x_P) = (1.000 − 1.000) / (0.000 − (-1.000)) = 0.000 x = s^2 − x_P − x_Q = 0.000^2 − (-1.000) − 0.000 = 1.000 y = s(x_P − x) − y_P = 0.000 × ((-1.000) − 1.000) − 1.000 = -1.000 R = (x, −y) = (1.000, 1.000) P + Q = (x, y) = (1.000, -1.000) check: y^2 = 1.000 x^3 + ax + b = 1.000

The point at infinity, and the rules

Point O is the point at infinity. A vertical line has no third intersection point, so the curve gets one extra point that is not in the picture. Think of it as the point where every vertical line ends, far up. O acts like zero: P + O = P. A vertical line gives P + (−P) = O. Choose “P + (−P)” above to see it.

The rules of point addition, each with its meaning in words.
Rule	In words
P + O = P	O acts like zero.
P + (−P) = O	−P is the opposite of P, as −5 is the opposite of 5.
P + Q = Q + P	The line through P and Q is the line through Q and P.
(P + Q) + T = P + (Q + T)	The order of the additions does not matter. This one is true, but it is hard to see in a picture.

These are the rules of ordinary addition. That is why this operation is called addition, even though it is drawn with lines.

The next page keeps these formulas and changes the numbers: every coordinate is taken modulo a prime. The curve becomes a scatter of dots, and the line becomes a set of dots too. The picture then no longer shows where an answer will land, and cryptography needs exactly that.

step 1/3

CPE 645 / CS 685

Adding Points on an Elliptic Curve

Diffie–Hellman Key Exchange

An Elliptic Curve Modulo a Prime