Summarize currently implemented optimizations #747

1. 
   jonasnick commented at 8:55 AM on April 28, 2020: contributor

   Documenting the optimizations in this library would help the coming generations of contributors. A few things are already mentioned in the README's "Implementation details". Perhaps it would make sense to move everything outside the "General" item into a separate docs/implementation_details.md file and elaborate on the individual optimizations @sipa @apoelstra @gmaxwell @peterdettman

2. jonasnick added this to the milestone initial release on Apr 28, 2020
3. 
   real-or-random commented at 7:17 PM on December 2, 2020: contributor

   I think we should do this but this will require some effort, and I'm not sure how we should approach this.

   Maybe it's a good idea to come up with a list of items (some will be more like module documentation, some will be single optimizations and tricks) that we want to document. Then we can hopefully convince the original contributor to write some docs or find someone else.

   Does this sound good?

4. 
   apoelstra commented at 7:25 PM on December 2, 2020: contributor

   From me,

   • the ecmult_const WNAF code (though I just implemented a paper that gmax mentioned to me)
   • the in-place ecmult context generation which uses some dettman-style algebraic tricks to avoid ever needing a third fe per group element
5. 
   sipa commented at 7:31 PM on December 2, 2020: contributor

   Things that come to mind not currently listed in the README:

   • Exhaustive group tests (@apoelstra)
   • Pippenger's multiplication in addition to Strauss (@jonasnick)
   • Effective-affine trick in EC multiplication (@peterdettman)
   • Constant-time valgrind tests (@gmaxwell)
   • Proofs of our group laws/implementations (including the unified one, which is novel) in Sage (me)
   • Compile-time precomputed tables (unsure)

Contributors

jonasnickreal-or-randomapoelstrasipa

Milestone
stable release (1.0.0-rc.1)