计算（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)

- Vincent

---

你知道吗，Ronald L. Rivest的LCS35时光胶囊密码难题是基于这个问题设计的吗？而且选择这个问题是因为它本质上是一个串行计算。尽管它使用了(2^(2^N))%m的公式。 - Dan D.

请注意，如果您知道M的因数分解，您可以比指数运算更快地计算出答案。 - Dan D.

Answer 1

如果m是质数，你可以更快地计算这个。

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

然后使用从右到左的二进制方法计算 a^p % m，因为根据费马小定理，这个结果等于原来的表达式。

---

如果m不是质数，但足够小，可以分解m，并计算欧拉函数，使用欧拉定理。

如果没有依赖于m的优化，可能最好使用蒙哥马利约减。

- Evgeny Kluev

Answer 2

此外，针对Evgeny的回答，若你知道m的因式分解：m = p1 * p2 * ... * p{n}，你可以使用欧拉定理：

计算totient phi(m)= (p1-1)*(p2-1)*...*(p{n}-1)。

然后你可以计算p = 2^N % phi(m)并发现a^(2^N) % m = a^p % m。

不过这并没有使用2^N的特殊形式。

- Rasmus Faber

Answer 3

Evgeny和Rasmus给出了很好的答案。此外，记得使用连续平方算法来计算幂。也就是说，将指数（比如E）用二进制表示：

E = b0*1 + b1*2 + ... + bk*2^k

其中每个bi都是0或1，而bk = 1是最后一个非零位。然后，您可以通过以下方式将一个数字（例如N）提高到指数E：

N^E (mod m) = n0^b0 * n1^b1 * ... * nk^bk (mod m)

在哪里

n0 = N (mod m)
n1 = n0^2 (mod m)
n2 = n1^2 (mod m)
...
nk = n(k-1)^k (mod m)

例如，要计算28^27 mod 76，您需要N = 28，E = 27，m = 76，计算过程如下：

27 =  1 +  2 +  8 + 16
 E = b0 + b1 + b3 + b4

并且

n0 = 28 (mod 76) 
n1 = 28^2 (mod 76) = 24
n2 = 24^2 (mod 76) = 44
n3 = 44^2 (mod 76) = 36
n4 = 36^3 (mod 76) =  4

最后

28^27 (mod 76) = 28 * 24 * 36 *  4 (mod 76) = 20
 N^ E (mod  m) = n0 * n1 * n3 * n4 (mod 76)

- PengOne