<分区>
我正在通过 Python 3 模拟用于公钥和私钥设置的 RSA 协议(protocol)，我必须处理巨大的指数。由于 pow(base,exp) 似乎没有在合理的时间内运行，我一直在尝试使用不同的算法，但目前似乎都没有用。
目前最有效的算法是什么？
<分区>
我正在通过 Python 3 模拟用于公钥和私钥设置的 RSA 协议(protocol)，我必须处理巨大的指数。由于 pow(base,exp) 似乎没有在合理的时间内运行，我一直在尝试使用不同的算法，但目前似乎都没有用。
目前最有效的算法是什么？
最佳答案
首先，您的标题的答案是未知。这个问题非常难，你可以阅读更多相关内容in this Wikipedia article .实际上几乎每个人都使用 exponentiation by squaring ，包括 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，但对于大指数要快得多。
最后，对于非常大的以固定模数为模的大量乘法计算，将数字置于蒙哥马利形式并使用 Montgomery reduction 可能是有益的.不过，这是更高级的数论，您不需要它。
关于python-3.x - 计算幂的最有效算法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58023976/