[go: nahoru, domu]

Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Investigate Canonical Signed Digit representation for faster exponentiations and EC scalar mul #108

Open
feltroidprime opened this issue Feb 19, 2023 · 1 comment

Comments

@feltroidprime
Copy link
Contributor
feltroidprime commented Feb 19, 2023

The canonical signed digit, or Non-Adjacent Form (NAF) is a unique way to represent a binary number with a lower absolute hamming weight, using digit € {0,1,-1} as coefficients instead of just digit € {0,1}.

See https://en.wikipedia.org/wiki/Non-adjacent_form

It should improve performance in exponentiation by squaring algorithms and similar as you just need a sub or negate function for -1 cases.
The overall hamming weight W = sum([abs(digit) for digit in bin(int)]) is in average 1/3 instead of 1/2.
Using this representation should lead to improvements in the range of 10-25% for the average case.

An example of this technique can be found in the gnark repo :

definition : https://github.com/ConsenSys/gnark-crypto/blob/8f7ca09273c24ed9465043566906cbecf5dcee91/ecc/bn254/bn254.go#L141-L143
usage (miller loop) : https://github.com/ConsenSys/gnark-crypto/blob/8f7ca09273c24ed9465043566906cbecf5dcee91/ecc/bn254/pairing.go#L161

@jules
Copy link
jules commented Feb 20, 2023

As an addendum to your point here, this can be combined very efficiently with GLV scalar multiplication, which can allow for ~50% speedups when performing group scalar muls. I've implemented the code for BLS12-377 here and I'd be happy to port that code over as well :)

@feltroidprime feltroidprime changed the title Investigate Canonical Signed Digit representation for faster exponentiations Investigate Canonical Signed Digit representation for faster exponentiations and EC scalar mul Feb 22, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants