Skip to content

Latest commit

 

History

History
147 lines (80 loc) · 6.9 KB

readme.md

File metadata and controls

147 lines (80 loc) · 6.9 KB
Raw
title tags
11. 群
zk
basic
abstract algebra
group theory
group

WTF zk教程第11讲：群

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

1. 抽象代数

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

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

2. 群

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

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

  1. 封闭性（Closure）： 任意元素 $A,B$ 属于坤群， $A🐔B$ 仍属于坤群。

  2. 结合律（Associativity）： 群中的元素进行运算的结果不依赖于计算的顺序，即 $(A🐔B)🐔C =A🐔(B🐔C)$ 。

  3. 存在单位元（Identity Element）： 存在一个特殊的群元素 $E$ ，使得它与任何群元素进行运算都不会改变其值，即 $A🐔E=E🐔A=A$，类似于整数加法中的 $0$。

  4. 存在逆元（Inverse Element）： 对于群中的每个元素，存在另一个元素逆元素，两者运算的结果为单位元 $E$，即 $A🐔A'=A'🐔A=E$。元素 $A'$ 被称为 $A$ 的逆元，记为 $A^{-1}$。

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

补充：

  1. 若给定一个集合及其二元运算，且二元运算仅满足封闭性，则称之为 Magma
  2. 若给定一个 Magma，且二元运算还满足结合律，则称之为半群 Semigroup 。
  3. 若给定一个 Semigroup，且集合中存在单位元，则称之为 Monoid 。
  4. 若给定一个 Monoid ，且集合中任意元素都存在逆元，则称之为群 Group 。

2.1 $(\mathbb{Z}, +)$

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

  1. 整数相加的结果还是整数，满足封闭性。

  2. 整数加法也满足结合律。

  3. 单位元素是0，任何整数加0都等于这个整数本身。

  4. 整数的逆元素就是它的相反数，比如 $5$ 的逆元是 $-5$。

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

2.2 $(\mathbb{Z}, \times)$

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

  1. 整数相乘的结果还是整数，满足封闭性。

  2. 整数乘法也满足结合律。

  3. 单位元素是1，任何整数乘以1都等于这个整数本身。

  4. 除了 $1$ 和 $-1$ 以外的元素都不存在逆元，比如 $2$， $2 \times 0.5 = 1$，但是 $0.5$ 不是整数。

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

2.3 $(\mathbb{R}, \times)$

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

  1. 实数相乘的结果还是实数，满足封闭性。

  2. 实数乘法也满足结合律。

  3. 单位元素是1，任何实数乘以1都等于这个实数本身。

  4. 除了 $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^*$ 和乘法运算：

  1. 模 $n$ 的单元集 $\mathbb{Z}_n^*$ 的乘法封闭。

  2. 模运算中的乘法满足结合律。

  3. 单位元素是1，任何单位乘以1都等于这个它本身。

  4. 模 $n$ 的单元集中的元素都有逆元，两者乘积为 $1$。

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

2.5 平凡群

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

3. 群的性质

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

  • 1. 唯一单位元： 群中的单位元是唯一的。
点我展开证明👀

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

证毕。

  • 2. 唯一逆元： 群中每个元素的逆元是唯一的。
点我展开证明👀

我们是用反证法。假设群 $(G, 🐔)$ 的存在一个元素 $A$ 有两个不相等的逆元素 $B$ 和 $C$，即 $A🐔B=E$ 且 $A🐔C=E$。我们在 $A🐔B=E$ 同时🐔 $C$，有 $C🐔A🐔B=E🐔C$。由于 $C🐔A=E$，原式可以化简为 $E🐔B=E🐔C$。根据单位元定义，任何数🐔单位元都等于它本身，因此有 $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. 总结

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