Compute the modular inverse of a modulo n using the extended Euclidean Algorithm. See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers.
(a, n)
| 628 | raise RuntimeError("Vout not found for address: txid=%s, addr=%s" % (txid, addr)) |
| 629 | |
| 630 | def modinv(a, n): |
| 631 | """Compute the modular inverse of a modulo n using the extended Euclidean |
| 632 | Algorithm. See https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers. |
| 633 | """ |
| 634 | # TODO: Change to pow(a, -1, n) available in Python 3.8 |
| 635 | t1, t2 = 0, 1 |
| 636 | r1, r2 = n, a |
| 637 | while r2 != 0: |
| 638 | q = r1 // r2 |
| 639 | t1, t2 = t2, t1 - q * t2 |
| 640 | r1, r2 = r2, r1 - q * r2 |
| 641 | if r1 > 1: |
| 642 | return None |
| 643 | if t1 < 0: |
| 644 | t1 += n |
| 645 | return t1 |
| 646 | |
| 647 | class TestFrameworkUtil(unittest.TestCase): |
| 648 | def test_modinv(self): |
no outgoing calls