Алгоритм умножения Монтгомери на Python

Question

Я пытаюсь Алгоритм умножения Монтгомери на 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)

Но код не дает правильного результата. В чем проблема?

Спасибо за ответы.

Answer 1

Когда я запускаю ваш (модифицированный) код, я получаю 31, и 31 кажется правильным ответом.

Согласно вашему псевдокоду, R должно быть

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

В вашем случае это

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

Интерпретация 2^(-6) когда вы работаете с модом 41, нужно поднять мультипликативное обратное значение мод 41 от 2 до степени 6, а затем взять результат мод 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, число, возвращаемое вашим кодом. Таким образом, ваш код правильный. Если между результатом и ожиданием есть конфликт, возможно, в этом случае проблема заключается в ожидании.