2

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?

posdef
  • 6,498
  • 11
  • 46
  • 94
sabari
  • 779
  • 2
  • 8
  • 14
  • 2
    This seems more like a math question. – Luchian Grigore Jul 12 '12 at 09:19
  • 1
    Try http://math.stackexchange.com/ – Luchian Grigore Jul 12 '12 at 09:19
  • Do you mean where b doesn't fit into 64 bits? The usual exponentiation algorithm has you accumulating a result by multiplying by a if the next bit of b is set and then squaring. This seems pretty easy for large b, it's large a and m that is hard. – tbroberg Jul 12 '12 at 09:35
  • Yes, and let us say b is a Fibonacci number, and a & m< 10^9. How can I find the (a^b)%m. Given that I am using log(n) matrix exponentiation algorithm for finding b. How should I used the intermediate b values? – sabari Jul 12 '12 at 09:39

1 Answers1

9

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

interjay
  • 107,303
  • 21
  • 270
  • 254
  • to nit-pick: this is only true if a and m are coprime. – Henrik Jul 12 '12 at 10:02
  • @Henrik: That means it will work even if m is prime and a < m. Correct me if I am wrong. – sabari Jul 12 '12 at 10:06
  • @Henrik: Right, I forgot about that, thanks. sabari: Yes, it will work in that case. – interjay Jul 12 '12 at 10:07
  • Carmichael's function is a generalization of Totient for non-coprime numbers. See my answer to the exact same question here http://stackoverflow.com/questions/11272437/calculating-abmod/11272606#11272606 – Viktor Latypov Jul 12 '12 at 18:16
  • @ViktorLatypov: I don't see how Carmichael's function helps, as it still requires `a` and `m` to be coprime. – interjay Jul 12 '12 at 22:53