03.欧几里得算法

title: 03. 欧几里得算法 tags: zk basic euclidean WTF zk教程第3讲：欧几里得算法 这一讲，我们将学习最大公约数和计算它的欧几里得算法，它们在密码学中有广泛的应用。 最大公约数 1.1 定义 最大公约数（GCD）是能够同时整除两个整数的最大正整数，例如 $10$ 和 $15$ 的最大公约数是 $5$，可以写为： $$ \gcd(10, 15)=5 $$ 1.2 最大公约数的性质 对于自然数 $a$ 和 $b$ (假设 $a > b$) ，它们的最大公约数有以下性质： 交换律: $\gcd(a, b)=\gcd(b,a)$ $a$ 和 $b$ 的最大公约数同时也是 $b$ 和 $a$ 除以 $b$ 的余数 的最大公约数: $\gcd(a, b) = \gcd(b, a \bmod b)$ $a$ 和 $0$ 的最大公约数为 $a$: $\gcd(a,0)=a$ 如果 $a$ 能被 $b$ 整除（记为 $b \mid a$），则有 $\gcd(a,b)=b$ 大家可以尝试推导一下这些性质。 1.3 如何计算最大公约数 我们常用两个方法计算最大公约数：...