Consider an elliptic curve $$E$$ (in Weierstrass form)

$Y^2 + a_1 XY + a_3 Y = X^3 + a_2 X^2 + a_4 X + a_6$

over a field $$K$$.

Let $$P = (x_1, y_1)$$ be a point on $$E(K)$$.

### Negation

To compute $$-P$$, we need to find the line through $$P$$ and $$O$$ (recall $$O = OO$$), and find the third point of intersection. The line through $$P$$ and $$O$$ is the vertical line through $$P$$, so we need to find the points of intersection of $$X = x_1$$ and the curve. In other words, we need to solve

$Y^2 + (a_1 x_1 + a_3) Y - (x_1^3 + a_2 x_1^2 + a_4 x_1 + a_6) = 0$

Since we know one solution is $$Y = y_1$$, we know that the other must be $$- a_1 x_1 - a_3 - y_1$$. That is,

$-P = (x_1, -a_1 x_1 - a_3 - y_1)$

Recall that if $$\mathrm{char} K \ne 2$$, we can affinely transform the curve so that $$a_1 = a_3 = 0$$, so that to find the inverse of $$P$$ we simply negate its $$y$$-coordinate.

### Point Doubling

To find $$P + P = 2P$$ (whose coordinate we’ll denote by $$(x_3, y_3)$$), we need the equation of the tangent at $$P$$. The gradient of the tangent at the point $$(X, Y)$$ is given by $$(dE/dX) / (dE/dY) = (3X^2 + 2a_2 X - a_1 Y + a_4) / (2 Y + a_1 X + a_3)$$. So setting

$\lambda = \frac {3x_1^2 + 2a_2 x_1 - a_1 y_1 + a_4} {2y_1 + a_1 x_1 + a_3}$

means the tangent at $$P$$ is given by the equation $$Y = \lambda X - \lambda x_1 + y_1$$. Substituting this into the equation for $$E$$ and negating the coefficient of $$X^2$$ gives the sum of the roots:

$\lambda^2 + \lambda a_1 - a_2$

which means the $$x$$-coordinate of the third point of intersection must be

$x_3 = \lambda^2 + \lambda a_1 - a_2 - 2x_1$

and the corresponding $$y$$-coordinate can be found from the equation of the tangent at $$P$$:

$y' = \lambda x_3 - \lambda x_1 + y_1$

Lastly we need to negate $$(x_3, y')$$ which from above is

$y_3 = -a_1 x_3 - a_3 - \lambda x_3 + \lambda x_1 - y_1$

Suppose we have a second point $$Q = (x_2, y_2)$$ different from $$P$$. We wish to find $$P + Q$$ whose coordinates we shall denote by $$(x_3, y_3)$$. If $$P = -Q$$, then $$P + Q = O$$. Otherwise the gradient of the line determined by $$P$$ and $$Q$$ is

$\lambda = \frac{y_2 - y_1}{x_2 -x_1}$

and the equation of the line between $$P$$ and $$Q$$ is $$Y = \lambda X - \lambda x_1 + y_1$$. Substituting this into the curve gives the equation

$(\lambda X - \lambda x_1 + y_1)^2 + (a_1 X+a_3) (\lambda X - \lambda x_1 + y_1) = X^3 + a_2 X^2 + a_4 X + a_6$

The sum of the roots, i.e. the negation of the coefficient of $$X^2$$ is $$\lambda^2 + a_1 \lambda - a_2$$, hence

$x_3 = \lambda^2 + a_1 \lambda - a_2 - x_1 - x_2$

and the corresponding $$y$$-coordinate can be found by substituting into the equation of the $$P$$-$$Q$$ line:

$y' = \lambda x_3 - \lambda x_1 + y_1$

As before, we must negate this third point $$(x_3, y')$$ which from above gives

$y_3 = -a_1 x_3 - a_3 - \lambda x_3 + \lambda x_1 - y_1$

Ben Lynn blynn@cs.stanford.edu 💡