实现功能快速模块化求幂

Question

我正在尝试实现快速模块化幂（b，k，m）的功能，该功能仅使用大约2k模块化乘法来计算b ^{（2 k）} mod m 。

我尝试了这个：

def FastModularExponentiation(b, k, m):
    res = 1
    b = b % m
    while (k > 0):
        if ((k & 1) == 1):
            res = (res * b) % m
        k = k >> 1
        b = (b * b) % m
    return res

但是我仍然遇到相同的问题，即如果我尝试b = 2，k = 1，m = 10，我的代码将返回22。但是，正确的答案是：

2 ^（2 ^ 1）mod 10 = 2 ^ 2 mod 10 = 4

我找不到原因。

Answer 1

更新：我终于明白您不想要常规的模幂运算（即b^k mod m），但是b^(2^k) mod m（正如您明确说明的那样）。

使用常规的内置 Python 函数，pow这将是：

def FastModularExponentiation(b, k, m):
    return pow(b, pow(2, k), m)

或者，不使用pow：

def FastModularExponentiation(b, k, m):
    b %= m
    for _ in range(k):
        b = b ** 2 % m
    return b

如果你知道r = phi(m)（欧拉的 totient 函数），你可以先减少指数：exp = pow(2, k, r)然后计算pow(b, exp, m)。根据输入值，这可能会加快速度。

（这是我以为你想要的原始答案，b^k mod m）

这对我有用：

def fast_mod_exp(b, exp, m):
    res = 1
    while exp > 1:
        if exp & 1:
            res = (res * b) % m
        b = b ** 2 % m
        exp >>= 1
    return (b * res) % m

我发现的唯一显着差异是在最后一行：return (b * res) % m并且我的while循环更早终止：（while exp > 1这应该与您所做的相同 - 除了它节省了不必要的平方运算）。

另请注意，内置函数pow将免费执行所有操作（如果您提供第三个参数）：

pow(4, 13, 497)
# 445