algorithm - 模运算的从右到左二进制方法的解释？

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

我不明白 wiki 中给出的解释。为什么我必须检查 exp%2 是偶数还是奇数。还有我为什么要做这三个操作？

Answer 1

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

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

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

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

您所看到的是通过平方应用于模乘法的相同求幂。exponent >> 1该算法使用与相同的操作表示整数除以 2 floor(exponent / 2)。