python - 在Python中实现模幂的蒙哥马利阶梯法

Question

我正在尝试在 python 中实现 RSA 模幂的 mongomery-ladder 方法(因此 N=p•q，p,q 是素数)，如下 paper 所示:

我的代码如下所示:

• x 代表底数，k 代表指数，N 代表模

# uses montgomery-ladder method for modular exponentiation
def montgomery_ladder(x, k, N):
    x %= N
    k %= N
    # getting the binary representation of k
    bin_k = list(map(int, bin(k)[2:]))
    # Initialize two variables to hold the intermediate results
    r0 = 1
    r1 = x

    # Loop through each bit of the binary exponent from most significant to the least significant
    for i in range(len(bin_k)):
        if bin_k[i] == 0:
            r1 = (r1 * r0) % N
            r0 = (r0 ** 2) % N
        else:
            r0 = (r0 * r1) % N
            r1 = (r1 ** 2) % N

    # The final result is in r0
    return r0

它不适用于非常大的数字，例如以下测试:

def main():
    x = 412432421343242134234233
    k = 62243535235312321213254235
    N = 10423451524353243462
    print(montgomery_ladder(x, k, N))
    print(pow(x, k, N))


if __name__ == '__main__':
    main()

产量:

7564492758006795519
179467895766154563

pow(x, k, n) 返回正确的答案，但我的函数没有返回正确的答案。 有什么想法吗？

Answer 1

删除开头的k %= N。