数论相关基础知识课件.ppt

《数论相关基础知识课件.ppt》由会员分享，可在线阅读，更多相关《数论相关基础知识课件.ppt（34页珍藏版）》请在三一办公上搜索。

1、数论相关基础知识,提纲,群环域模运算欧几里德算法有限域GF(p)多项式运算有限域GF(2n),Abstract Algebra,Algebraic structure Semigroupclosure封闭性,associative 结合律Groupclosure,associativity,identity单位元,inverse逆元Ring+:associativity,commutativity交换律,identity,inverse 0*:associativity,distributivity分配律Fielda ringmultiplicative inverse 乘法逆元Lattice

2、,Boolean,4.1 群环域,群 Group集合，元素二元运算 封闭性、结合律单位元、逆元有限群、无限群交换群（Abel）循环群生成元,环 Ring,环R二元运算:加法+、乘法(R,+)是交换群乘法封闭性、乘法结合律分配律 a(b+c)=ab+ac交换环乘法交换律整环（交换环且）乘法单位元1无零因子:ab=0 a=0或b=0,域 Field,域FF是整环存在乘法逆元(0除外)除法定义:a/b=a(b-1)有理数域、实数域、复数域有限域,Group Ring Field,域相关概念及定理,域的特征-任意元素a的n次累计和为0的最小的n；域的特征要么是素数，要么是0(没有)；素域：没有非0真子

3、域的域；有限域的阶是pn（其中p是素数）；有限域的乘法群是循环群；,可逆在加/解密中的重要性,加密的操作对象是比特分组，通常被看作整数加密是对整数的变换。这种变换必须能恢复(解密时)，即可逆。如果加密是乘法，则解密就是除法，而域上正好有除法-乘法逆元。对于8bits字节，希望Z256是域，但它不是；于是转而寻求GF(28)，它是域。AES的S盒是基于模2系数的模某8次不可约多项式的剩余类。,4.2 模运算,模运算即求余数（C语言中的运算符）x mod na其中0an,且有证书k使knax如 532；871；16124同余关系若x mod ny mod n a，则说x和y是模n同余的，记xy m

4、od n如136 mod 7 207 mod 13因子0 mod 倍数,模运算性质,ab mod n(a mod nb mod n)mod nab mod n(a mod nb mod n)mod nab mod n(a mod nb mod n)mod n其他性质交换律结合律分配律,剩余集,模n完全剩余集给定了数n，则所有的整数都以同余的形式映射到模n的余数的集合上Zn0，1，2，3，n-1模n的运算可定义在该集合上模n简化剩余集只保留和n互素的元素（不要0）Z12*1，5，7，11模素数q的简化剩余集Zq*1，2，q-1,模n逆元,讨论在模n余数集上进行加法逆元如果ab0 mod n，则a

5、和b互为加法逆元Zn中有：0,0 1,n-1 2,n-2 n/2,n/2乘法逆元如果ab1 mod n，则a、b互为乘法逆元如6201 mod 119,一次同余式,并不是每个元素都有乘法逆元定理：axb mod n有解(a,n)|b推论：ax1 mod n有解 IFF(a,n)|1因此，如果n是素数p，就都有解a存在模n逆元 a和n互素，即(a,n)=1如果n是某素数p，则除了0元都有逆元？求a的模n逆元：使用扩展Euclid算法,（Zn,）是环,（Zn,）是环a Zn有乘法逆元 IFF gcd(a,n)=1其个数定义为(n)它们构成乘法交换群Zn*（Zn*,）是域Zp是域（除0元外都有乘法逆

6、）Zp*=1,2,3,p-1，(n)=p-1其每个非0元素都和p互素，即有逆元,4.3 欧几里德算法(Euclid),整除、倍数、因子公因子、最大公因子 gcd()Greatest Common Divisor最大公因子定理(ab)gcd(a,b)=gcd(b,a mod b)求最大公因子辗转相除法（欧几里德算法）gcd(a,b)=gcd(b%a,a%b),GCD(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(9

7、4,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),函数gcd(a,b),int gcd(int a,int b)if(a=0)|(b=0)return a+b;elsereturn gcd(a%b,b%a);,4.4 有限域GF(p),域，无限域有限域，又叫Galoris域有限域的阶都有pn的形式阶为p的有限域记为GF(p)唯一性(Isomorp

8、hism)在同构意义下，某阶有限域只有一个GF(p)：(Zp,+,x)GF(pm)：系数在Zp上的模某不可约多项式的多项式域GF(2n)：p=2,GF(p)：(Zp,+,x),逆元由于p是素数，所以除了0外都有逆元GF(p=2)：(Z2,+,x)GF(p=7)：(Z7,+,x)*GF(p=8)：(Z8,+,x)不是域,求逆元：扩展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

9、r0，得tm逆r1的逆,扩展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 80

10、22922(-1269)-2(4269)22 即-9269 291227(4269)-1(-9269)7 即 13269 22371(-9269)-3(13269)1即-48269 得301,函数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;,4.5 多项式运算,多项式 一元n次整数域多项式运

11、算加，减乘例子：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+2,-,除法: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的多项式,多项式环,系数是域F的多项式，构成环系数是Zn的多项式环系数是Zp的多项式环在Z2上的多项式环，在计算机上操作时有优势加法，即XOR乘法，即AND构造GF(pn)从环到域,构造G

12、F(pn),系数在Zp上的n-1次多项式f(x)集合S共有pn个(S,)构成有限域GF(pn)需要某n次不可约多项式m(x)使用模m(x)的多项式加法和乘法从GF(pn)到GF(2n)到GF(28)in AES,Example GF(23),-,4.6 有限域GF(2n),系数模2，即只可0或1若次数最高7次，共28=256个多项式(剩余类)加法XOR乘法移位，加法/XOR乘法逆元(除法)扩展Euclid算法,GF(23)上的运算（in AES）,m(x)=x8+x4+x3+x+1运算表：8x8 AES,Terms,abelian groupassociativecoefficient set

13、commutativecommutative ringcyclic groupdivisorEuclidean algorithmfieldfinite groupfinite ringfinite fieldgeneratorgreatest common divisorgroupidentity elementinfinite groupinfinite ringinfinite fieldintegral domaininverse elementirreducible polynomialmodular arithmeticmodular polynomial arithmeticmodulo operatormodulusmonic polynomialorderpolynomialpolynomial arithmeticpolynomial ringprime numberprime polynomialrelatively primeresiduering,小结,域结构在密码学上有重要应用。另外，格结构也越来越表现出重要用途。,Q&A,