I want to calculate a^b%m where a,b and m are very large number like 2^256 or 2^512 bit. As far I know some method called bigmod or powmod which calculate a^b%m in O(log m) time complexity but as the number is huge we need to implement it using BigIntegers. Which is slower than normal arithmetic operation. So for this job I have implemented my own Biginteger library and implemented a O(log m) algorithm to calculate a^b%m. But it is using minimum 7-8 seconds to execute where python pow(a,b,m) function is working in less than 1 second. So I want to know the details about the algorithm which is used to implement pow(a,b,m).
Asked
Active
Viewed 69 times
0
President James K. Polk
- 40,516
- 21
- 95
- 125
Tanmoy Datta
- 1,604
- 1
- 17
- 15
-
1BigIntegers are not a thing in Python. Regular integers will do just fine. What is your question? – roganjosh Dec 23 '18 at 00:17
-
4All of CPython is available of github for you to view – roganjosh Dec 23 '18 at 00:18
-
See: https://stackoverflow.com/questions/5246856/how-did-python-implement-the-built-in-function-pow – robert Dec 23 '18 at 00:25