This contains a rebased version of @peterdettman's #21 (to account for the move of lambda splitting from group to scalar, and avoiding secp256k1_num_get_bit which got removed), and then simplifies it to a pure scalar-based version.
Gives around a 0.8% speedup on --enable-endomorphism CFLAGS=-O3, and enables the endomorphism optimization without using GMP (with a 28% performance hit).
Did you measure what it did to the Linf norm of the split numbers?
- In secp256k1_gej_split_exp, there are two divisions used. Since the denominator is a constant known at compile-time, each can be replaced by a multiplication followed by a right-shift (and rounding).
- Add the constants g1, g2 for this purpose and rewrite secp256k1_scalar_split_lambda_var accordingly.
- Remove secp256k1_num_div since no longer used
Rebased-by: Pieter Wuille
This enables the use of the endomorphism optimization without bignum.
@gmaxwell: did 1000000 iterations using randomized ECDSA verifications, for each computing max(bits(wnaf(na_1)),bits(wnaf(na_lam))), and computing the quadratic average over those 1000000 max'es (to punish worst cases a bit stronger). Before this pull: 126.51001458 After this pull: 126.51001359
Both were done with the same sequence of verifications.
Darn, ... :) I was hoping that was why the improvement was so small.
Normal linear averages: 127.501717 and 126.501716. Probably exactly 1 case in 1000000 where it's one less.
ACK.