2021年2021年度密码学基础群循环群生成元讲义.ppt

文档介绍：注1: (G2)中的元素e 称为群G的单位元(unit element)或恒等元(identity). 群G的单位元是唯一的.
注2: (G3)中的元素b称为元素a的逆元(inverse).元素a的逆元是唯一的,记为a-1. 即有a∗a-1=a-1∗a=e
1
密码学基础群循环群生成元
2021/1/25
有限群
交换群
如果群G的运算还满足:
(G4)交换律:即对所有的a, b∈G, 有a∗b=b∗a.
则称G是一个交换群(commutative group),或阿贝尔群(abelian group).
G中元素的个数称为群G的阶(order), 记为|G|. 如果|G|是有限数,则称G是有限群(finite group), 否则称G是无限群(infinite group).
例: 整数加群(Z,+); 有理数加群(Q,+); 实数加群(R,+); 复数加群(C,+).
令Q*=Q-{0}, (Q*, ×)是群; Q+={q∈Q| q>0}, (Q+, ×)是群.
2
密码学基础群循环群生成元
2021/1/25
群的概念
例1 设G={1, -1, i, -i}, 则(G, ×) 是一个有限交换群.
元素a
1
-1
i
-i
逆元a-1
1
-1
-i
i
3
密码学基础群循环群生成元
2021/1/25
例2 设m∈Z+, Zm={0,1,…, m-1}, 则(Zm, ⊕) 是一个有限交换群. 称为模m剩余类加群.
单位元是e=0; a∈Zm的逆元a-1= m-a.
特别地: 取m=5, 有Z5={0,1,2,3,4},
元素a
0
1
2
3
4
逆元a-1
0
4
3
2
1
4
密码学基础群循环群生成元
2021/1/25
有时把交换群(G, ∗)记为(G, +), 称为“加群”.
把运算“∗”称为“加” 法, 运算结果记为: a∗b= a+b,称为a与b的“和”;
单位元称为“零元”, 记为“0”;
a∈G的逆元称为G的负元,记为: “- a”, 即有a+(-a)= 0.
5
密码学基础群循环群生成元
2021/1/25
例1
G={1, -1, i, -i}, (G, *)是一个有限交换群. 可记为: (G, *)= (G, +), 运算式为:
1+(-1)=-1, 1+i=i, 1+(-i)=-i, (-1)+i=-i, (-1)+(-i)=i, i+(-i)=1, 1+1=1
请问零元是？利用 a+e＝e+a=a
试求 (-i)+(-i), i+i, (-1)+(-1).
6
密码学基础群循环群生成元
2021/1/25
例2 加群: (Z5,⊕)=(Z5,+), 其中Z5={0,1,2,3,4}. 零元0=0,负元为:
元素x
0
1
2
3
4
负元-x
0
4
3
2
1
7
密码学基础群循环群生成元
2021/1/25
群的概念
有时把群(G, ∗)记为(G, ⋅), 称为“ 乘群”.
把运算“∗”称为“乘” 法, 运算结果记为: a∗b= a⋅b, 称为a与b的“积”;
运算符号通常省略, 简记为: a∗b=a⋅b=ab.
单位元记为: e=1.
8
密码学基础群循环群生成元
2021/1/25
例3 设m∈Z+, Zm={0,1,…, m-1}, 则(Zm, ⊗)!
0×?=1 找不到这样的元素！
例4 设m∈Z+是素数, Zm*= {1,2,…,m-1}, 则 (Zm*, ⊗)是一个有限交换群.
单位元: e=1; a∈Zm的逆元a-1: a×a-1=1 (mod m).
9
密码学基础群循环群生成元
2021/1/25
特别地: 取m=5, 有Z5*={1,2,3,4},
1×1＝1 mod 5 所以1的逆元素是1
求出其他元素的逆元素
10
密码学基础群循环群生成元
2021/1/25