《群环域讲解ppt课件.ppt》由会员分享，可在线阅读，更多相关《群环域讲解ppt课件.ppt（25页珍藏版）》请在三一办公上搜索。
1、群,群的概念是由一个非空集合G组成，在集合G中定义了一个二元运算符“ ”，并满足以下性质的代数系统，记为G, ,交换群：,有限群无限群有限群的阶循环群循环群的生成元,群的性质,群中的单位元是唯一的群中每一个元素的逆元是唯一的 (消去律) 对任意的，如果 ，或，则,群在密码学中要用的重要概念,循环群及生成元置转换见群.pdf,环：设是代数系统,R为集合,+,为二元运算,如果 (1)为阿贝尔群, (2)为半群, (3)乘法“”对加法“+”适合分配律,即对任何a,b,cR,有 a(b+c)=(ab)+(ac) (a+b)c =(ac)+(bc)则称是环,理解：环就是一个集合，可以在其上进行加法和乘法
2、运算而封闭。,剩余类环：剩余类集Zn=0,1,2,(n-1),Zn中每个整数代表一个剩余类，有时也记为Zn=0,1,2,n-1。运算定义： a+b=a+b ab=a b,零因子：元素a,b称零因子，如果a0，b0但ab0。环中没有这样的元素，则说环中无零因子。,域：若环去掉0元的是交换群，则称为域即：是交换群是交换群运算“”对于运算“+”是可分配的。,理解：域就是一个集合，可以在其上进行加法、减法、乘法和除法运算而封闭。（a/b定义为ab-1 ）有理数集合，实数集合，复数集合，这些都是无限域，在密码学中没有什么实际意义； 所以考虑与整数有关的域，对密码学有实际意义。,素域Fp：剩余类环 Fp=
3、0,1,2,p-1，p这素数。定理：如果(a,p)=1,p0,则 ax1(mod p) 有唯一解xa (mod p). 由定理可知，若(a,p)=1，a 的模逆存在，若p为素数，更成立。即：a为模p的剩余类，则存在剩余类b，使ab=1的充要条件是(a,p)=1. p为素数就更成立。 从引理可得， Fp是域。 有限域在密码学中很意义，主要有素域Fp（一般记为GF(p)）、二进制域GF(2n),例： GF(7),定理：域必是整环。证明：因为域是可交换含幺环，又无零因子，所以也是整环。 域必是整环，但整环不一定是域。 例如 是整环。但不是域，因为对 除1外均不可逆所以不是群。 整环与域的区别：只差可
4、逆性是整环； 是域： 是交换群。 是交换群。 是可交换。 是交换群。 “” 对“+”可分配。 “” 对“+”可分配。 无零因子,有限域的两个定理,密码学常用素域GF(p)或阶为2m的域GF(2m),GF(p)有限域中的计算,生成元与逆元,生成元可证明：在GF(p)中至少存在一个元素g，使得GF(p)中任意非零元素可以表示成g的某次方幂的形式，g称为GF(p)的生成元逆元,生成元的例子,有限域GF（23），5是GF（23）的生成元,多项式,多项式 不可约多项式(素多项式)f(x)不能表示为另两个多项式的乘积多项式运算加/减/乘多项式除法: f(x)/g(x)=q(x)r(x)整除，若r(x)=0
5、,系数在Zp中的多项式,系数在Zp中的多项式多项式环多项式除法: f(x)/g(x)=q(x)r(x)整除，若r(x)=0模g(x)同余f(x) = q(x) g(x) + r(x) f(x) r(x) mod g(x)系数在GF(2)中的多项式加法 XOR乘法 AND(这在计算机操作时有优势),GF(pn),GF(pn)域Zp上的小于n-1次多项式集合S共有pn个集合S上的有限域系数模pf(x)模某n次不可约多项式m(x),GF(2m)域,GF(28),系数模2，即只可0或1次数最高7次，共28=256个多项式(剩余类)m(x) = x8 + x4 + x3 + x + 1,Example GF(23),Example GF(23),生成元与逆元,生成元：逆元,例子：GF（24）,取：GF（24）的元素：,例子（续）,生成元为：a=x,GF(2n)上的运算,加法XOR乘法移位，加法/XOR乘法逆元(除法)扩展Euclid算法,
