readme.md

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

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

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

1. 最大公约数

1.1 定义

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

$$ \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$ 的最大公因数，首先先对它们进行质数分解：

$$ 30 = 2 * 3 * 5 $$

$$ 24 = 2^3*3 $$

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

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

2. 欧几里得算法

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

2.1 基本思想

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

$$ a = bq + r $$

，其中 $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$ 并运用欧几里得除法：

$$ b = rq_1 + r_1 $$

$$ ... $$

$$ r_{i-2} = r_{i-1}q_{i} + r_i $$

$$ ... $$

$$ r_{n-2} = r_{n-1}q_{n} + r_n $$

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

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

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

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

$$ \gcd(r_{n-1}, r_n) = \gcd(r_{n-1}, 0) = r_{n-1} $$

因此，最大公约数 $\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. 总结

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