Add find primitive root (keon#608)

* [Add] Find order algorithm and its supplemental * [Add] Find primitive root algorithm * [Edit] Add 'find_' in front of primitive root algorithm file * [Add/Fix] Supplemental & exception handling for the case n = 1 * [Fix] Exception handling for the case a == n == 1 in findOrder function * [Edit] Integrate find_order into find_primitive_root * [Edit] Include test cases * [Edit] Include information in readme files * [Fix] Delete misused square bracket * [Edit] Function naming convention / edit PULL_REQUEST_TEMPLATE for resolving collision
vdsmitnov52 · Dec 9, 2019 · 74566a3 · 74566a3
1 parent f8cae20
commit 74566a3
Show file tree

Hide file tree

Showing 4 changed files with 87 additions and 0 deletions.
diff --git a/README.md b/README.md
@@ -215,6 +215,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [sqrt_precision_factor](algorithms/maths/sqrt_precision_factor.py)
     - [summing_digits](algorithms/maths/summing_digits.py)
     - [hailstone](algorithms/maths/hailstone.py)
+	- [find_primitive_root](algorithms/maths/find_primitive_root_simple.py)
 - [matrix](algorithms/matrix)
     - [sudoku_validator](algorithms/matrix/sudoku_validator.py)
     - [bomb_enemy](algorithms/matrix/bomb_enemy.py)

diff --git a/algorithms/maths/__init__.py b/algorithms/maths/__init__.py
@@ -15,3 +15,4 @@
 from .rsa import *
 from .combination import *
 from .cosine_similarity import *
+from .find_primitive_root_simple import *
diff --git a/algorithms/maths/find_primitive_root_simple.py b/algorithms/maths/find_primitive_root_simple.py
@@ -0,0 +1,71 @@
+import math
+
+"""
+For positive integer n and given integer a that satisfies gcd(a, n) = 1,
+the order of a modulo n is the smallest positive integer k that satisfies
+pow (a, k) % n = 1. In other words, (a^k) ≡ 1 (mod n).
+Order of certain number may or may not be exist. If so, return -1.
+"""
+def find_order(a, n):
+    if ((a == 1) & (n == 1)):
+        return 1
+        """ Exception Handeling :
+        1 is the order of of 1 """
+    else:
+        if (math.gcd(a, n) != 1):
+            print ("a and n should be relative prime!")
+            return -1
+        else:
+            for i in range(1, n):
+                if (pow(a, i) % n == 1):
+                    return i
+            return -1
+
+"""
+Euler's totient function, also known as phi-function ϕ(n),
+counts the number of integers between 1 and n inclusive,
+which are coprime to n.
+(Two numbers are coprime if their greatest common divisor (GCD) equals 1).
+Code from /algorithms/maths/euler_totient.py, written by 'goswami-rahul'
+"""
+def euler_totient(n):
+    """Euler's totient function or Phi function.
+    Time Complexity: O(sqrt(n))."""
+    result = n;
+    for i in range(2, int(n ** 0.5) + 1):
+        if n % i == 0:
+            while n % i == 0:
+                n //= i
+            result -= result // i
+    if n > 1:
+        result -= result // n;
+    return result;
+
+"""
+For positive integer n and given integer a that satisfies gcd(a, n) = 1,
+a is the primitive root of n, if a's order k for n satisfies k = ϕ(n).
+Primitive roots of certain number may or may not be exist.
+If so, return empty list.
+"""
+
+def find_primitive_root(n):
+    if (n == 1):
+        return [0]
+        """ Exception Handeling :
+        0 is the only primitive root of 1 """
+    else:
+        phi = euler_totient(n)
+        p_root_list = []
+        """ It will return every primitive roots of n. """
+        for i in range (1, n):
+            if (math.gcd(i, n) != 1):
+                continue
+                """ To have order, a and n must be
+                relative prime with each other. """
+            else:
+                order = find_order(i, n)
+                if (order == phi):
+                    p_root_list.append(i)
+                else:
+                    continue
+        return p_root_list
diff --git a/tests/test_maths.py b/tests/test_maths.py
@@ -17,6 +17,7 @@
     combination, combination_memo,
     hailstone,
     cosine_similarity,
+    find_primitive_root,
 )
 
 import unittest
@@ -324,6 +325,19 @@ def test_cosine_similarity(self):
         self.assertAlmostEqual(cosine_similarity(vec_a, vec_b), -1)
         self.assertAlmostEqual(cosine_similarity(vec_a, vec_c), 0.4714045208)
 
+class TestFindPrimitiveRoot(unittest.TestCase):
+    """[summary]
+    Test for the file find_primitive_root_simple.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    def test_find_primitive_root_simple(self):
+        self.assertListEqual([0], find_primitive_root(1))
+        self.assertListEqual([2, 3], find_primitive_root(5))
+        self.assertListEqual([], find_primitive_root(24))
+        self.assertListEqual([2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35], find_primitive_root(37))
+
 
 if __name__ == "__main__":
     unittest.main()