finding a^b^c^... mod m

user182513 picture user182513 · Nov 19, 2010 · Viewed 16.2k times · Source

I would like to calculate:

abcd... mod m

Do you know any efficient way since this number is too big but a , b , c , ... and m fit in a simple 32-bit int.

Any Ideas?


Caveat: This question is different from finding ab mod m.

Also please note that abc is not the same as (ab)c. The later is equal to abc. Exponentiation is right-associative.

Answer

Henrik picture Henrik · Nov 19, 2010

abc mod m = abc mod n mod m, where n = φ(m) Euler's totient function.

If m is prime, then n = m-1.

Edit: as Nabb pointed out, this only holds if a is coprime to m. So you would have to check this first.