跳到主要内容

WTF zk教程第3讲：欧几里得算法

这一讲，我们将学习最大公约数和计算它的欧几里得算法，它们在密码学中有广泛的应用。

1. 最大公约数​

1.1 定义​

最大公约数（GCD）是能够同时整除两个整数的最大正整数，例如 1010 和 1515 的最大公约数是 55，可以写为：

gcd⁡(10,15)=5\gcd(10, 15)=5

1.2 最大公约数的性质​

对于自然数 aa 和 bb (假设 a>ba > b) ，它们的最大公约数有以下性质：

  1. 交换律: gcd⁡(a,b)=gcd⁡(b,a)\gcd(a, b)=\gcd(b,a)

  2. aa 和 bb 的最大公约数同时也是 bb 和 aa 除以 bb 的余数 的最大公约数: gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a, b) = \gcd(b, a \bmod b)

  3. aa 和 00 的最大公约数为 aa: gcd⁡(a,0)=a\gcd(a,0)=a

  4. 如果 aa 能被 bb 整除（记为 b∣ab \mid a），则有 gcd⁡(a,b)=b\gcd(a,b)=b

大家可以尝试推导一下这些性质。

1.3 如何计算最大公约数​

我们常用两个方法计算最大公约数：质数分解和欧几里得算法。这里我们先介绍质数分解法，它主要有三步：

  1. 质因数分解： 对于两个整数 aa 和 bb，分别进行质因数分解。

  2. 找出相同的质因数: 比较两个数的质因数，找出它们共有的部分。

  3. 相乘得到最大公约数: 将这些共有的质因数相乘，得到的结果即为最大公约数。

举个例子，计算 a=30a = 30 和 b=24b = 24 的最大公因数，首先先对它们进行质数分解：

30=2∗3∗530 = 2 * 3 * 5
24=23∗324 = 2^3*3

共有部分为 2∗32*3，因此它们的最大公约数为 66。

但是大数的质数分解非常困难，欧几里得算法是计算最大公约数更有效率的算法。

2. 欧几里得算法​

欧几里得算法（也称辗转相除法）是我们用于计算两个整数的最大公约数的常用算法。

2.1 基本思想​

设两个整数为 aa 和 bb，其中 a≥ba \geq b，使用欧几里得除法，有

a=bq+ra = bq + r

，其中 qq 和 rr 为自然数，且 0≤r<∣b∣0 \leq r \lt |b|。

根据最大公约数的性质（章节1.2的第2条），有 gcd⁡(a,b)=gcd⁡(b,r)\gcd(a, b) = \gcd(b, r)，而 r<b≤ar < b \le a，我们将两个大数之间的求公约数的问题转换为了两个较小数的相同。当 r≠0r \neq 0 时，我们可以不断地将 aa 和 bb 替换为 bb 和 rr 并运用欧几里得除法：

b=rq1+r1b = rq_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

迭代过程中，最大公因数有如下关系：

gcd⁡(a,b)=gcd⁡(b,r)=...=gcd⁡(rn−2,rn−1)=gcd⁡(rn−1,rn)\gcd(a, b) = \gcd(b, r) = ... = \gcd(r_{n-2}, r_{n-1}) = \gcd(r_{n-1}, r_{n})

又因为 0≤rn<rn−1<r0 \leq r_n < r_{n-1} < r，每次迭代 rnr_n 都会变小，直到 rn=0r_n = 0。

当 rn=0r_n = 0 时，根据最大公约数的性质（章节1.2第3条），有:

gcd⁡(rn−1,rn)=gcd⁡(rn−1,0)=rn−1\gcd(r_{n-1}, r_n) = \gcd(r_{n-1}, 0) = r_{n-1}

因此，最大公约数 gcd⁡(a,b)=rn−1\gcd(a,b)=r_{n-1}。

2.2 算法步骤​

  1. 令 rr 为 aa 除以 bb 的余数，即 r=amod  br = a \mod b。
  2. 如果 rr 不为零，则用 bb 替换 aa, rr 替换 bb，并返回第一步。
  3. 如果 rr 为零，则 bb 即为最大公约数。

2.3 例子​

下面我们计算 a=30a=30 和 b=24b=24 的最大公约数：

  1. 第一步：运用欧几里得除法，得到 30=1⋅24+630 = 1 \cdot 24 + 6

  2. 第二步：余数 r=6r=6 不为零，用 bb 替换 aa, rr 替换 bb，继续运用运用欧几里得除法，得到 24=4⋅6+024 = 4 \cdot 6 + 0

  3. 第三步：上一步余数 r=0r=0 为零，停止迭代，得到最大公约数 gcd⁡(30,24)=6\gcd(30,24)=6。

2.4 直观理解​

假如我们有一块长为 aa，宽为 bb 的长方形房间，它希望用正方形瓷砖平铺这个房间，并且瓷砖的边长尽可能大。其实这个瓷砖最大边长就是最大公约数 gcd⁡(a,b)\gcd(a,b)，而欧几里得方法可以让我们找到它：

首先，我们尝试使用 b×bb × b 方形瓷砖来平铺矩形；然而，这会留下一个 r×br × b 剩余矩形，其中 r<br < b。然后，我们尝试用 r×rr × r 方形图块来平铺剩余矩形，这留下了第二个残差矩形 r1×rr_1 × r。接下来，我们尝试使用 r1×r1r_1 × r_1 方形图块对其进行平铺，依此类推。当没有剩余矩形时，即当正方形图块完全覆盖先前的剩余矩形时，序列结束。最小正方形瓷砖的边长就是 gcd⁡(a,b)\gcd(a,b)。

图片来自维基百科

2.5 代码实现​

我们可以使用python实现欧几里得算法，只需要6行代码：

def euclidean_algorithm(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

# 示例
num1 = 30
num2 = 24
gcd_result = euclidean_algorithm(num1, num2)
print(f'{num1} 和 {num2} 的最大公约数是 {gcd_result}')
# 输出: 30 和 24 的最大公约数是 6

3. 总结​

最大公约数在密码学中非常重要，而欧几里得算法是解决整数的最大公约数的常用算法。通过了解这一算法，我们为后续深入学习零知识证明和密码学打下了基础。