Монтгомери Умножение

Question

Я хочу решить модульный продукт с использованием умножения Монтгомери.

Что-то вроде этого:

a * a mod m

Например, а = 3567730065637 м = 5524112124451

a * a mod m -> 12728697821250192328215769 % 5524112124451 = 822276999119

Если я сделаю сокращение Монтгомери, я получу неправильный результат (3692678398982). Что я должен сделать, чтобы получить правильный результат?

N = 5524112124451

A = 3567730065637

B = 3567730065637

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)