python - Python上的蒙哥马利乘法算法

我在python 3.x上尝试了montgomery乘法算法，该算法伪代码如下：

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)

编写的Python3.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)

但是，代码没有给出正确的结果怎么了？
谢谢你的回答。

最佳答案

当我运行您的（修改的）代码时，我得到31，31似乎是正确的答案。
根据你的伪代码，R应该是

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

对你来说就是

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

当你使用mod 41时，对2^(-6)的解释是将mod41的乘法逆2提高到幂6，然后得到mod41的结果换句话说，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，即代码返回的数字。
因此您的代码是正确的如果产出和预期之间存在冲突，那么在这种情况下，问题可能在于预期。

关于python - Python上的蒙哥马利乘法算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42694912/