在Python中实现模幂的蒙哥马利梯子方法

Question

我正在尝试在 python 中实现用于模幂的 mongomery-ladder 方法，如下论文所示：

我的代码如下所示：

• 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

。