最快的算法來計算（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？

回答

相關問題