Fixes #506
Increase sparsity of pippenger fixed window naf representation #513
pull jonasnick wants to merge 4 commits into bitcoin-core:master from jonasnick:wnaf_fixed-zeros changing 2 files +92 −32-
jonasnick commented at 6:21 PM on March 1, 2018: contributor
-
Increase sparsity of pippenger fixed window naf representation 6dbb007869
-
jonasnick commented at 7:57 PM on March 1, 2018: contributor
ecmult_multi pippenger speedup
without endo: 2 points 11%, pippenger threshold (160 points) 0.74% with endo: 2 points 10%, pippenger threshold (88 points) 2.1% -
96f68a0afc
Don't invert scalar in wnaf_fixed when it is even because a caller might
intentionally give a scalar with many leading zeros.
-
Fix bug in wnaf_fixed where the wnaf array is not completely zeroed when given a 0 scalar. 9e36d1bfe2
-
Don't touch leading zeros in wnaf_fixed. ec0a7b3ae3
-
jonasnick commented at 3:06 PM on March 23, 2018: contributor
Added wnaf_fixed bugfix and two commits that further increase sparsity. Now it's possible to use precomputation with pippenger similar to using the endomorphism: split a scalar, point pair
(s, G)into(s1, ..., sn, G, ..., Gn)where allsihave256 -256/nleading zeros ands1*G + ... + sn*Gn = s*G.With 128 points and
n=8this gives a speedup of 6% over endomorphism (13% over non-endo). See https://github.com/jonasnick/secp256k1/blob/bench_ecmult_precomp/src/bench_ecmult_precomp.c#L138 for the benchmarking and splitting code. -
sipa commented at 1:26 AM on March 27, 2018: contributor
Lightly tested ACK ec0a7b3ae3a09bd2ffbbeec83abe6c5042ce4a56
-
apoelstra commented at 2:49 PM on March 27, 2018: contributor
Let me test it with the BP code before merging.
-
apoelstra commented at 8:59 PM on March 27, 2018: contributor
ACK
- sipa merged this on Apr 5, 2018
- sipa closed this on Apr 5, 2018
- sipa referenced this in commit dbc3ddd5e2 on Apr 5, 2018
