Merge #19105: Add Muhash3072 implementation in Python

36ec9801a4edb9663ef9ce9ad298233766b903e8 test: Add chacha20 test vectors in muhash (Fabian Jahr)
0e2b400fea890e769b75da5b55fa1902fd9f9851 test: Add basic Python/C++ Muhash implementation parity unit test (Fabian Jahr)
b85543cb7361d6ba27c0eeca756eec9fd5395b36 test: Add Python MuHash3072 implementation to test framework (Pieter Wuille)
ab30cece0e84a8b917cb9a219c2466574362f300 test: Move modinv to util and add unit test (Fabian Jahr)

Pull request description:

  This is the second in a [series of pull requests](https://github.com/bitcoin/bitcoin/pull/18000) to implement an Index for UTXO set statistics.

  This pull request adds a Python implementation of Muhash3072, a homomorphic hashing algorithm to be used for hashing the UTXO set. The Python implementation can then be used to compare behavior with the C++ version.

ACKs for top commit:
  jnewbery:
    utACK 36ec9801a
  laanwj:
    Code review ACK 36ec9801a4edb9663ef9ce9ad298233766b903e8

Tree-SHA512: a3519c6e11031174f1ae71ecd8bcc7f3be42d7fc9c84c77f2fbea7cfc5ad54fcbe10b55116ad8d9a52ac5d675640eefed3bf260c58a02f2bf3bc0d8ec208baa6

1 files changed, 1 insertions, 16 deletions

diff --git a/test/functional/test_framework/key.py b/test/functional/test_framework/key.py
index 912c0ca978..adbffb7dc7 100644
--- a/test/functional/test_framework/key.py
+++ b/test/functional/test_framework/key.py
@@ -8,22 +8,7 @@ keys, and is trivially vulnerable to side channel attacks. Do not use for
 anything but tests."""
 import random
 
-def modinv(a, n):
-    """Compute the modular inverse of a modulo n
-
-    See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers.
-    """
-    t1, t2 = 0, 1
-    r1, r2 = n, a
-    while r2 != 0:
-        q = r1 // r2
-        t1, t2 = t2, t1 - q * t2
-        r1, r2 = r2, r1 - q * r2
-    if r1 > 1:
-        return None
-    if t1 < 0:
-        t1 += n
-    return t1
+from .util import modinv
 
 def jacobi_symbol(n, k):
     """Compute the Jacobi symbol of n modulo k