最快的算法来计算（a ^（2^N））％m？

有一些众所周知的密码学算法来计算模幂（a^b）％c（例如这里从右到左的二进制方法：http://en.wikipedia.org/wiki/Modular_exponentiation）。最快的算法来计算（a ^（2^N））％m？

但是，算法是否存在以比“经典”算法快的方式计算形式（a ^（2^N））％m的模幂运算？

非常感谢！

注：

1）M可以是一个非常大的质...或者没有（那么取决于M没有优化）

2）N可以是一样大2^32-1（ N < 2^32）

2012-03-22 Vincent

你知道，罗纳德L.维斯特的[LCS35 Time Capsule的加密益智]（http://www.google.com/search?q=LCS35+Time+Capsule + Crypto-Puzzle）是基于这个问题？而且选择这个问题是因为它是一个固有的连续计算。虽然它使用'（2 ^（2^N））％m'。 – 2012-03-22 07:46:09

请注意，如果您知道M的因式分解，则可以比求幂计算出更快的答案。 – 2012-03-22 07:57:19

如果m是素数，那么可以更快地计算它。

您从右到左的二进制方法开始计算p = 2 ^N％（m-1）。

然后，您使用从右到左的二进制方法来计算^p％m，因为Fermat's little theorem，这等于原始表达式。

如果m不是素数，但足够小，以便它可以被分解，可以计算欧拉函数，并使用Euler's Theorem。

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

来源

2012-03-22 08:33:58

此外，作为推广到叶夫根的回答是：如果你知道m的分解：m = p1 * p2 * ... * p{n}，您可以使用Euler's theorem：

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

然后你可以计算p = 2^N % phi(m)并找到那个a^(2^N) % m = a^p % m。

但是，这些都不使用特殊形式的2^N。

来源

2012-03-22 09:12:28

Evgeny和Rasmus给出了很好的答案。为了补充一点，请记住为权力使用连续的平方。也就是说，写了指数，说E，在基地2：

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

每个bi要么0或1和bk = 1是最后一个非零位。然后，你可以通过

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

养一些，说N，在指数E其中

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

and

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)

来源

2012-03-22 16:49:14 PengOne

最快的算法来计算（a ^（2^N））％m？

回答

相关问题