title: 03. 欧几里得算法
tags:
  - zk
  - basic
  - euclidean​

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

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

1. 最大公约数

1.1 定义

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

1.2 最大公约数的性质

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

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

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

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

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

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

1.3 如何计算最大公约数

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

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

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

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

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

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

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

2. 欧几里得算法

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

2.1 基本思想

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

，其中 q 和 r 为自然数，且 0 \leq r \lt |b|。

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

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

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

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

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

2.2 算法步骤

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

2.3 例子

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

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

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

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

2.4 直观理解

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

首先，我们尝试使用 b × b 方形瓷砖来平铺矩形；然而，这会留下一个 r × b 剩余矩形，其中 r < b。然后，我们尝试用 r × r 方形图块来平铺剩余矩形，这留下了第二个残差矩形 r_1 × r。接下来，我们尝试使用 r_1 × r_1 方形图块对其进行平铺，依此类推。当没有剩余矩形时，即当正方形图块完全覆盖先前的剩余矩形时，序列结束。最小正方形瓷砖的边长就是 \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. 总结

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