MoonMath SNARK 手册

本书最重要的部分之一是模运算及其在素数域(prime fields)计算中的应用。前者定义在3.3，后者定义在4.3.1。为了方便进行模运算，我们需要熟悉用于计算最大公约数(greatest common divisor，简写为GCD)¹的扩展欧几里得算法(Extended Euclidean Algorithm)。

两个非零整数 \(a\) 和 \(b\) 的最大公约数被定义为可以被 \(a\) 和 \(b\) 整除的最大非零自然数 \(d\)，即在 \(d | a\) 和 \(d | b\) 都成立的情况下的最大非零自然数 \(d\) 。我们使用 \( gcd(a,b) := d \) 表示最大公约数。由于自然数 \(1\) 可被任何其他整数整除，所以 \(1\) 是任何两个非零整数的公约数，但 \(1\) 不一定是最大公约数。

一个常用来计算最大公约数的方法是欧几里得算法。但是，在本书中我们不需要此算法，我们将介绍扩展欧几里得算法。此算法可以计算两个自然数 \(a\) 和 \(b \in \Bbb{N} \) 的最大公约数，并附加有两个整数 \(s, t \in \Bbb{Z} \) 满足以下等式:

\[gcd(a,b) = s \cdot a + t \cdot b \]

以下伪代码展示了如何使用扩展欧几里得算法计算最大公约数和 \(s\) 、 \(t\) ：

由于不知道如何使用mathjax进行伪代码输入，所以此处使用了图片。

该算法非常简单，可以在纸笔计算中有效使用。我们经常将此算法的中间过程写成一个表，在表内填入\(r\)、 \(s\) 和索引 \(k\) 的值。下面的例子给出了一个简单的计算执行过程。

示例 4

为解释扩展欧几里得算法，我们假设 \(a = 12 \)、 \(b = 5\)。由于 \(12,5 \in \Bbb{N} \) 且 \(12 \ge 5 \)。算法要求均被满足，我们可以进行如下计算：

\[ \begin{array}{c|ccc|cc} k & r_k & s_k & t_k & q_k\\ \hline 0 & 12 & 1 & 0 & \\ 1 & 5 & 0 & 1 &\\ 2 & 2 & 1 & -2 & 2 \\ 3 & 1 & -2 & 5 & 2 \\ 4 & 0 & & \\ 5 & \cdot & &\\ \end{array} \]

从上述表格中，我们可以得到 \(12\) 和 \(5\) 的最大公约数为 \(gcd(12,5) = 1 \) 并且得到了 \(1 = (-2) \times 12 + 5 \times 5 \)。使用Sage检查结果：

sage: ZZ(12).xgcd(ZZ(5)) # gcd(a,b),s,t
(1, -2, 5)

练习 8. 扩展欧几里得算法

找到整数 \(s, t \in \Bbb{Z} \) 使得 \(gcd(a, b) = s \cdot a + t \cdot b \) 成立：

• \((a, b) = (45, 10) \)
• \((a, b) = (13, 11) \)
• \((a, b) = (13, 12) \)

练习 9. 走向素数域

存在 \(n \in \Bbb{N} \) 属于自然数， \(p\) 是一个素数，满足 \(n < p\) 。最大公约数 \(gcd(p,n)\) 是多少？

练习 10. 找到所有 \(k \in \Bbb{N} \) 且 \(0 \geq k \geq 100 \)，满足 \(gcd(100, k) = 5 \)

练习 11. 证明对所有 \(n,m \in \Bbb{N} \) 都存在 \(gcd(n,m)=gcd(n+m,m) \)