计算幂的最有效算法是什么？

Question

我正在模拟 public 的 RSA 协议和通过 Python 设置的私钥 3 我必须处理巨大的指数。由于 pow(base,exp) 似乎没有在合理的时间内运行我一直在尝试使用不同的算法，但现在 none 似乎有效。

目前最有效的算法是什么？

Answer 1

通过对前一个二进制幂求平方来计算基模 n 的二进制幂，例如基数^2=基数^1*基数^1；基数^4 = 基数^2*基数^2

我所说的二进制是指 base^0、base^1、base^2、base^4、base^8 等

然后在指数中设置该位时乘以二进制幂。

例如指数 9：base^9 = base^1 * base^8。所有计算均以模 n.

完成

找到附加的伪代码；我希望它是正确的，因为它未经测试；

//pseudocode
function myPower(base, exponent, n) {
    power = 1;
    binarypower = base;
    while(exponent>0) {
        if(exponent&1 != 0) {
            power = (binarypower * power) %n;
        }
        exponent = exponent>>1;
        if(exponent>0) {
            binarypower = (binarypower*binarypower)%n;
        }
    }
    return power;
}

Answer 2

首先，您的标题的答案是未知。这个问题非常难，你可以阅读更多关于它的内容in this Wikipedia article. In practice almost everyone uses exponentiation by squaring，包括Python的算法。

但是在 RSA 中，您使用模幂，我想这就是您出错的地方。如果您计算 pow(base, exp) % mod，那将非常慢，因为中间指数会变得很大。诀窍是减少每一步的指数，这是允许的，因为 a * b mod m == ((a mod m) * (b mod m)) mod m。这也已经在 Python 中通过使用 three-argument built-in pow 函数（即 not math.pow 实现, 只是内置 pow): pow(base, exp, mod).此函数的结果等同于 pow(base, exp) % mod，但对于大指数来说要快得多。

最后，对于非常大的计算，对固定模数进行大量乘法运算，将数字置于蒙哥马利形式并使用 Montgomery reduction 可能会有所帮助。不过，这是更高级的数论，您不需要它。

计算幂的最有效算法是什么？

What's the most efficient algorithm to compute powers?

exponentiation

python-3.x