Montgomery Multiplication Algorithm on Python

Question

I try Montgomery Multiplication Algorithm on Python 3.x. This algorithm pseudo-code is given below:

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 code that was written is given below:

#!/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)

But, the code isn't given correct result. What is the problem?

Thanks for answering.

Answer 1

When I run your (modified) code I get 31, and 31 appears to be the right answer.

According to your pseudocode, R should be

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

In your case that is

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

The interpretation of 2^(-6) when you are working mod 41 is to raise the mod 41 multiplicative inverse of 2 to the power 6, then take the result mod 41. In other words, 2^-6 = (2^-1)^6.

Since 2*21 = 42 = 1 (mod 41), 2^(-1) = 21 (mod 41). Thus:

R = (13*17*2^-6) (mod 41)
  = (13*17*(2^-1)^6) (mod 41)
  = (13*14*21^6) (mod 41) 
  = 18954312741 (mod 41)
  = 31

which shows that the result is 31, the number returned by your code. Thus your code is correct. If there is a clash between output and expectation, perhaps in this case the problem is one of expectation.