群环域讲解ppt课件.ppt

《群环域讲解ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、群群的概念是由一个非空集合G组成，在集合G中定义了一个二元运算符“·”，并满足以下性质的代数系统，记为｛G,·｝交换群：有限群无限群有限群的阶循环群循环群的生成元群的性质群中的单位元是唯一的群中每一个元素的逆元是唯一的(消去律)对任意的　　　，如果，或　　　，则群在密码学中要用的重要概念循环群及生成元置转换见群.pdf环：设是代数系统,R为集合,+,·为二元运算,如果(1)为阿贝尔群,(2)为半群,(3)乘法“·”对加法“+”适合分配律,即对任何a,b,c∈R,有a·(b+c)=(a·b)+(a·c)(a+b)·c=(a

2、·c)+(b·c)则称是环理解：环就是一个集合，可以在其上进行加法和乘法运算而封闭。剩余类环：剩余类集Zn={0,1,2,…,(n-1)},Zn中每个整数代表一个剩余类，有时也记为Zn={[0],[1],[2],…,[n-1]}。运算定义：[a]+[b]=[a+b][a]·[b]=[a·b]零因子：元素a,b称零因子，如果a≠0，b≠0但a·b＝0。环中没有这样的元素，则说环中无零因子。域：若环去掉0元的是交换群，则称为域即：是交换群是交换群运算“·”对于运算“+”是可分配

3、的。理解：域就是一个集合，可以在其上进行加法、减法、乘法和除法运算而封闭。（a/b定义为a·b-1）有理数集合，实数集合，复数集合，这些都是无限域，在密码学中没有什么实际意义；所以考虑与整数有关的域，对密码学有实际意义。素域Fp：剩余类环Fp={[0],[1],[2],…,[p-1]}，p这素数。定理：如果(a,p)=1,p>0,则ax1(modp)有唯一解xa'(modp).由定理可知，若(a,p)=1，a的模逆存在，若p为素数，更成立。即：[a]为模p的剩余类，则存在剩余类[b]，使[a]·[b]=[1]的充要条件是(a,p)=1.p为素数就更成

4、立。从引理可得，Fp是域。有限域在密码学中很意义，主要有素域Fp（一般记为GF(p)）、二进制域GF(2n)例：GF(7)定理：域必是整环。证明：因为域是可交换含幺环，又无零因子，所以也是整环。域必是整环，但整环不一定是域。例如是整环。但不是域，因为对·除1外均不可逆所以不是群。整环与域的区别：只差可逆性是整环；是域：⑴是交换群。⑴是交换群。⑵是可交换。⑵是交换群。⑶“·”对“+”可分配。⑶“·”对“+”可分配。⑷无零因子有限域的两个定理密码学常用

5、素域GF(p)或阶为2m的域GF(2m)GF(p)有限域中的计算生成元与逆元生成元可证明：在GF(p)中至少存在一个元素g，使得GF(p)中任意非零元素可以表示成g的某次方幂的形式，g称为GF(p)的生成元逆元生成元的例子有限域GF（23），5是GF（23）的生成元50＝151＝552＝253＝1054＝455＝2056＝857＝1758＝1659＝11510＝9511＝22512＝18513＝21514＝13515＝19516＝3517＝15518＝6519＝7520＝12521＝14522＝1多项式多项式不可约多项式(素多项式)f(x)不能表示为另两

6、个多项式的乘积多项式运算加/减/乘多项式除法:f(x)/g(x)=q(x)…r(x)整除，若r(x)=0系数在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)modg(x)系数在GF(2)中的多项式加法XOR乘法AND(这在计算机操作时有优势)GF(p^n)GF(p^n)域Zp上的小于n-1次多项式集合S共有p^n个集合S上的有限域系数模pf(x)模某n次不可约多项式m(x)GF(2m)域GF(2^8)系数模2，即只可0或

7、1次数最高7次，共2^8=256个多项式(剩余类)m(x)=x^8+x^4+x^3+x+1ExampleGF(23)ExampleGF(23)生成元与逆元生成元：逆元例子：GF（24）取：GF（24）的元素：（0000）(0001)(0010)(0011)(0100)(0101)(0110)(0111)(1000)(1001)(1010)(1011)(1100)(1101)(1110)(1111)例子（续）生成元为：a=xGF(2^n)上的运算加法XOR乘法移位，加法/XOR乘法逆元(除法)扩展Euclid算法