扩展欧几里得算法求模逆元

### 使用扩展欧几里得算法求解模逆元

对于给定的两个正整数 \( a \) 和 \( m \)，如果存在一个整数 \( x \)，使得：

\[ ax ≡ 1 (\text{mod}\ m) \]

那么 \( x \) 就被称为 \( a \) 关于模 \( m \) 的乘法逆元。为了找到这样的 \( x \)，可以利用扩展欧几里得算法解决这个问题。

#### 理论基础

当且仅当 \( gcd(a,m)=1 \) 即 \( a \) 和 \( m \) 是互质的情况下，\( a \) 对于模 \( m \) 存在一个唯一的乘法逆元[^3]。这是因为只有在这种情况下才有可能找到一对整数 \( x \) 和 \( y \)，满足如下关系：

\[ ax + my = 1 \]

这实际上是一个线性丢番图方程的形式，而寻找该方程的一组特解正是扩展欧几里得算法的核心应用之一[^2]。

#### 实现过程

下面给出一段 Python 代码作为例子展示如何使用扩展欧几里得算法计算模逆元:

def extended_gcd(a, b):
    if a == 0 :
        return b,0,1             
    gcd,x1,y1 = extended_gcd(b%a, a)
    x = y1 - (b//a) * x1
    y = x1
    return gcd,x,y 

def mod_inverse(a, m):  
    gcd, x, _ = extended_gcd(a, m)
    if gcd != 1:
        raise ValueError('Modular inverse does not exist')
    else:
        return x % m

这段程序定义了一个 `extended_gcd` 函数用于执行扩展欧几里得算法，并返回最大公因数以及对应的系数；另一个函数 `mod_inverse` 则用来获取指定数值相对于某个模数下的乘法逆元[^5]。

#### 应用场景

在密码学领域内，特别是在RSA加密体制中经常需要用到大素数之间的模运算及其相应的逆元操作。此外，在处理分数取模问题时也常会遇到需要求解除法的结果的情况，这时就可以借助乘法逆元来间接完成除法的操作[^4]。