如何实现模幂运算? [英] 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.
我尝试过的事情:
-
Python的pow()函数需要花费数小时,但尚未产生结果。 (如果有人可以告诉我它是如何实现的,将非常有帮助!)
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屋!