Merge pull request #45 from manishrw/master

Added Modular multiplicative inverse algorithm
prakhar1989 · Oct 16, 2016 · 21945f6 · 21945f6
2 parents 691172d + 18a09aa
commit 21945f6
Show file tree

Hide file tree

Showing 3 changed files with 60 additions and 0 deletions.
diff --git a/README.md b/README.md
@@ -43,6 +43,7 @@ Completed
   - Parenthesis Matching
   - Infix to Postfix
 - Modular exponentiation
+- Modular multiplicative inverse
 
 
 Tests
@@ -54,3 +55,4 @@ Tests
     python -m tests.unionfind_test
     python -m tests.singly_linked_list_test
     python -m tests.modular_exponentiation_test
+    python -m tests.modular_multiplicative_inverse_test
diff --git a/misc/modular_multiplicative_inverse.py b/misc/modular_multiplicative_inverse.py
@@ -0,0 +1,42 @@
+"""
+Problem: https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
+"""
+import GCD as gcd
+
+def modular_multiplicative_inv(a, m):
+	if m == 1:
+		return 0
+	if m < 1:
+		raise ValueError('Modulus should be ve+ int > 0')
+	# check for co-prime condition
+	if gcd.greatest_common_divisor(a, m) != 1:
+		raise ValueError('a and m are not co-primes')
+
+	# Make var "a" positive if it's negative
+	if a < 0:
+		a %= m
+
+	# Initialise vars
+	m0 = m
+	x0 = 0
+	x1 = 1
+
+	while a > 1:
+		# Calculate quotient q; store m into temp t
+		q = a / m
+		t = m
+
+		# Calculate m as remainder(a, m); store temp t into a
+		m = a % m
+		a = t
+
+		# Assign x0 into temp t; Calculate x0 and store temp t into x1
+		t = x0
+		x0 = x1 - q * x0
+		x1 = t
+
+	# If x1 is negative then add modulus m0
+	if x1 < 0:
+		x1 += m0
+
+	return x1
diff --git a/tests/modular_multiplicative_inverse_test.py b/tests/modular_multiplicative_inverse_test.py
@@ -0,0 +1,16 @@
+import os, sys
+import unittest
+sys.path.append(os.path.join(os.getcwd(), os.path.pardir))
+from misc import modular_multiplicative_inverse as mmi
+
+class TestLCS(unittest.TestCase):
+    def test_modular_multiplicative_inverse(self):
+    	self.assertEqual(mmi.modular_multiplicative_inv(10, 7), 5)
+    	self.assertEqual(mmi.modular_multiplicative_inv(45, 13), 11)
+    	self.assertEqual(mmi.modular_multiplicative_inv(52, 1), 0)
+
+    	self.assertRaises(ValueError, mmi.modular_multiplicative_inv, 12, -1)
+    	self.assertRaises(ValueError, mmi.modular_multiplicative_inv, 12, 2)
+
+if __name__ == "__main__":
+    unittest.main()