跳到主要内容

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

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

1. 贝祖等式​

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

ax+by=gcd⁡(a,b)ax + by = \gcd(a, b)

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

2. 拓展欧几里得算法​

2.1 基本思想​

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

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

a=bq0+r0a = bq_0 + r_0
b=r0q1+r1b = r_0q_1 + r_1
......
ri−2=ri−1qi+rir_{i-2} = r_{i-1}q_{i} + r_i
......
rn−2=rn−1qn+rnr_{n-2} = r_{n-1}q_{n} + r_n

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

rn−2=gcd⁡(a,b)qnr_{n-2} = \gcd(a,b) q_{n}
rn−3=rn−2qn−1+gcd⁡(a,b)r_{n-3} = r_{n-2} q_{n-1} + \gcd(a,b)
......
a=bq+ra = bq + r

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

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

2.2 迭代推导​

2.2.1 迭代公式​

首先，我们将每次迭代得到的余数写为 aa 和 bb 的线性组合。对于第 ii 次迭代得到的余数 rir_i，设整数 xix_i 和 yiy_i 使得以下等式成立：

xia+yib=rix_i a + y_i b=r_i

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

xn−1a+yn−1b=gcd⁡(a,b)x_{n-1} a + y_{n-1} b=\gcd(a,b)

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

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

ri=ri−2−ri−1qir_i = r_{i-2} - r_{i-1}q_{i}

将 ri−2r_{i-2} 和 ri−1r_{i-1} 展开为 aa 和 bb 的线性组合，得到：

ri=(xi−2−xi−1qi)a+(yi−2−yi−1qi)br_i = (x_{i-2} - x_{i-1}q_{i}) a + (y_{i-2} - y_{i-1}q_{i}) b

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

xi=xi−2−xi−1qix_i = x_{i-2} - x_{i-1}q_{i}
yi=yi−2−yi−1qiy_i = y_{i-2} - y_{i-1}q_{i}

2.2.2 初始条件​

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

r0=a−q0br_0 = a - q_0b

也就是说 x0=1x_0 = 1, y0=−q0y_0 = -q_0, 因此有：

1=x−2−q0x−11 = x_{-2} -q_0 x_{-1}
−q0=y−2−q0y−1-q_0 = y_{-2} -q_0 y_{-1}

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

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

xi=xi−2−xi−1qix_i = x_{i-2} - x_{i-1}q_{i}
yi=yi−2−yi−1qiy_i = y_{i-2} - y_{i-1}q_{i}

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

2.2.3 例子​

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

ax+by=gcd⁡(a,b)ax + by = \gcd(a, b)

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

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

30=1⋅24+630 = 1 \cdot 24 + 6

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

x0=1−1×0=1x_0 = 1 - 1 \times 0 = 1
y0=0−1×1=−1y_0 = 0 - 1 \times 1 = -1

此时 xia+yib=rix_i a + y_i b=r_i，等式左边为 30−2430-24，右边 66，等式成立。

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

    24=4⋅6+024 = 4 \cdot 6 + 0

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

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

    a−b=6a - b = 6

2.3 递归推导​

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

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

当 b≠0b\neq 0 时，有 gcd(a,b)=gcd(b,a%b)gcd(a, b)=gcd(b, a\% b) 。对于左边， gcd(a,b)=ax+bygcd(a, b)=ax+by ，对于右边， gcd(b,a%b)=bx1+(a%b)⋅y1=bx1+(a−(a//b)⋅b)⋅y1=ay1+b(x1−(a//b)⋅y1)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=y1,y=(x1−(a//b)⋅y1)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≡1(modm)ax \equiv 1 \pmod{m} 的方程，其中 aa 和 mm 互质。

4. 总结​

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