Add chinese remainder theorem (keon#759)

mans-andersson · web-flow · commit 8f6e5f0aa54f · 2021-03-11T15:54:07.000-08:00
* feat: Add basic ch. remainder theorem algorithm

* feat: Add all n coprime check

Co-authored-by: Lazar Cerovic&lt;lazarc@kth.se&gt;

* Add gcd function

* Add list length &gt; 0 check

* doc: Improve function documentation

* feat: add all divisors need to be &gt; 1

* test: Add test cases for crt solver

* fix: make check_coprime private

* fix: Change to python3.7 type hints

* refactor: Move ch. remainder theorem tests to test_maths

* Add link in README

* Remove unnecessary whitespace and add newline at end of file

* docs: Fix README alphabetic order
diff --git a/README.md b/README.md
@@ -200,6 +200,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [is_anagram](algorithms/map/is_anagram.py)
 - [maths](algorithms/maths)
     - [base_conversion](algorithms/maths/base_conversion.py)
+    - [chinese_remainder_theorem](algorithms/maths/chinese_remainder_theorem.py)
     - [combination](algorithms/maths/combination.py)
     - [cosine_similarity](algorithms/maths/cosine_similarity.py)
     - [decimal_to_binary_ip](algorithms/maths/decimal_to_binary_ip.py)
diff --git a/algorithms/maths/chinese_remainder_theorem.py b/algorithms/maths/chinese_remainder_theorem.py
@@ -0,0 +1,46 @@
+from algorithms.maths.gcd import gcd
+from typing import List
+
+def solve_chinese_remainder(num : List[int], rem : List[int]):
+    """
+    Computes the smallest x that satisfies the chinese remainder theorem
+    for a system of equations.
+    The system of equations has the form:
+    x % num[0] = rem[0]
+    x % num[1] = rem[1]
+    ...
+    x % num[k - 1] = rem[k - 1]
+    Where k is the number of elements in num and rem, k > 0.
+    All numbers in num needs to be pariwise coprime otherwise an exception is raised
+    returns x: the smallest value for x that satisfies the system of equations
+    """
+    if not len(num) == len(rem):
+        raise Exception("num and rem should have equal length")
+    if not len(num) > 0:
+        raise Exception("Lists num and rem need to contain at least one element")
+    for n in num:
+        if not n > 1:
+            raise Exception("All numbers in num needs to be > 1")
+    if not _check_coprime(num):
+        raise Exception("All pairs of numbers in num are not coprime")
+    k = len(num)
+    x = 1
+    while True:
+        i = 0
+        while i < k:
+            if x % num[i] != rem[i]:
+                break
+            i += 1
+        if i == k:
+            return x
+        else:
+            x += 1
+
+def _check_coprime(l : List[int]):
+    for i in range(len(l)):
+        for j in range(len(l)):
+            if i == j:
+                continue
+            if gcd(l[i], l[j]) != 1:
+                return False
+    return True
diff --git a/tests/test_maths.py b/tests/test_maths.py
@@ -25,7 +25,8 @@
     alice_private_key, alice_public_key, bob_private_key, bob_public_key, alice_shared_key, bob_shared_key, diffie_hellman_key_exchange,
     num_digits,
     alice_private_key, alice_public_key, bob_private_key, bob_public_key, alice_shared_key, bob_shared_key,
-    diffie_hellman_key_exchange, krishnamurthy_number
+    diffie_hellman_key_exchange, krishnamurthy_number,
+    chinese_remainder_theorem,
 )
 
 import unittest
@@ -496,6 +497,36 @@ def test_num_digits(self):
         self.assertEqual(1,num_digits(-5))
         self.assertEqual(3,num_digits(-254))
 
+class TestChineseRemainderSolver(unittest.TestCase):
+    def test_k_three(self):
+        # Example which should give the answer 143
+        # which is the smallest possible x that
+        # solves the system of equations
+        num = [3, 7, 10]
+        rem = [2, 3, 3]
+        self.assertEqual(chinese_remainder_theorem.solve_chinese_remainder(num, rem), 143)
+
+    def test_k_five(self):
+        # Example which should give the answer 3383
+        # which is the smallest possible x that
+        # solves the system of equations
+        num = [3, 5, 7, 11, 26]
+        rem = [2, 3, 2, 6, 3]
+        self.assertEqual(chinese_remainder_theorem.solve_chinese_remainder(num, rem), 3383)
+
+    def test_exception_non_coprime(self):
+        # There should be an exception when all
+        # numbers in num are not pairwise coprime
+        num = [3, 7, 10, 14]
+        rem = [2, 3, 3, 1]
+        with self.assertRaises(Exception):
+            chinese_remainder_theorem.solve_chinese_remainder(num, rem)
+
+    def test_empty_lists(self):
+        num = []
+        rem = []
+        with self.assertRaises(Exception):
+            chinese_remainder_theorem.solve_chinese_remainder(num, rem)
 
 if __name__ == "__main__":
     unittest.main()
