Batch Inverse for Batch Point Additions
Motivation
The addition of two elliptic curve points and to receive must be done like so (See here for more information on elliptic curves):
We see that the calculation of the slope always includes the field inverse operation of , 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 total points as and where we are attempting to obtain the sums where .
Note that the points and are defined as follows:
As per definition, for a single point addition, computing requires computing .
Thus, we define the following instead:
With this definition, the only field inverse operation required across all calculations is . As is the total product of all values, it only needs to be calculated once across all inverses . Therefore, we now require the inverse of only one value when computing multiple point additions at once.
Note that the numerator 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