title: 04. 拓展欧几里得算法
tags:
  - zk
  - basic
  - euclidean​

WTF zk教程第4讲：拓展欧几里得算法

在本讲中，我们将深入研究欧几里得算法的一种扩展，这一算法不仅可以计算最大公约数，还能找到满足贝祖等式（Bézout equation）的整数解。

1. 贝祖等式

在介绍拓展欧几里得算法之前，让我们先来了解一下贝祖等式。对于两个整数 a 和 b，存在整数 x 和 y 使得它们满足如下等式：

这个等式称为贝祖等式，其中 \gcd(a, b) 是 a 和 b 的最大公约数。拓展欧几里得算法的目标就是找到这样的整数 x 和 y。

2. 拓展欧几里得算法

2.1 基本思想

拓展欧几里得算法在使用欧几里得算法计算最大公约数的同时，通过逆向推导，找到满足贝祖等式的整数解。在欧几里得算法中，我们只关心每次迭代的余数 r_i，而不关心商 q_i；而拓展算法中利用 q_i 逆向求出贝祖等式，可谓是废物利用了。

让我们回忆一下欧几里得算法：

我们会不断迭代直到 r_n = 0，而此时 r_{n-1}= \gcd(a,b)，有：

其中所有 q_i 都是已知的。因此，我们可以不断展开，将 r, ..., r_{n-2} 表示为 a 和 b 的线性组合，最终将 \gcd(a,b) 表示为 a 和 b 的线性组合，得到贝祖等式。

下面使用迭代和递归两种方法推导。

2.2 迭代推导

2.2.1 迭代公式

首先，我们将每次迭代得到的余数写为 a 和 b 的线性组合。对于第 i 次迭代得到的余数 r_i，设整数 x_i 和 y_i 使得以下等式成立：

因为 r_{n-1}=\gcd(a,b)，因此有

因此, (x_{n-1}, y_{n-1} ) 就是满足贝祖等式的 (x,y)。我们需要做的就是迭代的计算出它们。

从式子 r_{i-2} = r_{i-1}q_{i} + r_i 我们可以得到：

将 r_{i-2} 和 r_{i-1} 展开为 a 和 b 的线性组合，得到：

因此，我们得到了 (x_i, y_i) 与 (x_{i-2},x_{i-1},y_{i-2},y_{i-1}) 的迭代关系：

2.2.2 初始条件

有了迭代关系，接下来，我们需要确定初始条件。对于第一步迭代，有：

也就是说 x_0 = 1, y_0 = -q_0, 因此有：

因此，我们可以得到初始条件 (x_{-2}, x_{-1}, y_{-2}, y_{-1}) = (1, 0, 0, 1)

然后在使用欧几里得算法时不断迭代 (x_i, y_i)，

最终得到的 (x_{n-1}, y_{n-1}) 就是贝祖等式中的 (x,y)。

2.2.3 例子

下面我们计算使得 a=30 和 b=24 满足贝祖等式的整数 x 和 y：

1. 第一步：初始化 (x_{-2}, x_{-1}, y_{-2}, y_{-1}) = (1, 0, 0, 1)。

2. 第二步：运用欧几里得除法，得到

这里 (q_0, r_0) = (1, 6)，代入 (x_i, y_i) 迭代等式，有：

此时 x_i a + y_i b=r_i，等式左边为 30-24，右边 6，等式成立。

2. 第三步：余数 r=6 不为零，用 b 替换 a, r 替换 b，继续运用欧几里得除法，得到

这里 (q_1, r_1) = (4, 0), 此时余数为0，停止迭代。得到最大公约数 \gcd(30,24)=6, 而 (x, y) = (x_0, y_0)=(1, -1).

4. 第四步：得到满足贝祖等式的系数 (x, y) =(1, -1)，贝祖等式为：

2.3 递归推导

要求 x, y 满足 x\cdot a+y\cdot b=gcd(a, b) 。

当 b = 0 时，显然 x=1, y=0 ；

当 b\neq 0 时，有 gcd(a, b)=gcd(b, a\% b) 。对于左边， gcd(a, b)=ax+by ，对于右边， gcd(b, a\% b)=bx_1+(a\% b)\cdot y_1=bx_1+(a-(a//b)\cdot b)\cdot y_1=ay_1+b(x_1-(a//b)\cdot y_1), 左右对应有： x=y_1, y=(x_1-(a//b)\cdot y_1)。推毕。

2.4. 代码实现

让我们用Python来实现拓展欧几里得算法：

迭代版本

def extended_euclidean_algorithm(a, b):
    x1, y1, x2, y2 = 1, 0, 0, 1
    
    while b:
        q = a // b
        a, b = b, a % b
        x1, x2 = x2, x1 - q * x2
        y1, y2 = y2, y1 - q * y2

    return a, x1, y1

# 示例
num1 = 30
num2 = 24
gcd_result, x, y = extended_euclidean_algorithm(num1, num2)
print(f'{num1} 和 {num2} 的最大公约数是 {gcd_result}')
print(f'满足贝祖等式的整数解为：{num1}*{x} + {num2}*{y} = {gcd_result}')
​

递归版本

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

3. 应用场景

拓展欧几里得算法的应用非常广泛，其中一些主要的应用场景包括：

• 乘法逆元： 拓展欧几里得算法最主要的用途是计算模 N 乘法逆元，具体过程见下一讲。
• RSA算法： 在RSA非对称加密算法中，拓展欧几里得算法用于生成私钥，确保其满足一定的数学关系。
• 同余方程求解： 在数论中，拓展欧几里得算法常用于解决同余方程，即形如 ax \equiv 1 \pmod{m} 的方程，其中 a 和 m 互质。

4. 总结

这一讲，我们介绍了贝祖等式和拓展欧几里得算法。拓展欧几里得算法有着广泛应用，学好它，可以为我们日后深入学习零知识证明奠定基础。