如何在Python中处理非常高的指数？

Question

我正在使用Python实现RSA算法。当我输入像17和41这样的质数时，我的代码可以顺利运行，没有出现任何问题。但是，如果我尝试使用1000以上的质数，代码就会“停止”运行（我的意思是，它将在指数上卡住并且无法返回结果）。

问题出在以下部分：

msg = ''
msg = msg + (ord(char ** d) % n for char in array)

我知道对于类似于d = 32722667和char = 912673这样的数字执行指数运算需要大量计算，但是我想它不应该需要超过5到10分钟都没有返回结果。

我的电脑是i3-6006U，并且有4GB的RAM。

- Akari Oozora

---

计算的复杂度更多地取决于 n 而不是其他数字。例如，当 n = 1 时，很容易说出 947532598145 的 3452346277108 次方的结果 - 它将是 5（因为以 5 结尾的任何数字的任何幂次方都是 5）。 - Alex Sveshnikov

Answer 1

如果您对 x**y 的结果不感兴趣，而更关心 x**y%z 的结果，那么您可以使用内置函数 pow。可通过 help(pow) 查看相关信息：

Help on built-in function pow in module builtins:

pow(x, y, z=None, /)
    Equivalent to x**y (with two arguments) or x**y % z (with three arguments)

    Some types, such as ints, are able to use a more efficient algorithm when
    invoked using the three argument form.

- Daweo

---

这是一个不错的、合理的建议，但由于问题涉及运行时，我希望看到一些性能比较，以便知道这种方法是否真正改变了什么（从而回答了问题）。 - Tomerikoo

Answer 2

你想要做的是计算模幂。你不应该先计算指数的结果再计算取模的结果。有更高效的算法，你可以在维基百科上了解。在Python中，你可以使用内置的pow函数进行模幂运算，就像之前提到的那样。

- Alex G