用python代码实现欧几里得扩展算法 模运算求逆

欧几里得扩展算法（也称为中国剩余定理的简化版）用于计算两个整数的最大公约数（GCD）以及它们的模逆元。当需要找到a除以b的逆元模m（即gcd(a, m) = 1的情况下），可以同时求出a和b的逆元c和d。

Python实现如下：

def extended_gcd(a, b):
    """
    使用欧几里得扩展算法计算最大公约数并返回 a * c % m == 1 的c值（如果存在）
    """
    x, y, u, v = 0, 1, 1, 0
    while b != 0:
        q, r = divmod(a, b)
        a, b = b, r
        x, u = u - q * x, x
        y, v = v - q * y, y
    return a, u, v

# 示例：计算5和17的最小公倍数及模逆
a = 5
b = 17
gcd, inv_a, inv_b = extended_gcd(a, b)

if gcd == 1:  # 如果有模逆元
    lcm = a * b // gcd  # 最小公倍数
    print(f"5对17取模逆的结果是 {inv_a} (mod {b})")
    print(f"17对5取模逆的结果是 {inv_b} (mod {a})")
    print(f"5和17的最小公倍数是 {lcm}")
else:
    print("无法找到模逆元，因为gcd(5, 17) != 1")

相关问题

使用python代码实现欧几里得扩展算法 模运算求逆，命名为getInverse(m, b方法，如没有逆，则返回None值

在Python中，可以使用欧几里得扩展算法（也称作中国剩余定理的简化版本）来计算模逆，即找到一个数x使得 (m * x) % b == 1。这个算法通常用于解决同余方程组的问题。以下是将这个功能封装成一个名为`get_inverse`的方法：

def get_inverse(m, b):
    # 检查是否满足模逆的基本条件（b和m互质）
    if gcd(m, b) != 1:
        return None

    # 初始化两个变量 x 和 s，初始值都为0，t初始化为1，相当于 x = 0, s = 1, t = m
    x, s, t = 0, 1, m

    # 执行欧几里得算法
    while t != 0:
        quotient = s // t
        temp = x - quotient * t
        x = s
        s = t
        t = temp

    # 返回模逆结果，如果t等于b，则x就是b的逆元
    return x % b if x != 0 else None

# 辅助函数：计算最大公约数 (gcd)
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 示例用法
print(get_inverse(15, 26))  # 输出：7，因为15*7 % 26 == 1

在这个代码中，`get_inverse`函数首先检查`m`和`b`是否互质，如果不是则返回`None`。然后通过循环逐步更新`x`, `s`, `t`，直到`t`变为0，此时`x`就是`b`对于`m`的逆元。

python代码实现快速模幂运算、扩展欧几里得、中国剩余定理等公钥密码算法所需要的数学基础运算的心得体会

快速模幂运算：
在实现快速模幂运算时，需要注意到一个简单的公式：
a ^ b % m = (a % m) ^ b % m
这个公式可以极大地减少计算量，加快计算速度。具体实现时，可以通过不断将指数b除以2，并将底数a平方，直到指数b为0，最后将结果对模数m取余即可得到快速幂结果。代码实现如下：

def fast_power(base, exponent, mod):
    result = 1
    base = base % mod
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % mod
        exponent = exponent // 2
        base = (base * base) % mod
    return result

扩展欧几里得：
扩展欧几里得算法是用于求解两个整数a和b的最大公约数gcd以及一组满足 ax+by=gcd 的整数解x和y。在实现该算法时，需要注意到以下性质：
- gcd(a, b) = gcd(b, a % b)
- 若ax+by=gcd(a,b)，则bx'+(a%b)y'=gcd(b,a%b)，其中 x'=y, y'=x-(a//b)y

从而可以递归调用该算法，直到b=0为止。最后返回gcd以及最后一次迭代中求得的x和y即可。代码实现如下：

def extended_euclidean_algorithm(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x, y = extended_euclidean_algorithm(b, a % b)
        return gcd, y, x - (a // b) * y

中国剩余定理：
中国剩余定理是用于求解一组同余方程组的解。在实现该算法时，需要注意到以下性质：
- 若m1,m2互质，则同余方程组x≡a1(mod m1),x≡a2(mod m2)的解为x=(a1m2M2+a2m1M1)(mod M)，其中M=m1m2，M1=M/m1，M2=M/m2，且M1x1≡1(mod m1)，M2x2≡1(mod m2)
- 若m1,m2不互质，则同余方程组x≡a1(mod m1),x≡a2(mod m2)无解

可以逐个求解每个同余方程，最后通过合并得到一个更小的同余方程组来求解。具体实现时，可以使用扩展欧几里得算法求解M1和M2的乘法逆元，从而计算出x1和x2，再代入上述公式即可得到最终解。代码实现如下：

def chinese_remainder_theorem(a, m):
    M = 1
    for mi in m:
        M *= mi

    result = 0
    for i in range(len(a)):
        Mi = M // m[i]
        gcd, x, y = extended_euclidean_algorithm(Mi, m[i])
        result += a[i] * Mi * x
        result %= M

    return result