## Explicit Addition Formulae

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

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

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,

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

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:

which means the \(x\)-coordinate of the third point of intersection must be

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

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

### Point Addition

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

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

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

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

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

*blynn@cs.stanford.edu*💡