Python - べき剰余アルゴリズムの実装！
Updated:
こんにちは。
以前、 C++ や Ruby で「べき剰余」のアルゴリズムを実装しました。
今回は Python で実装してみました。
0. 前提条件
- LMDE 2 (Linux Mint Debian Edition 2; 64bit) での作業を想定。
- Python 3.6.4 での作業を想定。
- 当方は他のバージョンとの共存環境であり、
python3.6,pip3.6で 3.6 系を使用するようにしている。（適宜、置き換えて考えること）
1. べき剰余、べき剰余演算アルゴリズムについて
当ブログ過去記事を参照。
2. Python スクリプトの作成
まず、非再帰的な記述方法で作成。
File: modular_exponentiation_1.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#! /usr/local/bin/python3.6
"""
Modular Exponentiation (iterative)
"""
import sys
import traceback
class ModularExponentiation:
def comp_mod_exp(self, b, e, m):
""" Computation of modular exponentiation
:param int b: base
:param int e: exponent
:param int m: modulus
:return int me: modular expornentiation
"""
ans = 1
try:
while e > 0:
if (e & 1) == 1:
ans = (ans * b) % m
e >>= 1
b = (b * b) % m
return ans
except Exception as e:
raise
if __name__ == '__main__':
# me = b^e mod m
b, e, m = 12345, 6789, 4567
try:
obj = ModularExponentiation()
me = obj.comp_mod_exp(b, e, m)
print("{}^{} mod {} = {}".format(b, e, m, me))
except Exception as e:
traceback.print_exc()
sys.exit(1)
次に、再帰的な記述方法で作成。(comp_mod_exp メソッドの内容が異なるだけ）
File: modular_exponentiation_2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#! /usr/local/bin/python3.6
"""
Modular Exponentiation (recursive)
"""
import sys
import traceback
class ModularExponentiation:
def comp_mod_exp(self, b, e, m):
""" Computation of modular exponentiation
:param int b: base
:param int e: exponent
:param int m: modulus
:return int me: modular expornentiation
"""
try:
if e == 0:
return 1
ans = self.comp_mod_exp(b, e // 2, m)
ans = (ans * ans) % m
if e % 2 == 1:
ans = (ans * b) % m
return ans
except Exception as e:
raise
if __name__ == '__main__':
# me = b^e mod m
b, e, m = 12345, 6789, 4567
try:
obj = ModularExponentiation()
me = obj.comp_mod_exp(b, e, m)
print("{}^{} mod {} = {}".format(b, e, m, me))
except Exception as e:
traceback.print_exc()
sys.exit(1)
3. 動作確認
$ ./modular_exponentiation_1.py
12345^6789 mod 4567 = 62
$ ./modular_exponentiation_2.py
12345^6789 mod 4567 = 62
6. 参考サイト
以上。
Comments