从右到左二进制运算法则的解释？ [英] Explanation of right to left binary method of modular arithmetic?

问题描述

我一直在研究大量模数维基百科的链接，这是伪代码。

I have been studying this link from wikipedia of modulo of a large number, Here is the pseudocode.

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

I不理解wiki中给出的解释。为什么我必须检查exp％2是偶数还是奇数。还有为什么我要执行这三个操作？

I don't understand the explanation given in wiki.Why I have to check if exp%2 is even or odd. also why I am doing the three operations?

推荐答案

此算法是 平方求幂 算法和模运算。

This algorithm is a combination of the Exponentiation by Squaring algorithm and modulo arithmetic.

要了解正在发生的事情，请首先考虑指数是 2 的幂的情况。然后，假设 exponent = 2 ^ k ，则可以通过对结果 k 乘以平方，即

To understand what's going on, first consider a situation when exponent is a power of 2. Then, assuming that exponent = 2 ^ k, the result could be computed by squaring the result k times, i.e.

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

当指数不是 2 的幂时，我们需要进行附加乘法。事实证明，如果我们可以将指数除以2而没有余数，则可以对底进行平方，然后除以指数。但是，如果还有余数，则必须将中间结果乘以当前 base 的值。

When exponent is not a power of 2, we need to make additional multiplications. It turns out that if we can divide exponent by 2 without remainder, we can square the base, and divide the exponent. If, however, there is a remainder, we must additionally multiply the intermediate result by the value of the current base.

您看到的是通过求平方求模得到的平方乘幂。该算法使用指数>表示整数除以2。 1 操作，与 floor（exponent / 2）相同。

What you see is the same exponentiation by squaring applied to modulo multiplication. The algorithm denotes integer division by two using the exponent >> 1 operation, which is identical to floor(exponent / 2).

这篇关于从右到左二进制运算法则的解释？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！