toposware / cheetah

A STARK-friendly elliptic curve defined over a sextic extension of a small prime field.
Apache License 2.0
38 stars 3 forks source link

Speed-up scalar multiplication in the group #1

Closed Nashtare closed 2 years ago

Nashtare commented 2 years ago

Currently the scalar multiplication is done through a simple double-and-add algorithm, skipping the first MSB that is always zero. We would gain from having other, more efficient methods implemented (not necessarily limited to only 1), among which:

More here:

Nashtare commented 2 years ago

Point 2 [Shamir's simultaneous scalar mult] is partially implemented (limited to 2 points, with regular bitwise double-and-add) in commit 7cdb2b3.

Nashtare commented 2 years ago

Pippenger's algorithm is implemented in commit 5b0b2ac5b67dc3ed070a3e62fe8c0d8e1060eac1. Closing this issue as of now. If other optimizations with respect to scalar multiplication seem of any interest, we'll open another related issue.