Multiplication-only lambda splitter without bignum #127

1. 
   sipa commented at 7:02 pm on December 1, 2014: contributor

   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).

2. 
   gmaxwell commented at 2:30 pm on December 2, 2014: contributor

   Did you measure what it did to the Linf norm of the split numbers?
3. Add secp256k1_scalar_mul_shift_var ff8746d457
4. Avoid division when decomposing scalars

   - 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

   cc604e9842
5. Convert lambda splitter to pure scalar code.

   This enables the use of the endomorphism optimization without bignum.

   c35ff1ea44
6. sipa force-pushed on Dec 2, 2014
7. 
   sipa commented at 3:50 pm on December 2, 2014: contributor

   Rebased. @gmaxwell Going to look at that now.
8. 
   sipa commented at 4:03 pm on December 2, 2014: contributor

   @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.

9. 
   gmaxwell commented at 4:09 pm on December 2, 2014: contributor

   Darn, … :) I was hoping that was why the improvement was so small.
10. 
    sipa commented at 4:11 pm on December 2, 2014: contributor

    Normal linear averages: 127.501717 and 126.501716. Probably exactly 1 case in 1000000 where it’s one less.
11. 
    gmaxwell commented at 7:11 pm on December 3, 2014: contributor

    ACK.
12. sipa merged this on Dec 3, 2014
13. sipa closed this on Dec 3, 2014

    ---

14. sipa referenced this in commit d5e8362ae5 on Dec 3, 2014
15. roconnor-blockstream cross-referenced this on Sep 21, 2020 from issue Increase precision of g1 and g2. by roconnor-blockstream

Contributors
sipa gmaxwell