如何实现模幂运算？ [英] How to implement modular exponentiation?

问题描述

我正在尝试计算如下内容：a ^ b mod c，其中所有三个数字都很大。

I am trying to calculate something like this: a^b mod c, where all three numbers are large.

我尝试过的事情：

1. Python的pow（）函数需要花费数小时，但尚未产生结果。 （如果有人可以告诉我它是如何实现的，将非常有帮助！）

1. Python's pow() function is taking hours and has yet to produce a result. (if someone could tell me how it's implemented that would be very helpful!)

我实现的从右到左的二进制方法，用O（log e）时间，大约需要30到40个小时（不想等待那么长时间）。

A right-to-left binary method that I implemented, with O(log e) time, would take about 30~40 hours (don't wanna wait that long).

各种递归方法都会产生细分错误（在我更改了递归限制）

Various recursion methods are producing segmentation faults (after I changed the recursion limits)

我可以进行任何优化吗？

Any optimizations I could make?

推荐答案

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

Python uses Karatsuba multiplication so the running time of multiplication is O(n^1.585). But division is still O(n^2).

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

For exponentiation, Python uses a left-to-right method with a 5-bit window. (It consumes 5 bits at once instead of just 1 bit. It does use more memory but will generally be faster.)

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

To get faster computations, you may want to look at gmpy2. It wraps the GMP multiple-precision library and will be faster. I ran a quick test and I think it will be ~100x faster.

免责声明：我维护gmpy2。

Disclaimer: I maintain gmpy2.

这篇关于如何实现模幂运算？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！