抽象代数是研究带有特定操作符（一个或多个）的集合的学科。在我们的讨论范围内，我们只关心其操作符为二元操作符的集合。

给定一个带有二元操作符的集合，我们可以根据二元操作符的行为以及集合中允许（或预期）存在的元素对这些集合进行分类。

数学家们为集合上二元操作符的每种可能行为都规定了专门的术语。作为应用型程序员，我们最主要关注的是群（Group，源自群论），但让我们循序渐进地了解它。在这个庞大的代数动物园中，群只是其中的一种。因此，与其孤立地研究群，不如将其放在相关的代数结构（即带有二元操作符的集合）的大背景下进行研究。

抽象代数是一个极其庞大的领域，但我们此处的目的是清晰地理解什么是群，因为在零知识证明（Zero Knowledge Proofs）中它无处不在。我们现在就可以给出一个定义：

群是一个带有二元操作符的集合，该操作符满足封闭性、结合律，具有单位元，且每个元素都有一个逆元。

但这种简练的定义往往不够具有启发性。将其与更广泛的抽象代数领域联系起来理解会更有帮助。

原群 (Magma)

原群（Magma）是一个具有封闭二元操作符的集合。仅此而已。

作为一个程序员，你凭借直觉绝对能理解原群。现在你只是知道了它的专业名称。

例如，考虑所有正整数的集合，我们的二元操作符是 $x^y$。注意我们不允许有负数，因为如果 $y$ 为负数，我们就会得到分数。

很明显，输出结果必定在整数空间内。我们的函数是 $(\mathbb{Z}\times\mathbb{Z})$ 和 $\mathbb{Z}$ 的笛卡尔积（关系）的一个子集。具体而言，$x^y$ 是一个从 $(\mathbb{Z}\times\mathbb{Z})$ 映射到 $\mathbb{Z}$ 的函数。

有趣的是，这个例子既不满足交换律，也不满足结合律。你可以通过在下面的 Python 代码中为 a、b 和 c 选择不同的值来亲自验证这一点。

Copy
assert a ** (b ** c) != (a ** b) ** c
assert a ** b != b ** a

但我们并不在乎这一点。原群（Magma）是限制最少的代数结构之一。唯一重要的是其二元操作符必须具有封闭性。至于其他特性则均不做要求。

代数结构指的是一个带有在该集合上定义的一系列操作的集合。在我们的讨论范围内，我们唯一关心的操作就是二元操作符。

半群 (Semigroup)

半群（Semigroup）是一种二元操作符必须满足结合律的原群（Magma）。

所有的半群都是原群，但并非所有的原群都是半群。

换句话说，半群是一个具有封闭且满足结合律的二元操作符的集合。

假设我们的（无限）集合是由传统字母表 a, b, c,…, x, y, z 组成的所有可能的非空字符串集合。例如，“az”、“programmer”、“zero”、“asdfghjk”、“foo” 和 “bar” 都在这个集合中。

假设我们的二元操作符是字符串的拼接。这显然是封闭的，因为它会生成该集合中的另一个字符串。

请注意，如果我们将 “foo” 和 “bar” 交换位置，输出的字符串将不相同，即 “foobar” 和 “barfoo”。但这并不重要。无论是 “foobar” 还是 “barfoo” 都是该集合的成员，因此 “拼接” 这个二元操作符是封闭的。因为我们拥有一个二元操作符既封闭又满足结合律的集合，所以所有字符串在拼接操作下构成了一个半群。

练习： 请自行推导按顺序拼接 “foo”、“bar” 和 “baz” 是满足结合律的。记住，结合律意味着 $(A \square B) \square C = A \square (B \square C)$，其中 $\square$ 是半群的二元操作符。

练习： 请分别给出一个原群和半群的例子。该原群必须不能是半群。不要使用上面的例子。这意味着对于原群，你必须想出一个封闭但不满足结合律的二元操作符；而对于半群，该二元操作符必须既封闭又满足结合律。

幺半群 (Monoid)

幺半群（Monoid）是一个带有单位元的半群。

啊，是的，这正是“单子（monad）是自函子范畴上的幺半群（A monad is a monoid in the category of endofunctors）”名言中所指的那个幺半群。

如果我们查看 Scala 的 Cats 库中的 monoid documentation，我们可以清楚地看到这些定义：

Copy
trait Semigroup[A] {
    def combine(x: A, y: A): A
}

trait Monoid[A] extends Semigroup[A] {
    def empty: A
}

Cats 库简单地将“单位元（identity）”称为 empty，并将二元操作符称为 combine。Monoid 继承了 Semigroup 这一事实表明，幺半群就是一个半群，只是额外要求它必须包含一个“empty”（单位元）。

尽管上面的代码片段中没有体现，但实际上 combine 是被要求必须满足结合律的。

半群仅仅是拥有一个二元操作符，除了它的输出类型（A）必须与输入类型（x 和 y）相同之外，没有任何其他限制。

例如，不包含零的正整数加法是一个半群，但如果你将零包含在内，它就变成了一个幺半群。

单位元的意思是，如果你将二元操作符作用于单位元和另一个元素 $a$，结果将得到 $a$。在加法的例子中，$8 + 0 = 8$，其中 $0$ 就是单位元。如果你的二元操作符是乘法，那么单位元将是 $1$，因为乘以 $1$ 会返回原本的数字。

如果我们的集合是所有 $2\times 2$ 矩阵的集合，且二元操作符是矩阵乘法，那么单位元将是单位矩阵

基于并集和交集的集合之集合

在我们早先关于集合的讨论中，有些奇怪地没有提到集合的并集和交集。它们也是二元操作符，现在正是介绍它们的好时机。

如果你取 $\set{1,2,3,4}$ 和 $\set{3,4,5,6}$ 这两个集合的并集，你会得到 $\set{1,2,3,4,5,6}$。如果你取 $\set{1,2,3,4}$ 和 $\set{3,4,5,6}$ 的交集，你会得到 $\set{3, 4}$。

显然，这两个操作符都满足结合律。

如果我们定义作用域为所有有限整数集合的集合，那么二元操作符并集和交集就是封闭的，因为它们的结果也是一个整数集合。

集合的并集在这个作用域中存在一个单位元：空集 $\set{}$。任何集合与空集取并集，得到的都是原集合，即 $A \cup \set{} = A$。

因此，所有有限整数集合在并集操作下构成了一个幺半群。

然而，对于所有可能的有限整数集合，在交集（$\cap$）操作下它只是一个半群——因为没有任何有限集合可以作为单位元。但是，如果我们扩展这个集合以包含 $\mathbb{Z}$ 本身——也就是说，我们的集合是 $\{\text{all finite sets of integers}\}\cup\mathbb{\{Z\}}$（所有有限整数集合与 $\mathbb{Z}$ 的并集），在交集操作下，它就会变成一个幺半群，因为 $\mathbb{Z}$ 成为了单位元。

如果感觉我们像是把单位元“硬塞”进去的，确实如此。

稍后我们将看到，椭圆曲线（elliptic curves）也使用了类似的技巧，它包含了一个特殊的点，被称为“无穷远点（point at infinity）”，以此来保持与代数定律的一致性。关键在于，如果我们要说一个集合在某个二元操作符下是幺半群，我们就必须非常清楚其单位元到底是什么。

再举个例子，我们可以假设我们的集合是所有的正整数，在此加法操作中加入一个额外的元素 $\text{mug}$。我们定义 $\text{mug} + x = x$ 且 $x + \text{mug} = x$。作为系统的架构师，我们完全有权决定我们的集合由什么组成，以及二元操作符应当如何表现。不过，为了让这个代数数据结构成为幺半群，其二元操作符必须具有封闭性、满足结合律，并且该集合必须有一个单位元。

如果我们将作用域限制在 $\set{0,1,2,3,4,5}$ 的所有子集，那么在此交集操作下它显然会变成一个幺半群，因为此时的单位元将是 $\set{0,1,2,3,4,5}$，任何与之取交集的整数集合都会返回该集合本身，即 $A \cap \set{0,1,2,3,4,5} = A$。例如，$\set{1,3,4} \cap \set{0,1,2,3,4,5} = \set{1,3,4}$。

在这一点上应该很清楚了，给定二元操作符的代数结构的分类是对集合的作用域非常敏感的。

练习： 假设我们整数上的二元操作符是函数 min(a,b)。它是一个原群、半群还是幺半群？如果我们将作用域限制为正整数（大于等于零）呢？如果在这两个作用域上使用二元操作符 max(a,b) 又是怎样的结果？

练习： 假设我们的集合是所有的 3 位二进制数（一个势为 8 的集合）。假设我们可选的二元操作符是按位与（bit-wise and）、按位或（bit-wise or）、按位异或（bit-wise xor）、按位或非（bit-wise nor）、按位同或（bit-wise xnor）以及按位与非（bit-wise nand）。显然它是封闭的，因为输出的结果是一个 3 位二进制数。请针对每种二元操作符判断，该集合在该二元操作符下属于原群、半群还是幺半群。

群 (Group) - 闪亮登场的主角

群是一个幺半群，其中每个元素都拥有一个逆元（inverse）。

或者具体一点，它是一个具有以下四个属性的集合：

1. 二元操作符是封闭的（原群）
2. 二元操作符满足结合律（半群）
3. 集合具有单位元（幺半群）
4. 集合中的每个元素都有一个逆元

也就是说，对于集合 $A$ 中的任意元素 $a$，存在一个 $a'$ 使得 $a \square a' = i$，其中 $i$ 是单位元，$\square$ 是二元操作符。用更偏数学的语言表述为：

此处，$\square$ 为集合的二元操作符。

说“该集合有一个逆元”是不准确的。确切地说，集合中的每个元素在该集合内都有另一个属于自身的逆元。

在整数与加法操作中，单位元是零（因为你加上零后返回的数字不变），而一个整数的逆元则是符号反转后的该整数（例如，$5$ 的逆元是 $-5$，$-7$ 的逆元是 $7$）。

回到刚才提到的对作用域的敏感度，在正整数上的加法就不能构成群，因为里面不可能存在逆元。

这里的表格进一步讲明了重点：

注意，如果集合没有单位元，“逆元”也就不具有任何意义。根据定义，对一个元素及其逆元应用二元操作符，其结果必定为单位元。

练习： 为什么字符串在拼接操作下不能形成群？

练习： 多项式在加法下满足群的性质。请通过证明它满足所有定义群的性质来证明情况确实如此。

不幸的是，我们的教程只能就此结束，因为初等群论是另一章的主题。

但是，尽管我们在这里鲜有深究，现在你已经具备了大量的背景知识来理解到底什么是群！

简单提一下交换律

上述所有代数数据结构都不要求必须满足交换律。如果它们满足，我们就称它们在该二元操作符上是阿贝尔的（abelian）。在这个语境中，“阿贝尔”意味着二元操作符具有交换性，也就是说操作数的顺序不会影响结果。

阿贝尔的（Abelian）意味着二元操作符满足交换律。

但是要是用“阿贝尔”这个词，听起来会显得更聪明些。

从专业术语层面来看，我们通常不说“加法是阿贝尔的”，而是说“该群在加法上是阿贝尔群”。

再来谈谈子集

让我们把所有这些联系到我们一开始所学的内容上。原群、半群、幺半群和群都是拥有封闭二元操作符的集合。二元操作符本质上就是从集合与自身的笛卡尔积中产生的所有有序对映射回该集合本身的一种映射关系。

群是幺半群的子集，幺半群是半群的子集，半群是原群的子集，而原群则是广义上集合的子集。每个群同时也是一个原群或集合，但原群并不一定是群。

“集合”的概念非常容易在脑海里勾勒，但当我们开始谈论群及其他代数结构时，就很容易感到迷茫。群在我们学习密码学时极其重要。只要记住：

群是一个拥有二元操作符并且遵循四条法则的集合。

此外，现在是时候解放你的固有认知了：不要仅仅将“加法”和“乘法”视为组合事物的主要方式。

我们可以取一个集合（可以包含任何事物）与自身的笛卡尔积，然后将这个有序对的集合映射回它自身。这就是一个二元操作符。如果它遵循上述的构造，那么它就是封闭的。

数学术语并不可怕

在你开始本教程之前，下面这个句子

“字符串集合在字符串拼接这一二元操作符下，究竟是半群还是幺半群，取决于该集合中是否存在空字符串”

对你而言或许还如同天书。

也许你像大多数学习第二语言的人一样，仍然需要在脑海中进行一番转换，但你已经意识到，它其实在极小的篇幅里打包传递了非常庞大的信息量。

我能不带任何数学术语说出这句话吗？当然可以，但那至少需要我用 500 字才能说清楚。理解这些术语的含义是非常有价值的，从长远来看，这会帮我们省下很多麻烦。

它最酷的一点在于：有极其多关于群的定理允许我们直接对群作出断言，而完全不需要理解群内部二元操作符底层的具体运作方式。 这在一定程度上类似于面向对象编程中的多态（polymorphism）或函数式语言中的特征（traits）。它们替你隐藏了底层实现的细节，让你能集中注意力在更高层的逻辑上。这非常强大。

在下一章中，你将学习如何通过同态（homomorphisms）让不同的群之间产生“关联”。

在 RareSkills 学习更多

查看我们的 Zero Knowledge Course，与我们的社区一起学习。

我们的 ZK Book 包含了本系列中其余的 ZK 教程。

原文首发于 2023 年 7 月 25 日