密码学与网络安全-第四章 密码数学基础(B).ppt

第四章密码学基础(B)
代数结构——群、环、域
§1 代数结构
一、群(group)
定义 设G为一非空集合, 为定义在G上的二元运算.
如果下述条件成立, 则称代数系统G, 为一个群.
(1) 运算封闭性: a, bG, abG;
(2) 结合律: a, b, cG,
a(bc)=(ab)c;
(3) 存在单位元 eG: 使得对aG,
ae=ea=a;
(4) aG, 存在a的逆元 a1G: 使得
aa1= a1a=e.
(5) 交换律:a,b G, ab= ba.
交换群
例1 G =  Zn, + (模 n +) 为一个群, 且是交换群。
单位元为 0 mod n
a 的逆元是– a mod n= n-a
例2 G =  Z*n, × (模 n ×) 为一个群, 且是交换群。
单位元为 1 mod n
a 的逆元是 a -1 mod n
例3 A={a, b, c, d}, G = A , · 是交换群。
运算表:
·
a
b
c
d
a
a
b
c
d
b
b
c
d
a
c
c
d
a
b
d
d
a
b
c
单位元: a
逆元对: (a,a) , (b,d), (c,c)
例4 置换群(permutation group)
设(1,2,3) 的所有置换构成集合
T={(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2),(3,2,1)}
在T上规定二元运算⊙为两个置换的复合:
(2,1,3)⊙(2,3,1) =(1,3,2)
⊙
(1,2,3)
(1,3,2)
(2,1,3)
(2,3,1)
(3,1,2)
(3,2,1)
(1,2,3)
(1,2,3)
(1,3,2)
(1,2,3)
(2,1,3)
(1,2,3)
(3,2,1)
(2,3,1)
(1,3,2)
(1,2,3)
(3,1,2)
(1,2,3)
(3,2,1)
(1,2,3)
则G =  T, ⊙为一个群, 但不是交换群。
单位元为恒等置换 e ={ 1,2,3}
a 的逆元是 a 的逆置换
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
1 2 3
(2 1 3 )
(2 3 1 )
(1 3 2 )
定义设G, 是一群, H是G的一非空子集. 如果
H, 也是群, 则称H, 是G, 的一个子群.
定义设G, 是一群, 若G的元素个数有限, 则称
G, 是有限群(finite group).
|G| 表示G的元素个数,称为G的阶。
在模 n 加法运算下,Zn 是n阶有限群。
定义设G, 是一群, 若G的元素可以由一个元素及其
幂组成,则称G, 是循环群(cyclic group).
在 n 阶循环群中,生成元素为 g ,
G={e, g, g2, … gn-1 } , gn = e
循环群的生成元素可能不只一个!
例6 在 G= Z*10 , * 中, Z*10 ={1,3,7,9}, 有循环子群:
H1= {1}, × , 生成元是 1
H2= {1,9}, × ,生成元是9
H3= G, 生成元是3, 或 7
例5 在 G= Z6 , + 中, 有循环子群:
H1= {0}, + , 生成元是0
H2= {0,2,4}, + ,生成元是2或4
H3= {0,3}, + , 生成元是3
H4= Z6, + , 生成元是1
例7 在 G= Z17 , + 中,
仅有两个可能的子群:
阶数为1的子群: {0} , + 
阶数为17的子群: G
 Zp , + 子群结构很简单!
Lagernge 定理
设H 是 G 的子群,则|H| | |G|。
H的阶数必能整除G的阶数!
子群H的阶数一定是|G|的因子!
定义设G, 是一群, a 是G的一个元素。
满足 a n = e 的最小整数,称为元素 a 的阶,
记为 ord (a) 。
ord (a) 等于由 a 生成的循环子群的阶数。
例9 G= Z*10 , * , Z*10 ={1,3,7,9},
H1= {1}, × , ord(1)= 1
H2= {1,9}, × ,ord(9)=2
H3= G, ord(3)=ord(7)=4
例8 在 G= Z6 , + 中, 有循环子群:
H1= {0}, + , ord(0)=1
H