MoonMath SNARK 手册

$$\gdef\G{\Bbb{G}}$$

交换群(Commutative Groups)是对数学现象的本质抽象，如加法和减法或乘法和除法。¹

为了理解交换群，让我们回想当我们在学校学习整数加法和减法的时候。我们已经知道每当两个整数相加那么结果必然是一个整数。我们还了解到当我们对任一整数增加零，那么产生的结果与最初的加数相同。此外，我们还了解到两个(或更多)整数相加的顺序对加法结果没有影响，并且括号对于加法结果没有影响。对于任意整数，总存在另一个整数(负数)使其相加后结果为 0

这些条件是交换群的定义属性，数学家认识到完全相同的规则集可以在不同的数学结构内找到。因此，给出一个抽象的、形式化的且与任何具体的例子分离的群定义是有意义的。这使我们可以灵活地处理来自不同数学领域的实体，同时保留抽象代数等领域的基本结构部分。

将这些规则提炼为最小的独立属性列表并将其抽象化，我们得到了如下交换群的定义：

一个交换群 \((\G,\cdot)\) 由集合 \(\G\) 和映射 \(\cdot:\G \times \G \to \G\) 构成。该映射被称为群法则(group law)，该映射将集合内两个元素运算为第三个元素，使得以下属性成立：

1. 交换性(Commutativity)：对于任意的 \(g_1, g_2 \in \G\)，等式 \(g_1 \cdot g_2 = g_2 \cdot g_1\) 成立
2. 结合性(Associativity)：任选 \(g_1,g_2,g_3 \in \G\) ，等式 \(g_1 \cdot (g_2 \cdot g_3) = (g_1 \cdot g_2) \cdot g_3\) 成立
3. 存在幺元(Existence of a neutral element)：对于任一 \(g \in \G\)，存在 \(e \in \G\) 使得 \(e \cdot g = g\)
4. 存在逆(Existence of an inverse)：对于任一 \(g \in \G\) ，存在 \(g^{-1} \in \G\) 使得 \(g \cdot g^{-1} = e\)

如果 \((\G, \cdot)\) 是一个群，并且 \(\G'\subset\G\) 是 \(\G\) 的子集且映射关系依旧封闭，即 \(\cdot:\G' \times \G' \to \G'\) 成立，那么我们称 \((\G', \cdot)\) 是 \((\G, \cdot)\) 的子群(subgroup)

通俗地说，群是我们可以以类似整数相加的方式进行运算的一类结构。具体来说，这意味着我们可以以一种可逆的方式将两个元素结合成一个新的元素，且最终结果与结合的顺序无关。

符号 3

因为我们在本书中仅关注交换群，所以我们直接称交换群为群。

如果不会引起歧义(即已知群法则)的情况下，我们通常删除 \(\cdot\) 符号而直接使用 \(\G\) 表示一个群。

符号 4

对于交换群 \((G, \cdot)\)，我们有时使用所谓的加法记号(additive notation) \((G, +)\) ，即使用 \(+\) 而不是 \(\cdot\) 代表群法则，幺元记为 \(0\) ，且 \(g \in \G\) 的逆元为 \(-g := g^{-1}\)

在后文中，群会在密码学和 SNARKs 中大量使用。但是先让我看一些熟悉的例子。

示例 31

具有整数加法的整数集 \((\Bbb{Z}, +)\) 是典型的交换群，其中群法则使用 加法记号书写。

为了将整数加法与交换群的抽象公理进行比较，我们首先注意到整数的加法是符合交换律和结合律的。整数加法的幺元 \(e\) 是 \(0\) ，此外整数的逆元是其相反数。 这意味着整数与加法是符合抽象意义上的交换群的。

举一个整数子群的例子，已知包含 \(0\) 的偶数集：

\[\Bbb{Z}_{even}:=\{\ldots,-4,-2,0,2,4,\ldots\}\]

我们可以发现此集合是 \((\Bbb{Z}, +)\) 的子集，因为满足以下条件：

1. 偶数的和仍为偶数，说明映射关系封闭
2. 存在幺元 \(0\)
3. 存在逆元

示例 32

交换群最基本的例子是只有一个元素 \(\{\bullet\}\) 且映射关系为 \(\bullet\cdot \bullet=\bullet\) 的群。我们称这种群为平凡群(trivial group)

平凡群是任何群的子群。为证明这一点，设 \((G, \cdot)\) 是一个具有幺元 \(e \in \G\) 的群，那么 \(e \cdot e = e\) 和 \(e^{-1}=e\) 都成立。因此，集合 \(\{e\}\) 是 \(\G\) 的子群。事实上， \(\{0\}\) 是 \((\Bbb{Z}, +)\) 的子群，因为 \(0 + 0 = 0\) 成立。

示例 33

已知模 6 算术体系 \((\Bbb{Z}_6, +)\)中的加法，如 示例 11 中的定义。显然，同余类 \(0\) 是模 6 体系中的幺元，同余类 \(r\) 的逆元为 \(6-r\) ，因为 \(r + (6-r) = 6\) ，其中 \(6\) 与 \(0\) 同余。此外，\(r_1 + r_2 = r_2 + r_1\) 及 \((r_1+r_2)+r_3=r_1+(r_2+r_3)\) 继承自整数加法。因此，我们认为 \((\Bbb{Z}_6,+)\) 是一个群。

上一个示例(即示例 33)中的交换群在本书中是一个重要的示例。从这个例子中，我们可以抽象得到以下结论：对于任意模数 \(n\) 的 \((\Bbb{Z}_n, +)\) ，可以证明 \((\Bbb{Z}_n, +)\) 为一个交换群，且幺元为 \(0\) ，任何元素 \(r \in \Bbb{Z}_n\)都存在加法逆元 \(n-r\)。我们称这样的群为关于模 n 的同余类群(remainder class group)

练习 33. 已知 示例 16，设 \(\Bbb{Z}_5^{*}\) 是 \(\Bbb{Z}_5\) 中除同余类 0 以外的所有同余类的集合，即 \(\Bbb{Z}^{ * }_5 = \{1,2,3,4\}\) ，证明 \((\Bbb{Z}_5^*, \cdot)\) 为交换群。

练习 34. 推广上一个练习的，已知对一般的模数 \(n\)，设 \(\Bbb{Z}_n^*\) 是 \(\Bbb{Z}_n\) 中除同余类 \(0\) 以外的元素构成的集合，即 \(\Bbb{Z}_n^*=\{1,2,\cdots,n-1\}\)。举一个反例证明 \((\Bbb{Z}_n^*, \cdot)\) 不是一般的群。

找到一个条件使得 \((\Bbb{Z}_n^*, \cdot)\) 是一个交换群，并计算幺元，给出任何元素的逆元表达式并证明交换群公理。