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

文档介绍：第四章密码学基础(B)代数结构——群、环、域§1代数结构一、群(group),,则称代数系统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=Zn,+(模n+)为一个群,且是交换群。单位元为0modna的逆元是–amodn=n-a例2G=Z*n,×(模n×)为一个群,且是交换群。单位元为1modna的逆元是a-1modn例3A={a,b,c,d},G=A,·是交换群。运算表:·dabddabc单位元:a逆元对:(a,a),(b,d),(c,c)例4置换群(permutationgroup)设(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的逆置换123123123123123123(213)(231)(132)定义设G,是一群,H,也是群,则称H,是G,G,是一群,若G的元素个数有限,则称G,是有限群(finitegroup).|G|表示G的元素个数,称为G的阶。在模n加法运算下,Zn是n阶有限群。定义设G,是一群,若G的元素可以由一个元素及其幂组成,则称G,是循环群(cyclicgroup).在n阶循环群中,生成元素为g,G={e,g,g2,…gn-1},gn=e循环群的生成元素可能不只一个!例6在G=Z*10,*中,Z*10={1,3,7,9},有循环子群:H1={1},×,生成元是1H2={1,9},×,生成元是9H3=G,生成元是3,或7例5在G=Z6,+中,有循环子群:H1={0},+,生成元是0H2={0,2,4},+,生成元是2或4H3={0,3},+,生成元是3H4=Z6,+,生成元是1例7在G=Z17,+中,仅有两个可能的子群:阶数为1的子群:{0},+阶数为17的子群:GZp,+子群结构很简单!Lagernge定理设H是G的子群,则|H|||G|。H的阶数必能整除G的阶数!子群H的阶数一定是|G|的因子!定义设G,是一群,a是G的一个元素。满足an=e的最小整数,称为元素a的阶,记为ord(a)。ord(a)等于由a生成的循环子群的阶数。例9G=Z*10,*,Z*10={1,3,7,9},H1={1},×,ord(1)=1H2={1,9},×,ord(9)=2H3=G,ord(3)=ord(7)=4例8在G=Z6,+中,有循环子群:H1={0},+,ord(0)=1H2={0,2,4},+,ord(2)=ord(4)=3H3={0,3},+,ord(3)=2H4=Gord(1)=ord(5)=6他们都是|G|的因子!他们也都是|G|的因子!二、环(ring)定义设G为一非空集合,G上定义了两种二元运算+:构成加法交换群:满足封闭性+结合律(+交换律)而且*对+有分配律则称代数系统R=G,+,为一个环或交换环。+运算*运算运算封闭性运算封闭性结合律结合律交换律交换律*单位元(零元)逆元(负元)*对+分配律整数集Z上的(+,*)运算构成交换环R=Z,+,不能进行“除法”运算三、域(field)定义设G为一非空集合,G上定义了两种二元运算+:构成加法交换群:构成乘法交换群而且*对+有分配律则称代数系统F=G,+,为一个域。+运算*运算运算封闭性运算封闭性结合律结合律交换律交换律零元单位元负元逆元*对+分配律加减乘除畅通无阻!