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?
According to Euler's theorem, if
a
andm
are coprime:ab mod m = ab mod phi(m) mod m
so if
b
is large, you can use the valueb % phi(m)
instead ofb
.phi(m)
is Euler's totient function, which can be easily calculated if you know the prime factorization ofm
.Once you've reduced the value of
b
in this way, use Exponentiation by squaring to compute the modular exponentiation inO(log (b % phi(m)))
.