Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit55877e7

Browse files
D-Sinuskeon
authored andcommitted
Add find order (keon#605)
* [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* [Delete] Left find_order algorithm only in this branch* [Add] Link to find_order algorithm in the README.md* [Add] Test cases for find_order_simple.py* [Edit] Modify pull request template* [Edit] Exclude mistyped one space in README.md* [Fix] Problems in test* [Edit] Function name in algorithm file and test file* [Edit] Function name in unittest file* [Edit] Function name in unittest file (2)* [Edit] Add module information into __init__.py* [Edit] Replace PULL_REQUEST_TEMPLATE.md file for resolving conflicts
1 parent74566a3 commit55877e7

File tree

4 files changed

+44
-1
lines changed

4 files changed

+44
-1
lines changed

‎README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -215,7 +215,8 @@ If you want to uninstall algorithms, it is as simple as:
215215
-[sqrt_precision_factor](algorithms/maths/sqrt_precision_factor.py)
216216
-[summing_digits](algorithms/maths/summing_digits.py)
217217
-[hailstone](algorithms/maths/hailstone.py)
218-
- [find_primitive_root](algorithms/maths/find_primitive_root_simple.py)
218+
- [find_order](algorithms/maths/find_order_simple.py)
219+
- [find_primitive_root](algorithms/maths/find_primitive_root_simple.py)
219220
-[matrix](algorithms/matrix)
220221
-[sudoku_validator](algorithms/matrix/sudoku_validator.py)
221222
-[bomb_enemy](algorithms/matrix/bomb_enemy.py)

‎algorithms/maths/__init__.py

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,4 +15,5 @@
1515
from .rsaimport*
1616
from .combinationimport*
1717
from .cosine_similarityimport*
18+
from .find_order_simpleimport*
1819
from .find_primitive_root_simpleimport*

‎algorithms/maths/find_order_simple.py

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
importmath
2+
3+
"""
4+
For positive integer n and given integer a that satisfies gcd(a, n) = 1,
5+
the order of a modulo n is the smallest positive integer k that satisfies
6+
pow (a, k) % n = 1. In other words, (a^k) ≡ 1 (mod n).
7+
Order of certain number may or may not be exist. If so, return -1.
8+
"""
9+
deffind_order(a,n):
10+
if ((a==1)& (n==1)):
11+
return1
12+
""" Exception Handeling :
13+
1 is the order of of 1 """
14+
else:
15+
if (math.gcd(a,n)!=1):
16+
print ("a and n should be relative prime!")
17+
return-1
18+
else:
19+
foriinrange(1,n):
20+
if (pow(a,i)%n==1):
21+
returni
22+
return-1
23+
24+
"""
25+
Time complexity only for calculating order = O(nlog(n))
26+
O(n) for iteration loop, O(log(n)) for built-in power function
27+
"""

‎tests/test_maths.py

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717
combination,combination_memo,
1818
hailstone,
1919
cosine_similarity,
20+
find_order,
2021
find_primitive_root,
2122
)
2223

@@ -339,6 +340,19 @@ def test_find_primitive_root_simple(self):
339340
self.assertListEqual([2,5,13,15,17,18,19,20,22,24,32,35],find_primitive_root(37))
340341

341342

343+
classTestFindOrder(unittest.TestCase):
344+
"""[summary]
345+
Test for the file find_order_simple.py
346+
347+
Arguments:
348+
unittest {[type]} -- [description]
349+
"""
350+
deftest_find_order_simple(self):
351+
self.assertEqual(1,find_order(1,1))
352+
self.assertEqual(6,find_order(3,7))
353+
self.assertEqual(-1,find_order(128,256))
354+
self.assertEqual(352,find_order(3,353))
355+
342356
if__name__=="__main__":
343357
unittest.main()
344358

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp