You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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}.
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 :
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
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
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 justdigit € {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
ornegate
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
The text was updated successfully, but these errors were encountered: