python - 如何实现模幂运算？

Question

我试图计算这样的东西：a^b mod c，所有三个数字都很大。

我尝试过的事情：

1. Python 的 pow() 函数需要几个小时，但尚未产生结果。（如果有人能告诉我它是如何实现的，那将非常有帮助！）

2. 我用 O(log e) 时间实现的从右到左的二进制方法大约需要 30~40 小时（不想等那么久）。

3. 各种递归方法正在产生分段错误（在我更改了递归限制之后）

我可以做任何优化吗？

Answer 1

听起来您正在尝试评估pow(a, b) % c. 您应该使用 3 参数形式 ，pow(a, b, c)它利用了这一事实a * b mod c == a mod c * b mod c，这意味着您可以在计算 时减少子a ^ b积，而不必先进行所有乘法运算。

Answer 2

Python 使用 Karatsuba 乘法，因此乘法的运行时间为 O(n^1.585)。但除法仍然是 O(n^2)。

对于求幂，Python 使用从左到右的方法和 5 位窗口。（它一次消耗 5 位而不是 1 位。它确实使用更多内存，但通常会更快。）

要获得更快的计算，您可能需要查看gmpy2。它包装了GMP多精度库，并且会更快。我进行了快速测试，我认为它会快 100 倍左右。

免责声明：我维护 gmpy2。