Weak normalization #154

1. 
   sipa commented at 2:05 pm on December 10, 2014: contributor

   This introduces the concept of weak normalization (reducing the magnitude to 1, but not fully normalizing), and then using this for testing equality between field elements (which can be done by subtracting weakly normalized elements + comparing to zero after fully normalizing, instead of comparing after two full normalizes). This gives a 2% signing speedup, and a 0.4% speedup for validation.

   Built on top of #123.

2. sipa force-pushed on Dec 10, 2014
3. sipa force-pushed on Dec 10, 2014
4. sipa force-pushed on Dec 10, 2014
5. 
   peterdettman commented at 2:21 am on December 12, 2014: contributor

   Definitely a useful concept, and I’ve been playing with the idea in a local branch for a while, as there are several places in the group operations where we only need to reduce the magnitude. I’ve noticed a further speedup using a method _reduces_to_zero, which internally calculates the weak normal, then only has to test for two possible zero values (0, P), and doesn’t have to actually write back. In double/add ops, we can test h,i values for zero this way, instead of u?,s? equality checks.

   I could PR to your branch if you like, or just follow up once it’s in?

6. 
   peterdettman commented at 7:12 am on December 12, 2014: contributor

   I put together a patch: https://github.com/peterdettman/secp256k1/commit/db0e03fb1b29dd4e1278b139d617f29cb0191163
7. 
   gmaxwell commented at 2:42 pm on December 12, 2014: contributor

   @peterdettman I think your patch could be faster still, in variable time form. The cases we use this the result should virtually never be zero. You can terminate when n[0] is not 0 or the bits from P.
8. 
   sipa commented at 2:45 pm on December 12, 2014: contributor

   @peterdettman Nice, seems to give an extra 0.5% speedup.
9. 
   peterdettman commented at 10:22 am on December 13, 2014: contributor

   @gmaxwell Sure, good idea: https://github.com/peterdettman/secp256k1/commit/61ef8271587f9596e970cb37147d4af676b86b91

   I think we still need the high and low limbs, not sure if I’m missing something obvious.

10. sipa force-pushed on Dec 13, 2014
11. 
    sipa commented at 2:36 pm on December 13, 2014: contributor

    @peterdettman Awesome, another 0.2%. Cherry-picked your commits into this PR.
12. sipa cross-referenced this on Dec 14, 2014 from issue Use Co-Z arithmetic for precomputations by peterdettman
13. sipa force-pushed on Dec 16, 2014
14. 
    sipa commented at 10:31 pm on December 16, 2014: contributor

    Rebased after #123.
15. weak normalization 0295f0a33d
16. Weak normalization for secp256k1_fe_equal d7174edf5f
17. Add _fe_normalizes_to_zero method eed599dd72
18. Add _normalizes_to_zero_var variant 49ee0dbe16
19. sipa force-pushed on Dec 20, 2014
20. 
    sipa commented at 1:41 pm on December 20, 2014: contributor

    Rebased after #168.
21. 
    gmaxwell commented at 6:40 pm on December 22, 2014: contributor

    ACK.
22. sipa merged this on Dec 22, 2014
23. sipa closed this on Dec 22, 2014

    ---

24. sipa referenced this in commit d57cae9473 on Dec 22, 2014

Contributors
sipa peterdettman gmaxwell