数论相关基础知识.ppt
B数论相关基础知识B提纲群环域模运算欧几里德算法有限域GF(p)多项式运算有限域GF(2n)BAbstract AlgebraAlgebraic structure Semigroupclosure封闭性,associative 结合律Groupclosure,associativity,identity单位元,inverse逆元Ring+:associativity,commutativity交换律,identity,inverse 0*:associativity,distributivity分配律Fielda ringmultiplicative inverse 乘法逆元Lattice,BooleanB4.1 群环域群 Group集合，元素二元运算 封闭性、结合律单位元、逆元有限群、无限群交换群（Abel）循环群生成元B环 Ring环R二元运算:加法+、乘法(R,+)是交换群乘法封闭性、乘法结合律分配律 a(b+c)=ab+ac交换环乘法交换律整环（交换环且）乘法单位元1无零因子:ab=0 a=0或b=0B域 Field域FF是整环存在乘法逆元(0除外)除法定义:a/b=a(b-1)有理数域、实数域、复数域有限域BGroup Ring FieldB域相关概念及定理域的特征 -任意元素a的n次累计和为0的最小的n；域的特征要么是素数，要么是0(没有)；素域：没有非0真子域的域；有限域的阶是pn（其中p是素数）；有限域的乘法群是循环群；B可逆在加/解密中的重要性加密的操作对象是比特分组，通常被看作整数加密是对整数的变换。这种变换必须能恢复(解密时)，即可逆。如果加密是乘法，则解密就是除法，而域上正好有除法-乘法逆元。对于8bits字节，希望Z256是域，但它不是；于是转而寻求GF(28)，它是域。AES的S盒是基于模2系数的模某8次不可约多项式的剩余类。B4.2 模运算模运算即求余数（C语言中的运算符）x mod na其中0ab)gcd(a,b)=gcd(b,a mod b)求最大公因子辗转相除法（欧几里德算法）gcd(a,b)=gcd(b%a,a%b)BGCD(1970,1066)1970=1 x 1066+904 gcd(1066,904)1066=1 x 904+162 gcd(904,162)904=5 x 162+94 gcd(162,94)162=1 x 94+68 gcd(94,68)94=1 x 68+26 gcd(68,26)68=2 x 26+16 gcd(26,16)26=1 x 16+10 gcd(16,10)16=1 x 10+6 gcd(10,6)10=1 x 6+4 gcd(6,4)6=1 x 4+2 gcd(4,2)4=2 x 2+0 gcd(2,0)B函数gcd(a,b)int gcd(int a,int b)if(a=0)|(b=0)return a+b;elsereturn gcd(a%b,b%a);B4.4 有限域GF(p)域，无限域有限域，又叫Galoris域有限域的阶都有pn的形式阶为p的有限域记为GF(p)唯一性(Isomorphism)在同构意义下，某阶有限域只有一个GF(p)：(Zp,+,x)GF(pm)：系数在Zp上的模某不可约多项式的多项式域GF(2n)：p=2BGF(p)：(Zp,+,x)逆元由于p是素数，所以除了0外都有逆元GF(p=2)：(Z2,+,x)GF(p=7)：(Z7,+,x)*GF(p=8)：(Z8,+,x)不是域B求逆元：扩展Euclid算法扩展扩展Euclid算法算法做欧几里德算法的计算序列做欧几里德算法的计算序列r0q1r1r2 (令令r0n，r1a)r1q2r2r3r2q3r3r4rm-2qm-1rm-1rm (1)rm-1qmrm rm+1 (0)记记 t0 rm+1，t1rm，依依 tjtj-2 qi-1 tj-1 mod r0，得得 tm逆逆 r1的逆的逆B扩展Euclid算法举例22 1 mod 31311229-122 9 即 3022 9 mod 312229422-2(3022)4 即 322 4 mod 31 92413022-2(322)1即2422 1 mod 3128 1 mod 757522819-22819 即 732819 mod 7528119928-1(7328)9 即 328 9 mod 7519291 (7328)-2(338)1 即6728 1 mod75269 1 mod 349349126980 -126980 即 -126926938029 269-3(-1269)29 即 4269 8022922 (-1269)-2(4269)22 即-9269 291227 (4269)-1(-9269)7 即 13269 22371 (-9269)-3(13269)1即-48269 得301B函数reverse()int reverse(int a,int m)int b,b1=1,b2=0;/逆元int r,r1=a,r2=m;/do r=r2%r1;/y-kx=rb=(b2-(r2/r1)*b1)%m;r2=r1;b2=b1;r1=r;b1=b;while(r1);if(r=0)return 0;if(b0)b+=m;return b;B4.5 多项式运算多项式 一元n次整数域多项式运算加，减乘例子：f(x)=x3+x2+2，g(x)=x2-x+1f(x)+g(x)=x3+2x2-x+3f(x)g(x)=x3+x+1f(x)x g(x)=x5+3x2-2x+2B-除法: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)不可约多项式(素多项式,既约多项式)g(x)不能表示为另两个多项式的乘积关于系数Zn的多项式B多项式环系数是域F的多项式，构成环系数是Zn的多项式环系数是Zp的多项式环在Z2上的多项式环，在计算机上操作时有优势加法，即XOR乘法，即AND构造GF(pn)从环到域B构造GF(pn)系数在Zp上的n-1次多项式f(x)集合S共有pn个(S,)构成有限域GF(pn)需要某n次不可约多项式m(x)使用模m(x)的多项式加法和乘法从GF(pn)到GF(2n)到GF(28)in AESBExample GF(23)B-B4.6 有限域GF(2n)系数模2，即只可0或1若次数最高7次，共28=256个多项式(剩余类)加法XOR乘法移位，加法/XOR乘法逆元(除法)扩展Euclid算法BGF(23)上的运算（in AES）m(x)=x8+x4+x3+x+1运算表：8x8 AES BTermsabelian groupassociativecoefficient setcommutativecommutative ringcyclic groupdivisorEuclidean algorithm fieldfinite groupfinite ringfinite fieldgeneratorgreatest common divisorgroupidentity elementinfinite groupinfinite ringinfinite fieldintegral domaininverse elementirreducible polynomialmodular arithmeticmodular polynomial arithmeticmodulo operator modulusmonic polynomialorderpolynomialpolynomial arithmeticpolynomial ringprime numberprime polynomialrelatively primeresidueringB小结域结构在密码学上有重要应用。另外，格结构也越来越表现出重要用途。BQ&A
