mk-mode BLOG

このブログは自作の自宅サーバに構築した Debian GNU/Linux で運用しています。
PC・サーバ構築等の話題を中心に公開しております。(クローンサイト: GitHub Pages

ブログ開設日2009-01-05
サーバ連続稼働時間
Reading...
Page View 合計
Reading...
今日
Reading...
昨日
Reading...

Python - べき剰余アルゴリズムの実装!

[ プログラミング, 数学 ] [ Python ]

こんにちは。

以前、 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 スクリプトの作成

まず、非再帰的な記述方法で作成。

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 メソッドの内容が異なるだけ)

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. 動作確認

1
2
3
4
5
$ ./modular_exponentiation_1.py
12345^6789 mod 4567 = 62

$ ./modular_exponentiation_2.py
12345^6789 mod 4567 = 62

6. 参考サイト


以上。

Comments