11.群

文档摘要

title: 11. 群 tags: zk basic abstract algebra group theory group WTF zk教程第11讲：群在继续学习数论进阶内容之前，我们需要学习一些抽象代数的内容，包括群，环，和域。这一讲，我们介绍群论基础，包括群的定义和基本性质。抽象代数 "抽象代数"之所以被称为"抽象"，是因为它是从具体的数学结构中抽象出来的一种独立的代数理论。在抽象代数中，研究的不是特定的代数系统（比如实数或复数域），而是关注代数结构的普遍性质和规律。具体来说，抽象代数从代数结构的一般性质出发，研究集合、运算和代数方程等概念。它将对各种代数结构的研究抽象为共同的代数理论，例如群、环、域等概念。


title: 11. 群
tags:
  - zk
  - basic
  - abstract algebra
  - group theory
  - group

WTF zk教程第11讲：群

在继续学习数论进阶内容之前，我们需要学习一些抽象代数的内容，包括群，环，和域。这一讲，我们介绍群论基础，包括群的定义和基本性质。

1. 抽象代数

"抽象代数"之所以被称为"抽象"，是因为它是从具体的数学结构中抽象出来的一种独立的代数理论。在抽象代数中，研究的不是特定的代数系统（比如实数或复数域），而是关注代数结构的普遍性质和规律。

具体来说，抽象代数从代数结构的一般性质出发，研究集合、运算和代数方程等概念。它将对各种代数结构的研究抽象为共同的代数理论，例如群、环、域等概念。通过这种抽象的方法，抽象代数可以揭示不同代数系统之间的共性，同时提供了一种更一般的视角，使得我们能够理解和比较不同数学结构之间的关系。

2. 群

群（Group）是一种抽象的代数结构，它包含一个集合和一个二元运算。群通常用 (G, \cdot) 表示，其中 G 代表群的集合，\cdot 代表群的二元运算。但在本教程中，我们需要更加拥抱抽象代数文化。G通常会让人想起坤坤的代表作“G你太美”，因此，我们用坤群代表最抽象的群，简称为群，用 (G, ) 表示，代表二元运算，读作g运算。

但不是每个集合与二元运算的组合都可以称为群，必须要满足 4 个基本性质：

封闭性（Closure）： 任意元素 A,B 属于坤群， AB 仍属于坤群。
结合律（Associativity）： 群中的元素进行运算的结果不依赖于计算的顺序，即 (AB)C =A(BC) 。
存在单位元（Identity Element）： 存在一个特殊的群元素 E ，使得它与任何群元素进行运算都不会改变其值，即 AE=EA=A，类似于整数加法中的 0。
存在逆元（Inverse Element）： 对于群中的每个元素，存在另一个元素逆元素，两者运算的结果为单位元 E，即 AA'=A'A=E。元素 A' 被称为 A 的逆元，记为 A^{-1}。

我们可以用群的4个基本性质判断一个拥有二元运算的集合是否是群，下面举几个例子。

补充：

若给定一个集合及其二元运算，且二元运算仅满足封闭性，则称之为 Magma

若给定一个 Magma，且二元运算还满足结合律，则称之为半群 Semigroup 。

若给定一个 Semigroup，且集合中存在单位元，则称之为 Monoid 。

若给定一个 Monoid ，且集合中任意元素都存在逆元，则称之为群 Group 。

2.1 (\mathbb{Z}, +)

考虑整数集合 \mathbb{Z} 和加法运算：

整数相加的结果还是整数，满足封闭性。
整数加法也满足结合律。
单位元素是0，任何整数加0都等于这个整数本身。
整数的逆元素就是它的相反数，比如 5 的逆元是 -5。

因此整数集合 \mathbb{Z} 和加法运算具有群的性质，它们构成了整数加法群。

2.2 (\mathbb{Z}, \times)

考虑整数集合 \mathbb{Z} 和乘法运算：

整数相乘的结果还是整数，满足封闭性。
整数乘法也满足结合律。
单位元素是1，任何整数乘以1都等于这个整数本身。
除了 1 和 -1 以外的元素都不存在逆元，比如 2， 2 \times 0.5 = 1，但是 0.5 不是整数。

因此整数集合 \mathbb{Z} 和乘法运算不满足群的性质，不构成群。

2.3 (\mathbb{R}, \times)

考虑实数集合 \mathbb{R} 和乘法运算：

实数相乘的结果还是实数，满足封闭性。
实数乘法也满足结合律。
单位元素是1，任何实数乘以1都等于这个实数本身。
除了 0 以外的其他实数都存在逆元，为它的倒数。但是 0 不存在逆元。

因此实数集合 \mathbb{R} 和乘法运算不满足群的性质，不构成群。但是如果把 0 剔除后的实数集 \mathbb{R} \setminus \{0\} 和乘法运算组合，就满足群的性质，因此 (\mathbb{R}\setminus \{0\}, \times) 是一个群。

2.4 (\mathbb{Z}_n^*, \times)

考虑模 n 的单元集（Set of units） \mathbb{Z}_n^* 和乘法运算：

模 n 的单元集 \mathbb{Z}_n^* 的乘法封闭。
模运算中的乘法满足结合律。
单位元素是1，任何单位乘以1都等于这个它本身。
模 n 的单元集中的元素都有逆元，两者乘积为 1。

因此模 n 的单元集 \mathbb{Z}_n^* 和乘法运算满足群的性质，它经常被称为整数模n乘法群。

2.5 平凡群

平凡群指仅包含一个元素的群，这个元素就是它的单位元 E。运算为 EE=E。平凡群满足群的4个基本性质，你可以自行验证。

3. 群的性质

从群的4个基本性质，我们能推出一些所有群都具备的重要性质：

1. 唯一单位元： 群中的单位元是唯一的。

点我展开证明

我们用反证法。首先，假设群 (G, ) 有两个单位元 E 和 E'。根据单位元定义，单位元乘以任何数都等于它本身，也就是 EE'=E=E' （可以理解为 E 右单位元 E' 等于 E，同时可以理解为 E' 左单位元 E 等于 E‘），也就是 E=E'，推出矛盾。因此群中的单位元是唯一的。

证毕。

2. 唯一逆元： 群中每个元素的逆元是唯一的。

点我展开证明

我们是用反证法。假设群 (G, ) 的存在一个元素 A 有两个不相等的逆元素 B 和 C，即 AB=E 且 AC=E。我们在 AB=E 同时 C，有 CAB=EC。由于 CA=E，原式可以化简为 EB=EC。根据单位元定义，任何数单位元都等于它本身，因此有 B=C，推出矛盾。因此群中每个元素的逆元是唯一的。

证毕。

3. 消去律： 对于群中的任意元素 a, b, c，如果 ab = ac 或 ba = ca，则 b = c。

点我展开证明

我们可以在 ab = ac 两边左侧同时乘以 a 的逆元，就能得到 b=c。

ba = ca 同理，在右侧同时乘以 a 的逆元，能得到 b=c。

证毕。

4. 有限群和无限群

有限群（Finite Group）指群中元素的个数是有限的，比如 (\mathbb{Z}_n^*, +)。密码学中主要使用的是有限群，因此它是我们的重点学习对象。

无限群（Infinite Group）指群中元素的个数是无限的，比如 (\mathbb{Z}, +)， (\mathbb{R},+)。

5. 总结

这一讲，我们介绍了抽象代数，群的基本定义和性质。很多零知识证明算法都基于群论，我们需要掌握好它。