Thread: Calculate hugh mod

Hi,

How would one do to calculate something like a^b mod m where 0<a,b,m<10000?

Is there an efficient algorithm do to this? I have heard (and think I understand it) that the Euler totient (phi)-function can be used, but I'm not quite sure how.

And if we go one step further, and want to know a^b^c mod m, 0 < a,b,c,m < 10000, can we use some kind of recursive formula?

Thanks!
Alex

Originally Posted by faximan

Hi,

How would one do to calculate something like a^b mod m where 0<a,b,m<10000?

Is there an efficient algorithm do to this? I have heard (and think I understand it) that the Euler totient (phi)-function can be used, but I'm not quite sure how.

And if we go one step further, and want to know a^b^c mod m, 0 < a,b,c,m < 10000, can we use some kind of recursive formula?

Thanks!
Alex

In the event that gcd(a,m) = 1, you can reduce b mod phi(m), for example because and and .

Often for a powermod calculation it's fast enough to compute by squaring while considering the exponent in binary. I explain it here (post #7).

http://www.mathhelpforum.com/math-he...tml#post508102

You might also like to compare with this Wikipedia article, which I found a bit hard to follow the last time I read it.

Modular exponentiation - Wikipedia, the free encyclopedia

For power towers, see this example (involving both totient and CRT - Chinese Remainder Theorem)

http://www.mathhelpforum.com/math-he...on-150486.html