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