群环域讲解

群•群的概念–是由一个非空集合G组成，在集合G中定义了一个二元运算符“·”，并满足以下性质的代数系统，记为｛G,·｝交换群：有限群无限群有限群的阶循环群循环群的生成元群的性质•群中的单位元是唯一的•群中每一个元素的逆元是唯一的•(消去律)对任意的，如果，或，则Gcba,,cabacbacab群在密码学中要用的重要概念•循环群及生成元•置转换见群.pdf环：设R,+,·是代数系统,R为集合,+,·为二元运算,如果(1)R,+为阿贝尔群,(2)R,·为半群,(3)乘法“·”对加法“+”适合分配律,即对任何a,b,c∈R,有a·(b+c)=(a·b)+(a·c)(a+b)·c=(a·c)+(b·c)则称R,+,·是环理解：环就是一个集合，可以在其上进行加法和乘法运算而封闭。剩余类环：剩余类集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。环中没有这样的元素，则说环中无零因子。域：若环A,+,·去掉0元的A-{0},·是交换群，则称A,+,·为域即：1)A,+是交换群2)A*,·是交换群3)运算“·”对于运算“+”是可分配的。理解：域就是一个集合，可以在其上进行加法、减法、乘法和除法运算而封闭。（a/b定义为a·b-1）有理数集合，实数集合，复数集合，这些都是无限域，在密码学中没有什么实际意义；所以考虑与整数有关的域，对密码学有实际意义。素域Fp：剩余类环Fp={[0],[1],[2],…,[p-1]}，p这素数。定理：如果(a,p)=1,p0,则ax1(modp)有唯一解xa'(modp).由定理可知，若(a,p)=1，a的模逆存在，若p为素数，更成立。即：[a]为模p的剩余类，则存在剩余类[b]，使[a]·[b]=[1]的充要条件是(a,p)=1.p为素数就更成立。从引理可得，Fp是域。有限域在密码学中很意义，主要有素域Fp（一般记为GF(p)）、二进制域GF(2n)例：GF(7)定理：域必是整环。证明：因为域是可交换含幺环，又无零因子，所以也是整环。域必是整环，但整环不一定是域。例如Z,+,·是整环。但不是域，因为对·除1外均不可逆所以Z-{0},·不是群。整环与域的区别：只差可逆性R,+,·是整环；F,+,·是域：⑴R,+是交换群。⑴F,+是交换群。⑵R,·是可交换。⑵F-{0},·是交换群。⑶“·”对“+”可分配。⑶“·”对“+”可分配。⑷无零因子有限域的两个定理密码学常用素域GF(p)或阶为2m的域GF(2m)GF(p)有限域中的计算+01234001234112340223401334012440123×01234000000101234202413303142404321(a)模5的加法(b)模5的乘法图4－1GF(5)的代数运算生成元与逆元•生成元–可证明：在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)不能表示为另两个多项式的乘积•多项式运算–加/减/乘–多项式除法: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上的有限域–系数模p–f(x)模某n次不可约多项式m(x)GF(2m)域GF(2^8)•系数模2，即只可0或1•次数最高7次，共2^8=256个多项式(剩余类)•m(x)=x^8+x^4+x^3+x+1ExampleGF(23)ExampleGF(23)•生成元与逆元•生成元：•逆元例子：GF（24）•取：GF（24）的元素：1)(4xxxf（0000）(0001)(0010)(0011)(0100)(0101)(0110)(0111)(1000)(1001)(1010)(1011)(1100)(1101)(1110)(1111)例子（续）生成元为：a=xGF(2^n)上的运算•加法–XOR•乘法–移位，加法/XOR•乘法逆元(除法)–扩展Euclid算法