快速模幂函数的实现

Question

我试图实现函数快速模幂（b，k，m），它计算：
b^（2k）mod m只使用大约2k模乘。在

我试过这个方法：

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

更新：我终于明白，您不需要常规的modular exponentiation（即b^k mod m），而是{}（正如您所明确指出的）。在

使用常规的内置Python函数^{}这将是：

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

或者，不使用pow：

^{pr2}$

如果你知道r = phi(m)（Euler's totient function），你可以先减少指数：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(4, 13, 497)
# 445