Added Modular Inverse (keon#721)

c-utkarsh · web-flow · commit bc0b1d33aad8 · 2020-10-11T20:23:54.000-05:00
diff --git a/README.md b/README.md
@@ -210,6 +210,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
     - [is_strobogrammatic](algorithms/maths/is_strobogrammatic.py)
     - [modular_exponential](algorithms/maths/modular_exponential.py)
+    - [modular_inverse](algorithms/maths/modular_inverse.py)
     - [next_bigger](algorithms/maths/next_bigger.py)
     - [next_perfect_square](algorithms/maths/next_perfect_square.py)
     - [nth_digit](algorithms/maths/nth_digit.py)
diff --git a/algorithms/maths/modular_inverse.py b/algorithms/maths/modular_inverse.py
@@ -0,0 +1,34 @@
+# extended_gcd(a, b) modified from 
+# https://github.com/keon/algorithms/blob/master/algorithms/maths/extended_gcd.py 
+
+def extended_gcd(a: int, b: int) -> [int, int, int]:
+    """Extended GCD algorithm.
+    Return s, t, g
+    such that a * s + b * t = GCD(a, b)
+    and s and t are co-prime.
+    """
+
+    old_s, s = 1, 0
+    old_t, t = 0, 1
+    old_r, r = a, b
+    
+    while r != 0:
+        quotient = old_r // r
+        
+        old_r, r = r, old_r - quotient * r
+        old_s, s = s, old_s - quotient * s
+        old_t, t = t, old_t - quotient * t
+    
+    return old_s, old_t, old_r
+
+
+def modular_inverse(a: int, m: int) -> int:
+    """
+    Returns x such that a * x = 1 (mod m)
+    a and m must be coprime 
+    """
+
+    s, t, g = extended_gcd(a, m)
+    if g != 1:
+        raise ValueError("a and m must be coprime")
+    return s % m
diff --git a/tests/test_maths.py b/tests/test_maths.py
@@ -8,6 +8,7 @@
     gcd, lcm, trailing_zero, gcd_bit,
     gen_strobogrammatic, strobogrammatic_in_range,
     is_strobogrammatic, is_strobogrammatic2,
+    modular_inverse,
     modular_exponential,
     find_next_square, find_next_square2,
     prime_check,
@@ -166,6 +167,21 @@ def test_is_strobogrammatic2(self):
         self.assertFalse(is_strobogrammatic2("14"))
 
 
+class TestModularInverse(unittest.TestCase):
+    """[summary]
+    Test for the file modular_Exponential.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """    
+
+    def test_modular_inverse(self):
+        # checks if x * x_inv == 1 (mod m)
+        self.assertEqual(1, 2 * modular_inverse.modular_inverse(2, 19) % 19)
+        self.assertEqual(1, 53 * modular_inverse.modular_inverse(53, 91) % 91)
+        self.assertEqual(1, 2 * modular_inverse.modular_inverse(2, 1000000007) % 1000000007)
+        self.assertRaises(ValueError, modular_inverse.modular_inverse, 2, 20)
+
 class TestModularExponential(unittest.TestCase):
     """[summary]
     Test for the file modular_Exponential.py
