Repository: keon/algorithms
Pull request #608 (2019-12-05 07:50:53)

Add find primitive root
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [X] **If creating a new file :**
  - [X] added links to it in the README files ?
  - [X] included tests with it ?
  - [X] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**


D-Sinus: To find primitive root, Euler's totient function is used.
At first I think I need to implement that function by myself,
but 'goswami-rahul' already implemented that function.
So I copy his/her code and write comment about that (this is not my code)
Would it be allowed? If not, I'll delete that part and re-implement that function by myself.
Please let me know. Thanks.

Patch:
diff --git a/README.md b/README.md
index f288ee3..eff0d16 100644
--- 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
index 7028a0a..d83cfb0 100644
--- a/algorithms/maths/__init__.py
+++ b/algorithms/maths/__init__.py
@@ -15,3 +15,4 @@ from .rabin_miller import *
 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
new file mode 100644
index 0000000..a5b74f6
--- /dev/null
+++ 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


Test patch:
diff --git a/tests/test_maths.py b/tests/test_maths.py
index 86b61e0..5476447 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -17,6 +17,7 @@ from algorithms.maths import (
     combination, combination_memo,
     hailstone,
     cosine_similarity,
+    find_primitive_root,
 )
 
 import unittest
@@ -324,6 +325,19 @@ class TestCosineSimilarity(unittest.TestCase):
         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()