Safegcd-based modular inverses in MuHash3072
Summary:
This implements a safegcd-based modular inverse for MuHash3072. It is a fairly straightforward translation of the libsecp256k1 implementation, with the following changes:
Generic for 32-bit and 64-bit
Specialized for the specific MuHash3072 modulus (2^3072 - 1103717).
A bit more C++ish
Far fewer sanity checks
A benchmark is also included for MuHash3072::Finalize. The new implementation is around 100x faster on x86_64 for me (from 5.8 ms to 57 μs); for 32-bit code the factor is likely even larger.
For more information:
Original paper by Daniel J. Bernstein and Bo-Yin Yang
Implementation for libsecp256k1 by Peter Dettman; and the final version
Explanation of the algorithm using Python snippets
Analysis of the maximum number of iterations the algorithm needs
Formal proof in Coq by Russell O'Connor (for the 256-bit version of the algorithm; here we use a 3072-bit one).Backport of core#21590.
This dramatically improves the performance of the coinstatsindex. This is especially visible when running the feature_assumeutxo test under debug (from 43s to 11s on my machine).
The Finalize benchmark is also 100x faster on my machine with this implementation.
Note that the code has been very slightly massaged to avoid using C++20 functions.
Test Plan:
ninja bitcoin-bench ninja bitcoin-fuzzers ninja all check-all
Reviewers: #bitcoin_abc, PiRK
Reviewed By: #bitcoin_abc, PiRK
Subscribers: PiRK
Differential Revision: https://reviews.bitcoinabc.org/D17964