Batch Inverse for Batch Point Additions

Motivation

The addition of two elliptic curve points P=(xP,yP)P=(x_P,y_P) and Q=(xQ,yQ)Q=(x_Q,y_Q) to receive R=P+Q=(xR,yR)R = P+Q = (x_R, y_R) must be done like so (See here for more information on elliptic curves):

m=yQyPxQxPxR=m2xPxQyR=m(xPxR)yPm = \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 mm always includes the field inverse operation of (xQxP)1(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.

Algorithm Process

We apply Batch Inversion to our point additions. Suppose we have two sets of nn total points as {P0,P1,,Pn1}\{P_0, P_1, \dots ,P_{n-1}\} and {Q0,Q1,,Qn1}\{Q_0, Q_1, \dots ,Q_{n-1}\} where we are attempting to obtain the sums {R0,R1,,Rn1}\{R_0, R_1, \dots ,R_{n-1}\} where Ri=Pi+QiR_i = P_i + Q_i.

Note that the points PiP_i and QiQ_i are defined as follows:

Pi=(xPi,yPi)Qi=(xQi,yQi)\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 mim_i requires computing (xQixPi)1(x_{Q_i}-x_{P_i})^{-1}.

Thus, we define the following instead:

λi=xQixPi(xQixPi)1=1λi=jiλjk=0n1λk\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 (xQixPi)1(x_{Q_i} -x_{P_i})^{-1} calculations is (k=0n1λk)1(\prod_{k=0}^{n-1} \lambda_k)^{-1}. As k=0n1λk\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 (xQixPi)1(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 jiλj\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 of Batch Inversion to learn more about the total cost.

References

Written by Ashley Jeong of A41

Last updated