Python による左バイナリ法の実装

バイナリ法はべき乗を高速に計算するアルゴリズムである．

バイナリ法で を計算する際， を二進展開した結果を右から見る方法 (右バイナリ法) と左から見る方法 (左バイナリ法) がある． 以下では，Python による左バイナリ法の実装を紹介する．

def binary(a, k):
    """
    左バイナリ法
    :return: a ** k
    """
    check = 1 << max(0, k.bit_length() - 1)
    x = 1
    while check:
        x *= x
        if k & check:
            x *= a
        check >>= 1
    return x


def binary_mod(a, k, n):
    """
    左バイナリ法
    :return: a ** k % n
    """
    check = 1 << max(0, k.bit_length() - 1)
    x = 1
    while check:
        x = x * x % n
        if k & check:
            x = x * a % n
        check >>= 1
    return x


def ex_binary_mod(k1, k2, a1, a2, n):
    """
    拡張左バイナリ法
    :return: a1 ** k1 * a2 ** k2
    """
    check = 1 << max(0, max(k1, k2).bit_length() - 1)
    x = 1
    while check:
        x = x * x % n
        if k1 & check:
            x = x * a1 % n
        if k2 & check:
            x = x * a2 % n
        check >>= 1
    return x