0

我在 Python 3.x 上尝试蒙哥马利乘法算法。该算法伪代码如下：

Input: Modulus N(n bit), gcd(n, 2) = 1, Multipler: A (n bit), Multiplicant: B (n bit)
Output: R = (A x B x 2 ^ (-n)) mod N

R = 0

for (i = 0; i < n; i++)
{
    q = (R + A(i) * B) mod 2
    R = (R + A(i) * B + q * N) / 2
}

print(R)

编写的 Python 3.x 代码如下：

#!/usr/bin/python3

N = 41

A = 13

B = 17

n = N.bit_length()

R = 0

for i in range(0, n):
    q = int(R + (A & (1 << i) != 0) * B) % 2
    R = int((R + (A & (1 << i) != 0) * B + q * N) / 2)

print("Result:", R % N)

但是，代码没有给出正确的结果。问题是什么？

谢谢回答。

4

1 回答 1

1

当我运行您的（修改后的）代码时，我得到 31，而 31 似乎是正确的答案。

根据你的伪代码，R应该是

R = (A x B x 2 ^ (-n)) mod N

在你的情况下

R = (13*17*2^(-6))%41

工作时 mod 41的解释2^(-6)是将 2 的 mod 41 乘法倒数提高到 6 次方，然后取结果 mod 41。换句话说，2^-6 = (2^-1)^6。

因为 2*21 = 42 = 1 (mod 41)，所以 2^(-1) = 21 (mod 41)。因此：

R = (13*17*2^-6) (mod 41)
  = (13*17*(2^-1)^6) (mod 41)
  = (13*14*21^6) (mod 41) 
  = 18954312741 (mod 41)
  = 31

这表明结果是 31，即您的代码返回的数字。因此，您的代码是正确的。如果输出和期望之间存在冲突，那么在这种情况下，问题可能是期望之一。

于 2017-03-09T12:49:36.847 回答