# Batch Inverse for Batch Point Additions

## Motivation

The addition of two elliptic curve points $$P=(x\_P,y\_P)$$ and $$Q=(x\_Q,y\_Q)$$ to receive $$R = P+Q = (x\_R, y\_R)$$ must be done like so ([See here for more information on elliptic curves](/intro/primitives/abstract-algebra/elliptic-curve.md)):

$$
m = \frac{y\_Q - y\_P}{x\_Q - x\_P} \\
x\_R=m^2-x\_P-x\_Q\\
y\_R=m(x\_P-x\_R)-y\_P
$$

We see that the calculation of the slope $$m$$ always includes the field inverse operation of $$(x\_Q-x\_P)^{-1}$$, but we know that field inverse operations are expensive. Thus, when computing multiple point additions at once, we want to find a way to only require a singular field inverse operation in total. This can simply be done with our previously established concept of [Batch Inverse](/intro/primitives/abstract-algebra/group/batch-inverse.md).

## Algorithm Process

We apply[ Batch Inversion](/intro/primitives/abstract-algebra/group/batch-inverse.md) to our point additions. Suppose we have two sets of $$n$$ total points as $${P\_0, P\_1, \dots ,P\_{n-1}}$$ and $${Q\_0, Q\_1, \dots ,Q\_{n-1}}$$ where we are attempting to obtain the sums $${R\_0, R\_1, \dots ,R\_{n-1}}$$ where $$R\_i = P\_i + Q\_i$$.

Note that the points $$P\_i$$ and $$Q\_i$$ are defined as follows:

$$
\begin{align\*}
P\_i &= (x\_{P\_i}, y\_{P\_i}) \\
Q\_i &= (x\_{Q\_i}, y\_{Q\_i}) \\
\end{align\*}
$$

As per definition, for a single point addition, computing $$m\_i$$ requires computing $$(x\_{Q\_i}-x\_{P\_i})^{-1}$$.

Thus, we define the following instead:

$$
\begin{align\*}
\lambda\_i &= x\_{Q\_i} - x\_{P\_i} \\
(x\_{Q\_i} -x\_{P\_i})^{-1} &= \frac{1}{\lambda\_i} =\frac{\prod\_{j\neq i}\lambda\_j}{\prod\_{k=0}^{n-1}\lambda\_k}
\end{align\*}
$$

With this definition, the only field inverse operation required across all $$(x\_{Q\_i} -x\_{P\_i})^{-1}$$ calculations is $$(\prod\_{k=0}^{n-1} \lambda\_k)^{-1}$$. As $$\prod\_{k=0}^{n-1} \lambda\_k$$ is the total product of all $$\lambda$$ values, it only needs to be calculated once across all inverses $$(x\_{Q\_i} -x\_{P\_i})^{-1}$$. Therefore, we now require the inverse of only one value when computing multiple point additions at once. 

> Note that the numerator $$\prod\_{j\neq i}\lambda\_j$$ will introduce new field multiplication operations, but this is fine as the cost of these multiplications is far less than computing more field inverse operations.

Refer to the [Computational Complexity Section](/intro/primitives/abstract-algebra/group/batch-inverse.md#computational-complexity) of [Batch Inversion](/intro/primitives/abstract-algebra/group/batch-inverse.md) to learn more about the total cost.

## References

* <https://hackmd.io/1mpavmFmQNWrahBi8mHBjQ>
* <https://hackmd.io/@tazAymRSQCGXTUKkbh1BAg/Sk27liTW9#Optimization-1-Batch-Affine-for-Point-Addition>

> Written by [Ashley Jeong](mailto:undefined) of Fractalyze


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://fractalyze.gitbook.io/intro/primitives/abstract-algebra/elliptic-curve/batch-inverse-for-batch-point-additions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.