前言
准备学习密码学,想在此之前先学习一下群论、数论和离散数学(这个不一定),在本文中,先学习一下群论。
***注意:***下面的*
不是乘法运算,而是一个二元运算符,用'*'
表示而已。
教程未完待续。。。
第一章 基础
第1节 定义
什么是一个群,群有着如下四个性质。定义一个非空集合G
,与一个运算*
,记为(G,*)
- 封闭性:∀a,b∈G,a∗b∈G,a与b的运算,也属于G。满足这条,则左单位元=右单位元=单位元
- 结合律:∀a,b,c∈G,a∗(b∗c)=(a∗b)∗c。满足这条,则左逆元=右逆元=逆元
- 单位元:∃e∈G,∀a∈G,a∗e=e∗a=a,如果只有一边满足,则称为左单位元或者右单位元
- 逆元:∀a∈G,则∃b∈G,a∗b=b∗a=e,e为单元元,如果只有一边满足,则称为左逆元或者右逆元,逆元可以用来做逆运算,如加法减法,乘法除法。记a的逆元为:a−1
下面举一个群论的例子,(Z,+)
,整数集和加法运算。
- 封闭性:∀a,b∈Z,a+b∈Z,显然成立的
- 结合律:∀a,b,c∈Z,a+(b+c)=(a+b)+c,也是显然成立的
- 单位元:0∈Z,∀a∈Z,a+0=0+a=a,加法运算中,0就是单位元
- 逆元:∀a∈Z,−a∈Z,a+(−a)=(−a)+a=0,存在逆元,逆元进行运算就是单位元0。
除此之外,非0有理数和乘法,这个也是一个群。
第2节 分类
- 有限群:G是有限集,称G里元素个数为群G的“阶”,记为|G|。
- 无限群:G是无限集,群G的“阶”为无限阶。
第二章 定理
-
群的单位元是唯一的,证明如下
假设存在e和e’两个单位元,且e≠e’,那么,e*e’ = e = e’,矛盾
- 群里只有一个元素,称为“平凡群”。唯一元素只能是单位元
-
每个元素只有唯一的逆元
假设b,c为a的两个逆元,那么b=b*e = b*(a*c) = (b*a)*c = e*c = c
-
消去律:a*b=a*c,那么b=c
a∗b=a∗c ⇒ a−1∗a∗b=a−1∗a∗c ⇒ e∗b=e∗c ⇒ b=c
-
a∗x=b,唯一解 x∈G
a∗x=b ⇒ x=a−1∗b∈G
-
(a∗b)−1=b−1∗a−1
(a∗b)∗(b−1∗a−1) ⇒ a∗(b∗b−1)∗a−1 ⇒ e
-
(a−1)−1=a
(a−1)−1=a ⇐ (a−1)−1∗a−1=a∗a−1 ⇐ e=e
-
一种记法:at=a∗a∗a∗...∗a,注意,a是元素,t是整数。元素不等于整数,元素是一个抽象概念。
-
一种记法:a−t=a−1∗a−1∗...∗a−1,注意同上
-
(at)m=(a∗a∗...∗a)∗(a∗a∗...∗a)∗...∗(a∗a∗...∗a)=at×m,这里×表示乘法
-
at∗am=a∗a∗...∗a ∗ a∗a∗a∗...∗a=at+m ,这里+表示加法
-
(a−1)t=a−1∗a−1∗...∗a−1=(a∗a∗...∗a)−1=(at)−1=a−t
第三章 阿贝尔群
第1节 定义
除了第一章第1节之外的定义,阿贝尔群还需要满足交换律
- ∀a,b∈G,a∗b=b∗a
第2节 定理
- 群G是阿贝尔群,当且仅当∀a,b∈G,有(a∗b)2=a2∗b2
- (a∗b)t=a∗b∗a∗b∗...∗a∗b=a∗a∗a...∗a∗b∗b∗...∗b=at∗bt
第四章 子群
第1节 定义
设(G, *)
为一个群,H是G的非空子集,如果(H,*)
是一个群,则称(H,*)
为(G,*)
的子群。
第2节 定理
假设群H是群G的子群
第3节 判断子群
一、H是G的非空子集,∀a,b∈H,则a∗b−1∈H,则H是G的子群。如何证明呢?
a,b∈H,b−1∈H⇒a∗b−1∈H
(1)证明单位元,b=a,a∗b−1=a∗a−1=e,存在单位元
(2)证明封闭性,a,c∈H,则c−1∈H,那么a∗c=a∗(c−1)−1∈H,其中把c−1看作b就知道了
(3)剩下的性质,由于群G是一个群,则可以证明
二、H是G的非空子集,如果H是有限集,而其G的运算*
在H上满足封闭性,则H是G的子群。(H是有限集、封闭,则是子群)
第五章 陪集及扩展
第1节 陪集
H是群G的子群,a∈G,则aH:={a∗h∣h∈H},称为H关于a在G中的左陪集。同理,Ha:={h∗a∣h∈H},称为右陪集。对于运算符合交换律,则左右陪集应该是相等的,下面只讨论陪集。由群G中元素a与子群H中每个元素进行二元运算*
之后构成的陪集记为[a]H。下面是一个陪集的例子。
例子:
所有偶数和加法可以构成一个群,记为O,但是所有奇数和加法没法构成群(可以由集合四大性质去证明看)。但是将O中所有元素加1,构成集合 [O]1,也就是奇数集合。那么这个集合称为陪集。
第2节 陪集的性质
接下来,讨论一下陪集有些什么性质。
-
a∈[a]H;证明:e∈H⇒e∗a∈H⇒a∈H。这是因为对子群H中的单位元与a做一次运算还是a,陪集的定义也是子群中的所有元素与a做一次运算的集合。
-
[e]H称为平凡陪集,子群本身也是陪集,是子群H中的所有元素与群G中的e做一次运算得到的集合,其就是子群H的集合。(e为单位元)。
-
a∈H⇔[a]H=H。
必要性:a∗e∈[a]H=H⇒a∈H
充分性:
第一,∀b∈H,a∈H⇒a∗b∈H⇒[a]H⊆H,其中,由于b的任意性有a∗b=[a]H。
第二,∀b∈H,a∈H⇒a−1∈H, a−1∗b∈H⇒a∗(a−1∗b)∈[a]H⇒b∈[a]H⇒H⊆[a]H,其中,a∗(a−1∗b)是陪集的定义,由于b的任意性,b=H。
-
[a]H=[b]H⇔a−1∗b∈H(b−1∗a∈H)
H={e,h1,h2,...,hn,...},[a]H={a,a∗h1,a∗h2,...,a∗hn,...},[b]H={b,b∗h1,b∗h2,...,b∗hn,...}。
[a]H=[b]H⇒b=a∗hm⇒a−1∗b=hm∈H。这是因为必定有aH里面必定有一个元素等于b
推论:两个陪集要么相等,要么相交为空
假如 [a]H∩[b]H=∅,那么必然有,h1,h2∈H,a∗h1=b∗h2⇒b−1∗a=h2∗h1−1∈H⇒[a]H=[b]H。
第3节 拉格朗日定理
不要跟高等数学中学的拉格朗日中值定理搞混,拉格朗日有好多定理。
若H是有限群G的子群,则H的阶可以整除G的阶。
给出简单的证明:
1.对于子群H,使用有限群中的a1,a2,a3…与子群H构成陪集,对于任意陪集,其都含于G。
2.现在考虑,a1与a2生成的陪集可能重叠吗?答案是不可能的。证明如下:a1≠a2,因为是不同元素。由上一节推论有,[a1]H=[a2]H或者[a1]H∩[a2]H=∅。
3.由于陪集的阶等于子群的阶,所以最终所有陪集阶与子群阶的和只能为子群的倍数。所有子群与子群的所有陪集可以覆盖群G,那么群G的阶肯定是子群H与其所有陪集阶的和。
第4节 商群
正规子群
如果子群N是群G的正规子群,那么有 ∀n∈N,∀g∈G,gng−1∈N。下面介绍正规子群的等价条件
- gNg−1=N(gN=Ng)
- gNg−1=N
- ∀g,h∈G,gh∈N⇔hg∈N
商群
设N是群G的正规子群,定义集合G/N是N在G中所有左陪集的集合,也就是G/N={aN:a∈G}。对于G/N中的任意两个元素,aN与bN,得到下列乘法关系。
(aN)(bN) = a(Nb)N = abNN = (ab)N