More performant computation of the multiplicative inverse mod 2^n

[AlekseiVambol]

The Inverse method of the Modulus class can be optimized to become more performant. The current implementation uses the Euler's theorem, requires O(log^3(M)) time and O(log(M)) space, where the modulus M = 2^B:

tachyon/tachyon/math/finite_fields/modulus.h

Line 69 in bbbabd0

constexpr static T Inverse(const BigInt<N>& modulus) {

There are at least 2 methods, which can be used instead:

• Inversion by means of the Extended Euclidean Algorithm. It is a general purpose method for an arbitrary modulus. An example for small numbers with explanation and proof can be found here: https://github.com/taikoxyz/research/blob/main/algebra/Proof%20and%20Implementation%20of%20Euclidean%20Inversion.rs
• The Hurchalla's method for computing the multiplicative inverse modulo a power of two. The original Hurchalla's paper contains the explanation, proof and implementation in C for small numbers: https://arxiv.org/pdf/2204.04342 For the ones interested in theory I can give more straightforward non-inductive proof.

For large numbers (arbitrary-precision arithmetic) both methods would require O(log^2(M)) time and O(log(M)) space (for the first method it is a well-known result, for the Hurchalla's one I can give my proof sketch). However, the Hurchalla's method is more convenient to implement in this case, and I hypothesize that it can be a bit more time efficient.

PS The Hurchalla's method is extremely efficient for small numbers (no arbitrary-precision arithmetic): requires O(log log M) time, while Euler's/Carmichael theorem-based and Euclidean-based methods require O(log M) time. The space complexity for all these methods in the case of small numbers is O(1).