通过平方求幂

当我在寻找的时候通过平方求幂我在那里得到了递归方法，但后来我偶然发现了这个伪代码，我无法完全理解它。

function powermod(base, exponent, modulus) {
    if (base < 1 || exponent < 0 || modulus < 1)
        return -1

    result = 1;
    while (exponent > 0) {
       if ((exponent % 2) == 1) {
           result = (result * base) % modulus;
       }
       base = (base * base) % modulus;
       exponent = floor(exponent / 2);
    }
    return result;
} 

如果您能用简单的术语提供一些见解，那将会有很大的帮助

该代码依赖于以下事实：

x^y == (x*x)^(y/2)

该循环正是这样做的：将指数除以二，同时对底数进行平方。

一个例子：

让我们考虑计算 3^13 的结果。您可以将指数 (13) 写为二进制幂的和：3^(8+4+1). Then: 3^13 = 3^8 * 3^4 * 3^1.

这种二元幂的分解是由%2, /2使用上面解释的基本原理在代码中完成。

一步步：

你开始于3^13. As 13%2==1，将结果乘以3，因为答案does有一个因素3^1.

然后将指数除以 2 并计算底数的平方 (9^6 == 3^12). As 6%2==0，这意味着答案doesn't有一个因素3^2.

然后将指数除以 2 并计算底数的平方 (81^3 == 3^12). As 3%2==1，将结果乘以 81 因为答案does有一个因素3^4.

然后将指数除以 2 并计算底数的平方 (6561^1 == 3^8). As 1%2==1，将结果乘以 6561 因为答案does有一个因素3^8.