Explicit Addition Formulae

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 \]

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

\[ \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 💡