algebra icon indicating copy to clipboard operation
algebra copied to clipboard

Optimize `add_assign` operation for Projective coordinates in Short Weierstrass model

Open tcoratger opened this issue 1 year ago • 0 comments

At the moment, the add_assign operation between two points in projective coordinates in the short weierstrass model implements the generic method (without any assumption over Z1 and Z2) here:

https://github.com/arkworks-rs/algebra/blob/3a6156785e12eeb9083a7a402ac037de01f6c069/ec/src/models/short_weierstrass/group.rs#L451-L537

This corresponds to the following logic: http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl

with a cost of 11M + 5S + 9add + 4*2.

If Z1 = Z2 assumption holds, this cost can be reduced to 5M + 2S + 9add (following https://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-zadd-2007-m).

Would it not be wise to also implement this variant in the add_assign inside a if self.z == other.z condition, in order to reduce the calculation cost of all operations satisfying this assumption, which can occur for several use cases.

  • For example when we simply add a and b which are initially in affine coordinates and transformed into projective coordinates for the occasion, z = 1 for both because the transformation from affine to projective coordinates is done with z = 1.

tcoratger avatar Feb 17 '24 21:02 tcoratger