# 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](https://fractalyze.gitbook.io/intro/~/revisions/GBuVDfZJZBNDtoleSgnx/primitives/abstract-algebra/elliptic-curve)):

$$
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](https://fractalyze.gitbook.io/intro/~/revisions/GBuVDfZJZBNDtoleSgnx/primitives/abstract-algebra/group/batch-inverse).

## Algorithm Process

We apply[ Batch Inversion](https://fractalyze.gitbook.io/intro/~/revisions/GBuVDfZJZBNDtoleSgnx/primitives/abstract-algebra/group/batch-inverse) 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](https://fractalyze.gitbook.io/intro/~/revisions/GBuVDfZJZBNDtoleSgnx/primitives/group/batch-inverse#computational-complexity) of [Batch Inversion](https://fractalyze.gitbook.io/intro/~/revisions/GBuVDfZJZBNDtoleSgnx/primitives/abstract-algebra/group/batch-inverse) 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](https://app.gitbook.com/u/PNJ4Qqiz7kSxSs58UIaauk95AO43 "mention") of Fractalyze