如何实现模幂代码

Question

拜托，我正在学习 算法导论（第 31 章第 957 页） 这本书，并遇到了这个伪代码。该伪代码是我们如何实现模幂运算的方法。伪代码如下

MODULAR-EXPONENTIATION(a,b,n)

1 c = 0

2 d = 1

3 let <b_k,b_(k-i),....b_0> be the binary representation of b

4 for i = k downto 0

5     c = 2c 

6     d = (d.d) mod n

7     if b_i == 1

8        c = c + 1

9        d = (d.a) mod n

10 return d

然后我尝试在python

中实现

def modExpn(a,b,n):
    c = 0
    d = 1
    binary_of_b = f'{b:b}'
    len_of_b = len(binary_of_b)
    for i in range(len_of_b,0,-1):
        val = i - 1
        c = 2 * c
        d = (d * d) %  n
        if binary_of_b[val] == '1':
            c = c + 1
            d = (d * a) % n
    return d

但是当我尝试运行 a = 7,b=560 和 n = 561 的函数 (modExpn) 时，我得到的输出是 415，但正确答案是 1。请问我哪里出错了？

Answer 1

您在将这些部分从伪代码转换为实际代码时搞砸了：

3 let <b_k,b_(k-i),....b_0> be the binary representation of b

4 for i = k **downto** 0

这些说明说你应该从二进制表示的 left-most 数字 (b_k) 迭代到 right-most (b_0) 因为你需要去从 k 下降到 0。例如，当您将 8 转换为二进制时，您会得到 "1000"，而在 Python 中， left-most 数字的索引将是 0 而不是 len("1000") - 1 正如你所做的那样。换句话说，如果你这样做：

for bin_digit in binary_of_b:

及以后：

if bin_digit == '1':

您的代码将起作用。

如何实现模幂代码

How to implement Modular Exponentiation Code

python

algorithm