在MIT开放课件中解释这个Power Mod B^E Mod M bruteforce算法

Question

你能一步一步解释一下逻辑吗，我没有得到他们迭代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/electrice-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/mit6_006F11_ps5.pdf

Answer 1

它是Paul Hankin指出的用平方算法进行模幂运算。

我们首先迭代E中的每个字/字节(E[i]有8位，E是N字节长）

对于当前字节中的每个位，我们开始对字节中的位进行迭代，这是使用mask变量完成的，mask被初始设置为1，所以按位和E[1]的，0000001基本上检查字的最后一位(LSB)是否为1，每次迭代，我们通过简单地乘以2将mask左移。位=2掩码的ie为00000010，依此类推直到掩码变为100000000

如果E上的位为1，我们将X的当前值与结果相乘。

因此例如要计算B^(00000011)%M

我们只需计算((B%M)*(B^2)%M)%M