Python实现扩展欧几里得算法(exgcd)及其应用288

扩展欧几里得算法(Extended Euclidean Algorithm, exgcd)是欧几里得算法的扩展，它不仅能够求出两个整数的最大公约数(Greatest Common Divisor, gcd)，还能找到满足贝祖等式 (Bézout's identity) 的整数解 x 和 y，即 ax + by = gcd(a, b)。这在数论、密码学以及许多算法问题中都有着重要的应用。

本文将详细介绍 exgcd 算法的原理、Python 实现以及几个典型的应用场景。我们将从基本的欧几里得算法开始，逐步引出 exgcd 算法，并提供清晰的代码示例和详细的解释。

1. 欧几里得算法回顾

欧几里得算法是求解两个非负整数最大公约数的经典算法。其核心思想基于以下性质：gcd(a, b) = gcd(b, a mod b)，其中 a mod b 表示 a 除以 b 的余数。算法递归地进行，直到余数为 0，此时另一个数就是最大公约数。

Python 代码实现如下：```python
def gcd(a, b):
"""
欧几里得算法求解最大公约数
"""
if b == 0:
return a
else:
return gcd(b, a % b)
```

2. 扩展欧几里得算法 (exgcd)

扩展欧几里得算法不仅求出 gcd(a, b)，还找到整数 x 和 y 使得 ax + by = gcd(a, b)。算法过程与欧几里得算法类似，但需要在递归过程中维护 x 和 y 的值。

我们可以通过递归的方式实现 exgcd 算法：```python
def exgcd(a, b):
"""
扩展欧几里得算法
返回 (gcd(a, b), x, y) 使得 ax + by = gcd(a, b)
"""
if b == 0:
return a, 1, 0
else:
g, x, y = exgcd(b, a % b)
return g, y, x - (a // b) * y
```

在这个递归实现中，当 b=0 时，gcd(a, 0) = a，此时 x=1, y=0 满足等式 ax + by = a。递归步骤则利用了以下关系：如果 g, x, y 满足 bx + (a % b)y = gcd(b, a % b)，则 g, y, x - (a // b) * y 满足 ax + by = gcd(a, b)。

我们也可以使用迭代的方式实现 exgcd，这在某些情况下效率更高：```python
def exgcd_iterative(a, b):
"""
扩展欧几里得算法 (迭代实现)
"""
x0, x1, y0, y1 = 1, 0, 0, 1
while b != 0:
q, r = divmod(a, b)
a, b = b, r
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
return a, x0, y0
```

3. 应用示例

exgcd 算法在许多领域都有应用，以下列举几个例子：

3.1 求解线性同余方程

线性同余方程形如 ax ≡ b (mod m)。如果 gcd(a, m) | b，则该方程有解。可以使用 exgcd 算法求解。具体来说，先求出 a 和 m 的最大公约数 g 和 x, y 使得 ax + my = g。如果 g | b，则 x0 = x * (b // g) 是一个特解。通解则为 x = x0 + k * (m // g)，其中 k 为整数。```python
def solve_linear_congruence(a, b, m):
"""
求解线性同余方程 ax ≡ b (mod m)
"""
g, x, y = exgcd(a, m)
if b % g != 0:
return None # 无解
else:
x0 = x * (b // g)
return x0 % m
```

3.2 求解模逆元

如果 gcd(a, m) = 1，则 a 模 m 的逆元存在。逆元 x 满足 ax ≡ 1 (mod m)。可以使用 exgcd 算法求解，即求解线性同余方程 ax ≡ 1 (mod m)。```python
def modular_inverse(a, m):
"""
求解模逆元
"""
g, x, y = exgcd(a, m)
if g != 1:
return None # 逆元不存在
else:
return x % m
```

4. 总结

本文详细介绍了扩展欧几里得算法的原理、递归和迭代实现，并给出了几个重要的应用场景，包括求解线性同余方程和模逆元。掌握 exgcd 算法对于深入理解数论和解决相关算法问题至关重要。读者可以根据实际需求选择递归或迭代实现，并根据应用场景灵活运用。

希望本文能够帮助读者更好地理解和应用 exgcd 算法。

2025-06-25

下一篇：Python Vandermonde矩阵：原理、实现与应用