algebra icon indicating copy to clipboard operation
algebra copied to clipboard

Published 20 hours ago • verified publisher icon arkworks-rs

Add GLV-based scalar multiplication for appropriate curves.

Open Pratyush opened this issue 5 years ago • 5 comments

We can obtain upto 30% speed ups for scalar multiplication by implementing a GLV-type endomorphism. See Section 3.5 (Pg 123) of http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.394.3037&rep=rep1&type=pdf

Pratyush avatar Feb 03 '20 17:02 Pratyush

I think it still falls in patents US7110538B2 and US7995752B2 until September 2020.

yelhousni avatar Feb 28 '20 09:02 yelhousni

We can add it behind a feature until then =)

Pratyush avatar Feb 29 '20 02:02 Pratyush

I know this applies to the BN curves (as long as p = 1 mod 3) and the to-be-implemented BW6-761 curve. Which other curves does this apply to?

jon-chuang avatar Mar 29 '20 21:03 jon-chuang

I believe a more modern reference for pairing-friendly curves would be link

jon-chuang avatar Apr 18 '20 04:04 jon-chuang

Actually the speedup can be more than 30% especially if using w-NAF, it is more like 80% over the w-NAF base case. Together, one achieves a more than 2x speedup.

jon-chuang avatar Sep 08 '20 18:09 jon-chuang