Skip to content
This repository has been archived by the owner on Dec 5, 2023. It is now read-only.

Speed-up scalar multiplication in the group #1

Closed
3 tasks
Nashtare opened this issue Nov 16, 2021 · 2 comments
Closed
3 tasks

Speed-up scalar multiplication in the group #1

Nashtare opened this issue Nov 16, 2021 · 2 comments
Labels
enhancement New feature or request

Comments

@Nashtare
Copy link
Contributor

Nashtare commented Nov 16, 2021

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:

  • variable based scalar mult
  • Shamir's simulteneous scalar mult (Algorithm 3.48, originally from Straus - can be generalized to more than 2 points, and either constant time with fixed window or variable time with sliding window. Could be beneficial in the Schnorr signature for computing h.P + r.G.)
  • Pippenger's algorithm

More here:

@Nashtare Nashtare added the enhancement New feature or request label Nov 16, 2021
@Nashtare
Copy link
Contributor Author

Nashtare commented Dec 6, 2021

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

@Nashtare
Copy link
Contributor Author

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

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant