I am trying to calculate something like this: a^b mod c, where all three numbers are large.
Things I've tried:
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!)
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 uses Karatsuba multiplication so the running time of multiplication is O(n^1.585). But division is still O(n^2).
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.)
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.
Disclaimer: I maintain gmpy2.