Python上的蒙哥馬利乘法算法

我在Python 3.x上嘗試蒙哥馬利乘法算法。這是寫在下面給出Python上的蒙哥馬利乘法算法

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)

但是，代碼沒有給出正確的結果。問題是什麼？

感謝您的回答。

來源

2017-03-09 Ercan Ersoy

它給了什麼結果？你期待什麼結果？ –

該代碼是給結果12 –

的代碼是給12，但你期待什麼號碼？ –

當我運行你的（修改過的）代碼時，我得到了31，而31似乎是正確的答案。

根據你的僞代碼，R應

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

在你的情況是

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

的2^(-6)的解釋，當你正在國防部41是提高國防部41乘法逆2來電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-09 12:49:36

對不起，n應該是6.我改變了我的問題的n變量的值。 –

Python上的蒙哥馬利乘法算法

回答

相關問題