Modular Exponentiation
c, exponentiation, modulus
Solution
According to Euler's theorem, if `a` and `m` are coprime:
` ab mod m = ab mod phi(m) mod m`
so if `b` is large, you can use the value `b % phi(m)` instead of `b`. `phi(m)` is Euler's totient function, which can be easily calculated if you know the prime factorization of `m`.
Once you've reduced the value of `b` in this way, use Exponentiation by squaring to compute the modular exponentiation in `O(log (b % phi(m)))`.
Problem
In C/C++ how can I calculate `(a^b)%m` where `b` does not fit into 64 bits? In other words, is there a way of calculating the above value using `b%m` instead of `b`? And is there any algorithm that can compute the above result in `O(log(b))` time or `O(log(b%m))` time?