Module combine 

Batch elliptic curve algorithms based on the batch-affine principle.

The principle is the following:

Usually, affine coordinates are not used because curve operations require division, which is very inefficient. However, if one is performing a large number of curve operations at the same time, then the inverses can be computed efficiently using the batch inversion algorithm which allows you to compute the inverses for an array of elements at a cost of 3 multiplications per element.

With the reduced cost of inversion, in settings where you are computing many parallel elliptic curve operations, it is actually cheaper to use affine coordinates.

Most algorithms in this module take an argument denominators: &mut Vec<F> which is a scratch array used for performing inversions. It is passed around to avoid re-allocating such a scratch array within each algorithm.

Functions

add_pairs_in_place 🔒

affine_shamir_window_table

affine_shamir_window_table_one

affine_window_combine

affine_window_combine_base 🔒

affine_window_combine_one

affine_window_combine_one_base 🔒

affine_window_combine_one_endo

Given vectors of curve points g1 and g2, compute a vector whose ith entry is g1[i] + g2[i].scale(chal.to_field(endo_coeff))

affine_window_combine_one_endo_base 🔒

Uses a batch version of Algorithm 1 of https://eprint.iacr.org/2019/1021.pdf (on page 19) to compute g1 + g2.scale(chal.to_field(endo_coeff))

batch_add_assign

Given arrays of curve points v0 and v1 do v0[i] += v1[i] for each i.

batch_add_assign_no_branch 🔒

Given arrays of curve points v0 and v1 do v0[i] += v1[i] for each i, assuming that for each i, v0[i].x != v1[i].x so we can use the ordinary addition formula and don’t have to handle the edge cases of doubling and hitting the point at infinity.

batch_double_in_place 🔒

Double an array of curve points in-place.

batch_endo_in_place 🔒

batch_negate_in_place 🔒

shamir_window_table

window_combine

window_shamir 🔒