解釋MIT開放課件此光焦度MOD乙^ E模m暴力破解算法

我碰到這個算法做的（B^E）MOD M在麻省理工學院的6.006當然，解釋MIT開放課件此光焦度MOD乙^ E模m暴力破解算法

你能一步解釋邏輯的步驟，我沒有得到這個角色，他們重複1至8

POWMOD(B, E, M, N) 
1 R = ONE(N) // result 
2 X = COPY(B, N) // multiplier 
3 for i = 1 to N 
4  mask = 1 
5  for bit = 1 to 8 
6   if E[i] & mask != 0 
7    R = MOD(MULTIPLY(R, X, N), M, 2N) 
8   X = MOD(MULTIPLY(X, X, N), M, 2N) 
9   mask = LSB(mask · 2) 
10 return R

這裏是鏈接到實際問題集

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps5.pdf

來源

2016-05-07 laughingman

你明白'B'和'E'是什麼，它們是如何在內存中表示的？一旦你得到了，算法是「平方指數」，這是解釋在這裏：http://stackoverflow.com/questions/30694842/exponentiation-by-squaring –

謝謝，我知道它是如何工作後，想一想，我實際上被掩碼弄糊塗了，現在我明白它用於檢查單詞E [i]的每個位不是零。 – laughingman

這是模冪的平方算法由Paul Hankin指出。

我們首先遍歷在E各自的字/字節（E [I]具有8個比特，以及E是N個字節長）

對於當前字節的每個比特，我們開始迭代上在字節中的位，這是使用掩碼變量完成的，掩碼被初始設置爲1，因此E [1]，0000001的按位AND基本上檢查該字的最後一位（LSB）是1，每次迭代，我們通過簡單地相乘2.對於位= 2掩碼爲00000010，依此類推直到掩碼變爲100000000

我們在X上保持平方（模），所以對於E中的每一位，我們都有X值爲B，B^2，B^4，B^8

我們乘保持（與國防部）X的當前值與結果，如果在E中的位爲1

因此，例如，計算乙^（00000011），％M

我們簡單計算（（B％ M）*（B^2）％M）％M

來源

2016-05-09 15:26:13 laughingman

解釋MIT開放課件此光焦度MOD乙^ E模m暴力破解算法

回答

相關問題