algorithm - 计算 (a^(2^N))%m 的最快算法？

Question

有著名的密码学算法来计算模幂 (a^b)%c(例如此处的从右到左二进制方法:http://en.wikipedia.org/wiki/Modular_exponentiation)。

但是是否存在比“经典”算法更快地计算 (a^(2^N))%m 形式的模幂的算法？

非常感谢!

注意:

1) m 可以是一个非常大的素数……也可以不是(因此没有根据 m 进行优化)

2) N 可以大到 2^32-1 (N < 2^32)

Answer 1

如果 m 是质数，您可以更快地计算它。

您首先使用从右到左的二进制方法计算 p = 2^N % (m-1)。

然后你用从右到左的二进制方法计算a^p % m，由于Fermat's little theorem，它等于原来的表达式.

---

如果 m 不是素数，但足够小，可以分解它，您可以计算 Euler 的 totient 函数并使用 Euler's Theorem .

如果无法根据 m 进行优化，那么最好的办法可能是使用 Montgomery reduction .