バイナリ法によるべき乗計算のPythonプログラム

バイナリ法

$x=a^k$のとき、$k$回の2乗計算が必要になるが、効率よく計算するためには、$a^{2^i}$を順次求めることで、計算量を$log(k)$回に抑えることができる。これがバイナリ法である。RSA暗号の複合時のべき乗計算などで用いられる。

具体例

$5^{21}$を計算する場合、以下のように展開する。

$5^{21}=5^{2^4}*5^{2^2}*5^{2^0}$

2進数に展開し、左から順に展開することにより計算を実行する。つまり、$21$の2進数表記である$10101$を使って以下のように計算する。

$5^{21} = 5^{(10101)_2} = 5^{(12^4 + 02^3 + 12^2 + 02^1 + 1*2^0)_2} = 5^{16} * 5^{4} * 5^{1}$

これにより、計算回数が大幅に削減される。

プログラム

以下は、Pythonでバイナリ法を用いたべき乗計算を行うプログラムである。

def binary_exponentiation(k: int, g: int, p: int) -> int:
    # 2進数表記に変換
    k_binary = []
    while k != 0:
        k_binary.append(k % 2)
        k = k // 2
        if k == 1:
            k_binary.append(k)
            k = 0
    
    # バイナリ法によるべき乗計算
    y = 1
    for i in reversed(range(len(k_binary))):
        if k_binary[i] == 1:
            y = (y * y % p) * g % p
        else:
            y = (y * y % p)
    
    return y

このプログラムでは、入力としてべき乗の指数$k$、底$g$、法$p$を受け取り、バイナリ法を用いてべき乗計算を行い、計算結果を返す。

• アルゴリズム