Python Montgomery 模幂算法实现代码

以下是 Python 实现的 Montgomery 模幂算法的代码：

def montgomery_pow(x, y, n):
    r = 1
    t = x % n
    
    while y != 0:
        if y % 2 == 1:
            r = (r * t) % n
        t = (t * t) % n
        y = y // 2

    return r

def montgomery_reduce(t, n, r, n_inv):
    m = t * n_inv % r
    t = (t + m * n) // r

    if t >= n:
        return t - n
    else:
        return t

def montgomery_multiply(x, y, n, r, n_inv):
    t = x * y
    return montgomery_reduce(t, n, r, n_inv)

def montgomery_pow_mod(x, y, n):
    r = 1
    n_inv = pow(r, -1, n)

    while r < n:
        r <<= 1

    t = (x * r) % n

    y = y % (n - 1)

    while y != 0:
        if y % 2 == 1:
            t = montgomery_multiply(t, x, n, r, n_inv)
        x = montgomery_multiply(x, x, n, r, n_inv)
        y = y // 2

    t = montgomery_reduce(t, n, r, n_inv)

    return t * n_inv % n

其中，montgomery_pow 函数用于计算幂运算，montgomery_reduce 函数用于 Montgomery 约减，montgomery_multiply 函数用于 Montgomery 乘法，montgomery_pow_mod 函数用于计算模幂运算。

代码中使用了位运算，<< 表示左移，>> 表示右移，// 表示整除运算。在 montgomery_pow_mod 函数中，将 r 扩大到大于等于 n 的最小 2 的幂次方，以保证 Montgomery 约减的正确性。n_inv 表示 r 模 n 的逆元，用于 Montgomery 约减。