基于Python的Montgomery乘法算法

Question

我在python3.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)

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

^{pr2}$

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

谢谢你的回答。在

Answer 1

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

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

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

你的情况就是这样

^{pr2}$

当你使用mod 41时，2^(-6)的解释是将mod 41乘以2的逆提升到6的幂，然后得到mod 41的结果。换句话说，2^-6 = (2^-1)^6。在

因为2*21=42=1（模数41），所以2^（-1）=21（模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，即代码返回的数字。 所以你的代码是正确的。如果产出和期望之间存在冲突，那么在这种情况下，问题可能是期望的问题。在