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
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. 总结

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