[演算法] b^n mod m 次方取模數 modular exponentiation algorithm

Python

def modular_exponentiation(base, n, mod):
    result = 1
    power = base % mod

    while n:
        if n & 1:
            result = (result * power) % mod
        n >>= 1
        power = (power ** 2) % mod

    return result

這個演算法可以快速求出 \( {base}^{n}\bmod m \) 的值,時間複雜度從 O(n) 變成 \(O(\log_{2}{n})\) ,大幅度減少運算時間。

用法: modular_exponentiation(base, n, mod)

Show Comments