Clever choice of (mult-)exponentiation algorithm
Closed this issue · 7 comments
Currently, the LazyGroup has a specific (mult-)exponentiation algorithm hardcoded. Instead, the LazyGroup::compute(Multiexponentiation) method (and related ones) should more cleverly choose what algorithm to use depending on the input, and/or allow the user to configure this.
How to we intend on making this clever choice? The previous version of math had a method to estimate cost of inversion for the group which was enough to decide between WNAF and the regular interleaved window sliding algorithm (although WNAF was generally slower even in fast inv groups due to the inefficient WNAF representation computation). I thought this was a reasonable approach.
Another option would be to hardcode the choice based on the GroupImpl instance, but that is harder to maintain since you need to update the mapping for each new GroupImpl which is easier to forget than forcing the developer to implement an inversion cost estimation method. Unless we just crash the library if there is no choice explicitly defined.
wnaf representation computation seemed relatively fast overall, so it feels kind of weird that this should be the deciding factor.
I've taken a try at improving wnaf computation speed: #28
Like I have mentioned during the discussion for issue #29, our own groups have pretty inefficient Op implementations which makes wNAF the best choice in general. For Mcl my experiments indicate that wNAF is better as well (even if only by a small margin), especially with the faster inversion we have now for GT.
Regarding configuration, I am adding one boolean each for exponentiation and multiexponentiation to the LazyGroup that allows enabling the use of the sliding window variant. If we latter also want to add the simultaneous approach (currently difficult due to the precomputations being very different), we can replace that with an enum of course.
The only thing missing now is deciding how to enable the user to easily take an inverted base and convert it to a single LazyGroupElement instead of an InvLazyGroupElement wrapping a LazyGroupElement. The former should then allow for precomputations ahead of time as desired.
If we latter also want to add the simultaneous approach (currently difficult due to the precomputations being very different), we can replace that with an enum of course.
We should probably replace this before release so that we don't break API if we change it later.
The only thing missing now is deciding how to enable the user to easily take an inverted base and convert it to a single LazyGroupElement instead of an InvLazyGroupElement wrapping a LazyGroupElement.
I don't understand this. What do you mean?
I don't understand this. What do you mean?
Moved discussion of that aspect into #29.
I ended up putting a cost inversion threshold for wNAF in #30 at 1.5 inversions per op for now. The algorithm will be chosen accordingly. We don't actually have any groups with such slow inversions though, so for now wNAF will still be always used. Finding an exact value is not so easy since stuff like number of negative exponents and whether negative exponents are precomputed also affect the exact result. Sliding can be worth it for only positive exponents, for example.