# Fast Elliptic Curve Arithmetic and Improved WEIL Pairing Evaluation

This explains <https://arxiv.org/abs/math/0208038>.

## Motivation

Compute $$2P + Q$$ without the intermediate results $$2P$$ and $$P + Q$$ given $$E: y^2 = x^3 + a \cdot x + b$$, where $$4a^3 + 27b^2 \ne 0$$,

* $$2P$$: 1 multiplication, 2 squarings and 1 division. If $$P = (x\_1, y\_1)$$, $$R = 2P = (x\_2, y\_2)$$ is computed as follows:

$$
\lambda = \frac{3 {x\_1}^2 + a}{2 y\_1}
\x\_2 = \lambda^2 - 2x\_1 \\
y\_2 = (x\_1 - x\_2) \lambda - y\_1
$$

* $$P + Q$$: 1 multiplication, 1 squaring and 1 division. If $$P = (x\_1, y\_1)$$ and $$Q = (x\_2, y\_2)$$, $$R = P + Q = (x\_3, y\_3)$$ is computed as follows:

$$
\lambda\_1 = (y\_2 - y\_1) / (x\_2 - x\_1),\\
x\_3 = {\lambda\_1}^2 - x\_1 -x\_2,    \\
y\_3 = (x\_1 - x\_3)\lambda\_1 - y\_1
$$

* Naive $$2P + Q$$: 2 multiplications, 3 squarings and 2 divisions&#x20;

How can we improve this?

## **Algorithm**

Suppose $$P = (x\_1, y\_1)$$ and $$Q = (x\_2, y\_2)$$ are distinct points on $$E$$, with $$x\_1 \ne x\_2$$. The sum $$P + Q$$ has coordinates $$(x\_3, y\_3)$$, where:

$$
\lambda\_1 = (y\_2 - y\_1) / (x\_2 - x\_1),\ x\_3 = {\lambda\_1}^2 - x\_1 -x\_2, \ y\_3 = (x\_1 - x\_3)\lambda\_1 - y\_1
$$

Now suppose we want to add $$(P + Q)$$ to $$P$$. To do this, we add $$(x\_1, y\_1)$$ to $$(x\_3, y\_3)$$ using the same addition rule. Assuming $$x\_3 \ne x\_1$$, the resulting coordinates are $$(x\_4, y\_4)$$, where

$$
\lambda\_2 = (y\_3 - y\_1) / (x\_ 3 - x\_1), \ x\_4 = {\lambda\_2}^2 - x\_1 - x\_3, \ y\_4 = (x\_1 - x\_4)\lambda\_2 - y\_1
$$

We can omit the explicit computation of $$y\_3$$ since it is used only to calculate $$\lambda\_2$$. Instead, $$\lambda\_2$$ can be computed directly as:

$$
\begin{align\*}
\lambda\_2 &= (y\_3 - y\_1) / (x\_3 - x\_1)\\
&= ((x\_1 - x\_3) \lambda\_1 - 2y\_1) / (x\_3 - x\_1) \\
&= -\lambda\_1 - 2y\_1 / (x\_3 - x\_1) \\
\end{align\*}
$$

Which means you can compute $$\lambda\_2$$ using $$x\_1, y\_1$$ and $$\lambda\_1$$.

$$
\lambda\_2 = -\lambda\_1 - 2y\_1 / ({\lambda\_1}^2 -x\_2 - 2x\_1)
$$

Additionally, you can compute $$x\_4$$ using $$x\_2, \lambda\_1$$ and $$\lambda\_2$$.

$$
\begin{align\*} x\_3 &= {\lambda\_1}^2 - x\_1 - x\_2 \\
x\_3 - x\_4 &= {\lambda\_1}^2 - x\_1 - x\_2 -( {\lambda\_2}^2 - x\_1 - x\_3 ) \ -x\_4 &={\lambda\_1}^2 - x\_2 - \lambda\_2^2 \ x\_4 &= x\_2 + {\lambda\_2}^2 - {\lambda\_1}^2 \end{align\*}
$$

This trick can also be applied when computing $$3P$$. Thus, $$3P + Q = ((P + Q) + P) + P$$ saves 2 multiplicaitons.

<figure><img src="https://755218234-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2Frwz1ZAZJtK5FHz4Y1esA%2Fuploads%2Fgit-blob-399b460537c39d758cc36c6c3e749260b4a5cb9a%2Fimage.png?alt=media" alt=""><figcaption></figcaption></figure>

## Conclusion

The cost of this algorithm is as follows:

* Optimized $$2P + Q$$: 1 multiplication, 2 squarings and 2 divisions (+ 1 squaring when $$P = Q$$)
  * Idea: $$(P + Q) +P$$ instead of $$2P + Q$$ and $$y$$-coordinate is not computed when computing $$(P + Q)$$ ⇒ This saves a field multiplication
  * if $$P = Q$$
    * 2 \* (1 multiplication, 2 squarings and 1 division) - 1 multiplication
  * otherwise
    * 2 \* (1 multiplication, 1 squaring and 1 division) - 1 multiplication

> Written by [Ryan Kim](https://app.gitbook.com/u/cPk8gft4tSd0Obi6ARBfoQ16SqG2 "mention") of Fractalyze