群的概念

2020/2/91群的概念群的概念。构成一个群，记为关于运算具有如下性质，则称该运算上的一种代数运算，若是是一个非空集合，设,GGGGeabbaGbGaaaeeaGaeecbacbaGcbaGbaGba**.4**,.3****,,,.2*,,.1使得存在元素存在逆元：恒有对：既存在存在单位元恒有结合律：封闭性：2020/2/92基于离散对数的密码体制群的概念如果一个群上的运算满足交换律，即abbaGba，有：对于任意的,称其为交换群(或Abel群，阿贝尔群)如果一个群的元素是有限的，则称该群是有限群，否则称为无限群。2020/2/93基于离散对数的密码体制群的性质称为右消去律。，则如果称为左消去律；，则如果，对任意的消去律,**,**,,cbacabcbcabaGcba群中每个元素的逆元是唯一的。群中的单位元是唯一的，单位元也称为恒等元。2020/2/94基于离散对数的密码体制例子：设G={1,-1,i,-i}，则(G,﹡)关于乘法“×”是一个有限交换群。元素a1-1i-i逆元a-11-1-ii2020/2/95基于离散对数的密码体制，，则有特别的，取4,3,2,1,0Z55m。的逆元为满足：的逆元，任意的元素单位元剩余加群。，称为模记为换群，的加法构成一个有限交关于模，则集合设aambabababaemZmmmmm0modZ0,ZZ元素a01234逆元043212020/2/96基于离散对数的密码体制乘法群有时把群(G,)记为(G,)，称为“乘法群”。abbababababa；常写成：积的与称为，法，运算结果记为：乘称为把运算。，且的逆元记为。单位元1111aaaGae2020/2/97基于离散对数的密码体制加法群举例，各元素的逆元为：零元，单位元的乘法构成群，即乘群关于模，，，集合1,Z54321Z5*5e元素x1234逆元x-113242020/2/98基于离散对数的密码体制乘群的幂。，，特别地，：即相乘记为个的，则是一个乘群，设nnnnaaaaaaaaanGaZnG101...,,nnnnmmnmnnmbabaGaaaaa是交换群，则如果；指数算法：.3.2.12020/2/99基于离散对数的密码体制加法群有时把群(G,)记为(G,+)，称为“加法群”的“和”；与称为，结果记为：”称为“加”法，运算把运算“bababa。，即有：的负元，记为：的逆元称为。，记为：零元单位元称为00aaaaGa2020/2/910基于离散对数的密码体制加法群举例，各元素的负元为：零元，单位元的加法构成群，即加群关于模，，，，集合0,543210Z55eZ元素x01234负元-x043212020/2/911基于离散对数的密码体制加法群中的倍加运算anananaaaaanGaZnG00...,,，特别地：，运算称为倍加：即相加的个，则是一个加群，设nbnabananmnamamnmana.3.2.1；倍数法则：2020/2/912基于离散对数的密码体制群的阶群元素的阶GGGG记为：的阶，中元素的个数称为群是一个群，则设是无限阶的。是有限阶的，否则，则称得，使，如果存在正整数的单位元，是群设个aaeraaarGaGe2020/2/913基于离散对数的密码体制元素的阶。是无限阶的，则记为。如果，记为：的阶称为正整数的最小满足，且是有限阶的，则把如果aaraareaGarordordorder,。无限阶的，则记为是。如果，记为：的阶称为正整数的最小满足，且是有限阶的，则把如果aaraarearGaordordorder,2020/2/914基于离散对数的密码体制元素的阶举例a1234orda1442425mod116222225mod3822225mod42225mod2224321Z,Z4321*5*5orda，所以，，，，有解：对于。，，，中每个元素的阶，计算群2020/2/915基于离散对数的密码体制元素的阶举例32ord6mod06222326mod422226mod2212543210,66，所以，，，有解：对于。，，，，，中每个元素的阶，计算群aZZa012345orda1632362020/2/916基于离散对数的密码体制群元素阶的性质子。素的阶都是群阶数的因元。即有限群的任何一个整除且有限阶的是，，则对任意的是一个有限群，设GaaGanGGord,2020/2/917基于离散对数的密码体制循环群...,,,G210GG是一个生成元。记为：所生成的循环群，并称称为由的方幂，则示成一个元素中的每一个元素都能表设群.,...,,,1210nGnG阶循环群，则是一个若的一个生成元。是，则即，的阶，的阶等于群阶循环群，如果元素是一个设ordGGGGnG2020/2/918基于离散对数的密码体制循环群举例是一个生成元。循环群。阶是，则设1,Z1,...,2,1,0Z,Zmmmmm循环群的生成元不是唯一的03056555,22054,3155341052551515,4,3,2,1,0Z66，，，。，的生成元有，取特别的，m2020/2/919基于离散对数的密码体制阶循环群。是是素数，则设1,Zmmm。，，，，，，所以，，，，，，有解：对于，。生成元：，，，阶循环群，是群例子：22224321Z116222223822224222222324321Z4,Z23145432155。，，，，，，，所以，，，，，有对于33334321Z181333332273333493333332134543212020/2/920基于离散对数的密码体制1,gcdrnGGnGnGr件是：的生成元的充分必要条也是的一个生成元，则是个生成元。如果恰有阶循环群，则是一个设个生成元。共有，故而群，从而，，所以，，，，由于对于验证：2,221244Z4321Z,Z512555Z个生成元。共有，故群，则有，，所以，，，，由于对于验证：2,Z2323266Z5,4321,0Z,Z66662020/2/921基于离散对数的密码体制举例。，，和的生成元有：。所以群，，为：的元素的一个生成元，且满足是群解：111117175151,11751,12gcd,11212ZrZ的全部生成元求,12Z2020/2/922练习13271,Z,Zpppp的形式，其中或幂成元的倍数成生把该群的全部元素表示群中取出一个生成元，的全部生成元，从每个和求出循环群