计算功率最有效的算法是什么？

Question

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

到目前为止，哪种算法是最有效的算法？

Answer 1

首先，你的标题的答案是未知的。这个问题非常困难，您可以在这篇维基百科文章中阅读更多相关信息。在实践中，几乎每个人都使用平方的幂，包括Python的算法。

但是，在RSA中，您使用模幂，我希望这就是您出错的地方。如果你计算pow(base, exp) % mod，那会很慢，因为中间的幂变得很大。诀窍是减少每一步的幂，这是允许的，因为a * b mod m == ((a mod m) * (b mod m)) mod m.这也已经在Python中实现了，通过使用三参数内置pow函数(不是math.pow，只是内置pow(：pow(base, exp, mod)。这个函数的结果等价于pow(base, exp) % mod，但对于大指数来说要快得多。

最后，对于非常大的计算，用大量乘法对固定模进行模化，将您的数字以蒙哥马利形式并使用蒙哥马利约简可能是有益的。不过，这是更高级的数字论，你不需要这个。

Answer 2

通过平方前一个二进制幂来计算基模 n 的二进制幂，例如 base^2=base

^1*base^1; base^4 = base^2*base^2通过二进制，我的意思是base^0，base^1，base^2，base^4，base^8等。

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

例如指数 9：基数^9 = 基数^1 * 基数^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;
}