How to implement modular exponentiation?

Question

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

Things I've tried:

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!)

2. 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).

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

Any optimizations I could make?

Answer 1

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.

Answer 2

It sounds like you are trying to evaluate pow(a, b) % c. You should be using the 3-argument form, pow(a, b, c), which takes advantage of the fact that a * b mod c == a mod c * b mod c, which means you can reduce subproducts as they are computed while computing a ^ b, rather than having to do all the multiplications first.