模数算术的右到左二进制方法的解释？

Question

我一直在研究这个来自大量模数的维基百科的链接,这是伪代码.

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

我不明白维基中给出的解释.为什么我要检查exp%2是偶数还是奇数.为什么我要做三个操作？

Answer 1

该算法是平方求幂算法和模运算的组合。

要了解发生了什么，首先考虑exponent的情况2。然后，假设exponent = 2 ^ k，结果可以通过结果k时间的平方来计算，即

res = (...((base ^ 2) ^2 ) ... ) ^2))
              ---------------------
                     k times

当exponent不是 的幂时2，我们需要进行额外的乘法。事实证明，如果我们能除以exponent2 而没有余数，我们就可以求底数的平方，然后除以指数。然而，如果有余数，我们还必须将中间结果乘以当前的值base。

您看到的是相同的平方乘幂应用于模乘法。该算法表示使用 运算将整数除以 2 exponent >> 1，与 相同floor(exponent / 2)。