diff options
Diffstat (limited to 'test/functional/test_framework/util.py')
-rw-r--r-- | test/functional/test_framework/util.py | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/test/functional/test_framework/util.py b/test/functional/test_framework/util.py index 6c8024c01c..af7f0b62f4 100644 --- a/test/functional/test_framework/util.py +++ b/test/functional/test_framework/util.py @@ -15,6 +15,7 @@ import os import random import re import time +import unittest from . import coverage from .authproxy import AuthServiceProxy, JSONRPCException @@ -625,3 +626,33 @@ def find_vout_for_address(node, txid, addr): if any([addr == a for a in tx["vout"][i]["scriptPubKey"]["addresses"]]): return i raise RuntimeError("Vout not found for address: txid=%s, addr=%s" % (txid, addr)) + +def modinv(a, n): + """Compute the modular inverse of a modulo n using the extended Euclidean + Algorithm. See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers. + """ + # TODO: Change to pow(a, -1, n) available in Python 3.8 + 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 + +class TestFrameworkUtil(unittest.TestCase): + def test_modinv(self): + test_vectors = [ + [7, 11], + [11, 29], + [90, 13], + [1891, 3797], + [6003722857, 77695236973], + ] + + for a, n in test_vectors: + self.assertEqual(modinv(a, n), pow(a, n-2, n)) |