몽고메리 곱셈 알고리즘 (Python)

Question

저는 몽고메리 곱셈 알고리즘을 파이썬 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) 

그러나 아래에 주어진다 작성되었습니다

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) 

파이썬 3.x의 코드 :이 알고리즘의 의사 코드는 아래와 같습니다. 문제가 무엇입니까?

답변 해 주셔서 감사합니다.

Answer 1

(수정 된) 코드를 실행하면 31이 나오는데 31이 올바른 대답 인 것 같습니다.

귀하의 의사에 따르면, R는 41 모드가의 모드 (41) 역수를 제기하는 것입니다 작업 할 때

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

2^(-6)의 해석을 당신의 경우

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

을해야한다 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이면, 코드에 의해 반환되는 숫자입니다. 코드가 정확합니다. 생산과 기대 사이에 충돌이있는 경우,이 경우에는 문제가 예상 중 하나 일 수 있습니다.