MIT开放课件中解释这个PowerModB^EmodM的蛮力算法

Question

我在 MIT 的 6.006 课程中遇到这个算法来做 (B^E) mod 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

这里是link实际问题集

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

Answer 1

正如 Paul Hankin 所指出的，它是 mod平方算法的 ulo 求幂。

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

对于当前字节中的每一位，我们开始迭代字节中的位，这是使用 mask 变量完成的，mask 最初设置为 1，因此 E[1] 的按位与，0000001 基本上检查是否单词的最后一位（LSB）是 1 ，每次迭代，我们通过简单地乘以 2 将掩码向左移动。即对于 bit=2 掩码是 00000010 ，依此类推直到掩码变为 100000000

我们在 X 上保持平方（使用 modulo），因此对于 E 中的每一位，我们的 X 值为 B、B^2、B^4、B^8

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

例如计算 B ^ (00000011) % M

我们简单地计算 ((B % M) * (B ^ 2) % M) % M

MIT开放课件中解释这个PowerModB^EmodM的蛮力算法

Explain this Power Mod B ^ E mod M bruteforce algorithm in MIT open courseware

algorithm

integer

modulo