求 a^b^c^... mod m

我想计算一下：

a^bcd... mod m

你知道有什么有效的方法吗，因为这个数字太大了，但 a 、 b 、 c 、...和 ​​m 适合一个简单的 32 位 int 。

有任何想法吗？

Caveat: This question is different from finding a^b mod m.

Also please note that a^bc is not the same as (a^b)^c. The later is equal to a^bc. Exponentiation is right-associative.

a^bc mod m = a^{bc mod n} mod m, where n = φ(m) Euler's totient function http://en.wikipedia.org/wiki/Euler's_totient_function.

如果 m 是素数，则 n = m-1。

编辑：正如 Nabb 指出的，这仅在 a 与 m 互质时成立。所以你必须先检查一下。