Napkin Math: Elliptic Curve Addition in terms of Field Operations

Objective
This note aims to analyze the cost of elliptic curve addition in terms of operations in the underlying field.

Summary
We find that adding two points requires the following field operations:

• one inverse operation
• four multiply operations
• 6 adds/subtract operations

Since one inverse operation requires

$\log (p)$ multiplications, that cost will dominate.

Problem Statement

Let

${\mathbb{F}}_p$ be a field, and let

$\mathbb{G}$ be the elliptic curve group defined by

$$\begin{array}{}\text{(1)}& y^2=x^3+ax+b\end{array}$$
for some

$a,b\in {\mathbb{F}}_p$. Let

$A_1$ and

$A_2$ be points in

$\mathbb{G}$, where

$x_1\ne x_2$.^[1]

The objective of this note is to count the number of field operations necessary to compute

$A_3=A_1+A_2$.

Addition in Affine Coordinates

We write

$A_1=(x_1,y_1)$ and

$A_2=(x_2,y_2)$.

We proceed as follows:

• construct the line
  $\mathbb{L}$ connecting
  $A_1$ and
  $A_2$
• use a clever observation to find
  $x_3$, the
  $x$ coordinate of the point of intersection of
  $\mathbb{L}$ and
  $\mathbb{G}$ (and the
  $x$-coordinate of
  $A_3$)
• find
  $y_3$, the
  $y$ coordinate of
  $A_3$

We first write the line connecting

$A_1=(x_1,y_1)$ and

$A_2=(x_2,y_2)$. Denoting the slope of the line as

$m=\frac{y_2-y_1}{x_2-x_1}$, we find

$b=-m{x}_1+y_1$. Then, we can write the equation for

$\mathbb{L}$ as

$$\begin{array}{}\text{(2)}& y=mx-m{x}_1+y_1\end{array}$$

Computing

$m$ requires 2 subtractions, finding one inverse, and one multiplication. Computing

$b$ requires one multiplication and one subtraction.

Cost for constructing

$\mathbb{L}$ is 1 inverse, 2 multiplications, and three subtractions.

AFAIK, Fermat's Little Theorem is the most efficient approach to computing multiplicative inverses. Using repeated squaring, computing

$x^{p-2}$ using takes ~

$\log (p)$ multiplications.

Finding

$(x_3,y_3)$

Substituting equation (2) into equation (1) yields:

$$\begin{array}{}\text{(3)}& (mx-m{x}_1+y_1{)}^2=x^3-ax+b\end{array}$$

Bringing all terms to the right-hand side, we find

$$\begin{array}{}\text{(4)}& 0=x^3+m^2{x}^2+(2m(y_1-m{x}_1)-a)x+b-(y_1-m{x}_1{)}^2\end{array}$$

Now, we make a clever^[1] observation: since

$x_1,x_2,$ and

$x_3$ are solutions to equation (3), we can also write equation (3) in the form

$$\begin{array}{}\text{(5)}& 0=(x-x_1)(x-x_2)(x-x_3)\end{array}$$

By comparing the coefficient of

$x^2$ in equations (4) and (5), we can deduce that

$x_1+x_2+x_3=m^2$. It follows that:

$$x_3=m^2-x_1-x_2$$

Cost for computing

$x_3$ is one multiplication and two subtractions.

Now we can the

$y$ coordinate of the point of intersection by substituting into equation (2). After reflecting across the

$x$-axis, we find the

$y$ coordinate of

$A_3$:

$$y_3=m(x_1-x_3)-y_1$$

Cost for computing

$y_3$ is one multiplication and one subtraction.

Addition in Projective Coordinates

The previous approach requires computing an inverse in order to add elliptic curve points. Writing our points in projective coordinates allows us to avoid that cost.

We write

$P_1=[\frac{x_1}{z_1}:\frac{y_1}{z_1}:1]$ and

$P_2=[\frac{x_2}{z_2}:\frac{y_2}{z_2}:1]$.
Assume

$z_1$ is non-zero and

$x_1\ne x_2$.
We aim to compute

$P_3=P_1+P_2$.

We continue to follow the approach in Section 2.2 here:

It folllows from the previous section that we can write the sum as

$$P_3=[m^2-\frac{x_1}{z_1}-\frac{x_2}{z_2}:m(\frac{x_1}{z_1}-x_3):1]$$
Substituting in our expression for

$x_3$:

$$=[m^2-\frac{x_1}{z_1}-\frac{x_2}{z_2}:m(\frac{x_1}{z_1}-(m^2-\frac{x_1}{z_1}-\frac{x_2}{z_2})):1]$$
Now we can clear denominators:

$$=[m^2{z}_1{z}_2-x_1{z}_2-x_2{z}_1:m(x_1{z}_2-(m^2{z}_1{z}_2-x_1{z}_2-x_2{z}_1)):z_1{z}_2]$$

$$=[m^2{z}_1{z}_2-x_1{z}_2-x_2{z}_1:m{x}_1{z}_2-m^3{z}_1{z}_2-m{x}_1{z}_2-m{x}_2{z}_1:z_1{z}_2]$$
Now, we simultaneously substitute

$m=\frac{y_2{z}_1-y_1{z}_2}{x_2{z}_1-x_1{z}_2}$, and multiply through by

$(x_2{z}_1-x_1{z}_2{)}^3$ to clear denominators:

$$=[(y_2{z}_1-y_1{z}_2{)}^2{z}_1{z}_2-x_1{z}_2-x_2{z}_1)(x_2{z}_1-x_1{z}_2):-(y_2{z}_1-y_1{z}_2{)}^3{z}_1{z}_2-(y_2{z}_1-y_1{z}_2)(x_2{z}_1-x_1{z}_2{)}^2{x}_2{z}_1:z_1{z}_2(x_2{z}_1-x_1{z}_2{)}^3]$$

Warning: Likely contains algebra errors, but it gets the idea across.

The reference notes suggest that with careful accounting it's possible to compute

$P_3$ in 12 additions if

$P_1\ne P_2$ and 14 additions for point doubling.

Addition in Montgomery Form

Details omitted. See Moon Math Manual for details.

Advantage here is constant time scalar multiplication. Note that even though it's "constant time," there's still a slight difference in the computational approach depending on whether

$P_1=P_2$, and whether one of the points is a point at infinity.

Addition in Twisted Edwards Form

Details omitted. See Moon Math Manual for details.

Advantage here is all additions use exactly the same computational approach: no branching necessary in your computational logic.

But, it seems this approach requires computing 2 inverses?!

Footnotes

[1]: For the case where

$A_1=A_2$ we proceed similarly using the tangent line for

$\mathbb{L}$. We can write find the tangent line using implicit differentiation. We find

$m=\frac{dy}{dx}=\frac{3x_1^2+a}{2y_1}$; the computation in this case requires one additional multiplication and one less addition. The remaining case is that

$A_1$ is the reflection of

$A_2$ across the

$x$-axis. In this case, the sum is defined to be the point at infinity.
[2]: See Section 2.2 here