《信息保障与安全》05-数论入门.ppt

《《信息保障与安全》05-数论入门.ppt》由会员分享，可在线阅读，更多相关《《信息保障与安全》05-数论入门.ppt（74页珍藏版）》请在三一办公上搜索。

1、数论入门,2023/9/17,华中农业大学信息学院,2,0 整数,整数：整数集,-3,-2,-1,0,1,2,3,记为Z。整除：设a,b为整数。若存在某个整数c,使得b=ac,则称a整除b（等价地，称a是b的一个因子，或者说a为b的一个因子）。若a整数b，则记为 a|b。例如：,2023/9/17,华中农业大学信息学院,3,0 整数,整除的基本性质：对所有的整数a，b，c，有以下正确结论：a|a若 a|b 且 b|c，则 a|c。若 a|b 且 a|c，则对于所有的整数x，y，有a|（bx+cy）。若 a|b 且 b|a，则 a=+b 或 a=-b。例如,2023/9/17,华中农业大学信息学

2、院,4,0 整数,整数的整除算法若a，b均为整数，且b=1,则按照a除以b的普通长除法可以找到整数q（商）和r余数，使得：a=qb+r，其中0=rb.且q和r唯一。除法所得余数记为a mod b，商记为a div b。例如,2023/9/17,华中农业大学信息学院,5,0 整数,整数模n设n为一整数。若a，b为整数，则称a与b是模n同余的，记为a b（mod n）。同余的性质：对所有的整数a，a1，b，b1，c有a b（mod n）当且仅当a与b被n除时所得的余数相同。自反性：a a（mod n）对称性：若 a b（mod n），则b a（mod n）传递性：若 a b（mod n），b c（

3、mod n），则a c（mod n）若 a a1（mod n），b b1（mod n），则 a+b a1+b1（mod n），且 a b a1 b1（mod n）,2023/9/17,华中农业大学信息学院,6,0 整数,整数的乘法逆元设a为整数，若存在整数x，使得ax 1（mod n），则称x为a的模n的乘法逆元。若x存在，则它是唯一的，此时称a为可逆的，a的逆元记为a-1。设a为整数，则a可逆当且仅当 gcd（a，n）=1。,2023/9/17,华中农业大学信息学院,7,2023/9/17,7,乘法逆元,若ab1 mod n，则a和b互为mod n的乘法逆元。例：2*4 1 mod 7，则2

4、是4模7的乘法逆元 或 4是2模7的乘法逆元。求乘法的逆元用欧几里得扩展算法。,2023/9/17,华中农业大学信息学院,8,欧几里得扩展算法EUCLID(m,b)1.(A1,A2,A3)(1,0,m);(B1,B2,B3)(0,1,b)2.if B3=0return A3=gcd(m,b);no inverse3.if B3=1 return B3=gcd(m,b);B2=b1 mod m4.Q=5.(T1,T2,T3)=(A1 Q B1,A2 Q B2,A3 Q B3)6.(A1,A2,A3)=(B1,B2,B3)7.(B1,B2,B3)=(T1,T2,T3)8.goto 2,乘法逆元,2

5、023/9/17,华中农业大学信息学院,9,乘法逆元,gcd(1759,550)=1,Abstract Algebra,Algebraic structure Semigroupclosure封闭性,associative 结合律Groupclosure,associativity,identity单位元,inverse逆元Ring+:associativity,commutativity交换律,identity,inverse 0*:associativity,distributivity分配律Fielda ringmultiplicative inverse 乘法逆元Lattice,Boo

6、lean,群：群G有时记为G,是一个二元运算的集合，这个二元运算表示为（操作符 可以指加法，乘法或者其他的数学运算符），G中的每一个序偶(a,b)通过运算生成G中的元素(ab)，满足以下公理：,chap4 有限域,(A1)封闭性:若a和b都属于G，a b也属于G(A2)结合律：对G中任意元素a,b,c，都有a(b c)=(a b)c成立。(A3)单位元：G中存在一个元素e，对于G中任意元素a，都有a e=ea=a成立。(A4)逆元：对于G中任意元素a，G中都存在一个元素a，使得a a=a a=e成立。,4.1 群环域,群 Group集合，元素二元运算 封闭性、结合律单位元、逆元有限群、无限群交

7、换群（Abel）循环群生成元,环 Ring,环R二元运算:加法+、乘法(R,+)是交换群乘法封闭性、乘法结合律分配律 a(b+c)=ab+ac交换环乘法交换律整环（交换环且）乘法单位元1无零因子:ab=0 a=0或b=0,域 Field,域FF是整环存在乘法逆元(0除外)除法定义:a/b=a(b-1)有理数域、实数域、复数域有限域,chap4 有限域,(A1)加法封闭性(A2)加法结合律(A3)加法单位元(A4)加法逆元,(M4)乘法交换律,(M1)乘法封闭性(M2)乘法结合律(M3)分配率,(M7)乘法逆元,(M5)乘法单位元(M6)无零因子,(A5)加法交换律,群,可交换群,环,可交换环,

8、整环,域,Group Ring Field,域相关概念及定理,域的特征-任意元素a的n次累计和为0的最小的n；域的特征要么是素数，要么是0(没有)；素域：没有非0真子域的域；有限域的阶是pn（其中p是素数）；有限域的乘法群是循环群；,可逆在加/解密中的重要性,加密的操作对象是比特分组，通常被看作整数加密是对整数的变换。这种变换必须能恢复(解密时)，即可逆。如果加密是乘法，则解密就是除法，而域上正好有除法-乘法逆元。对于8bits字节，希望Z256是域，但它不是；于是转而寻求GF(28)，它是域。AES的S盒是基于模2系数的模某8次不可约多项式的剩余类。,4.2 模运算,模运算即求余数（C语言中

9、的运算符）x mod na其中0an,且有证书k使knax如 532；871；16124同余关系若x mod ny mod n a，则说x和y是模n同余的，记xy mod 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简化剩余

10、集只保留和n互素的元素（不要0）Z12*1，5，7，11模素数q的简化剩余集Zq*1，2，q-1,模n逆元,讨论在模n余数集上进行加法逆元如果ab0 mod n，则a和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算法

11、,（Zn,）是环,（Zn,）是环a Zn有乘法逆元 IFF gcd(a,n)=1其个数定义为(n)它们构成乘法交换群Zn*（Zn*,）是域Zp是域（除0元外都有乘法逆）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(

12、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),函数gcd(a,b),int gcd(int a,int b)if(a=0)|(b=0)return a+b;elsereturn

13、gcd(a%b,b%a);,4.4 有限域GF(p),域，无限域有限域，又叫Galoris域有限域的阶都有pn的形式阶为p的有限域记为GF(p)唯一性(Isomorphism)在同构意义下，某阶有限域只有一个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)r1

14、q2r2r3r2q3r3r4rm-2qm-1rm-1rm(1)rm-1qmrm rm+1(0)记t0 rm+1，t1rm，依tjtj-2 qi-1 tj-1 mod 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

15、 即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 得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

16、;r1=r;b1=b;while(r1);if(r=0)return 0;if(b0)b+=m;return b;,4.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+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的多项式,多项式环,系

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

18、（in AES）,m(x)=x8+x4+x3+x+1运算表：8x8 AES,Terms,abelian groupassociativecoefficient setcommutativecommutative ringcyclic groupdivisorEuclidean algorithmfieldfinite groupfinite ringfinite fieldgeneratorgreatest common divisorgroupidentity elementinfinite groupinfinite ringinfinite fieldintegral domaininv

19、erse elementirreducible polynomialmodular arithmeticmodular polynomial arithmeticmodulo operatormodulusmonic polynomialorderpolynomialpolynomial arithmeticpolynomial ringprime numberprime polynomialrelatively primeresiduering,小结,域结构在密码学上有重要应用。另外，格结构也越来越表现出重要用途。,2023/9/17,华中农业大学信息学院,43,1 素数,数论主要关心的是素

20、数整数p 1是素数，当且仅当它只有因子1和 p。素数不能写作其它数的乘积 1是素数，但一般对它没兴趣 例如：2,3,5,7是素数，4,6,8,9,10 不是素数200以内的素数:2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199,2023/9/17,华中农业大学信息学院,44,2023/9/17,华中农业大学信息学院,45,素数的个数,20

21、23/9/17,华中农业大学信息学院,46,素因子分解,算数基本定理：任意整数 a 1 都可以唯一地因子分解为a=p1a1p2a2ptat，其中，pi 均是素数，且p10如.91=7 x 13;3600=24 x 32 x 52 确定一个大数的素因子分解不是一件容易的事,2023/9/17,华中农业大学信息学院,47,互素和最大公因子,两个数 a,b 互素，如果它们没有除1以外的公因子 如(8,15)=1 最大公因子如:300=22 x 31 x 52 18=21 x 32 因此 GCD(18,300)=21 x 31 x 50=6,2023/9/17,华中农业大学信息学院,48,2 Ferm

22、at定理和Euler定理,ap-1 1(mod p)p是素数，gcd(a,p)=1Fermat小定理ap a(mod p)p是素数，a是任意整数在公钥密码中很有用,Fermat 定理,2023/9/17,华中农业大学信息学院,49,小于n且与n互素的正整数的个数 如 n=10,0,1,2,3,4,5,6,7,8,9，1,3,7,9(10)=4素数 p(p)=p-1 素数p,q，有(pq)=(p-1)x(q-1)如：(37)=36(21)=(31)x(71)=2 x 6=12约定：(1)=1,Euler函数(n),2023/9/17,华中农业大学信息学院,50,定 理：设 n=p1e1 p2e2

23、 prer，pi pj,pi为素数，ei1,则(n)=n(1-p1-1)(1-p2-1)(1-pr-1),例如：12=22*3(12)=12*(1-2-1)*(1-3-1)=4,2023/9/17,华中农业大学信息学院,51,2023/9/17,华中农业大学信息学院,52,a(n)1(mod n)对任意 a,n，gcd(a,n)=1另一种表示：a(n)+1 a(mod n)对任意 a,n如：a=3;n=10;(10)=4;则 34=81 1 mod 10a=2;n=11;(11)=10;则 210=1024 1 mod 11Fermat定理是Euler定理的推论，或者说，Euler定理是Fer

24、mat定理的更一般化形式。,Euler 定 理,2023/9/17,华中农业大学信息学院,53,与RSA有关的结果两个素数 p 和 q，整数m 和 n，n=pq,0 m n,则有 m(n)+1=m(p-1)(q-1)+1 m(mod n)另一种表示：mk(n)+1 m(mod n),Euler 定 理,2023/9/17,华中农业大学信息学院,54,3 素性测试,常常需要找到大的素数 试除法 例如，用小于该数平方根的所有数去试除对较小数有效基于素数性质的有选择的统计方法 所有素数均应满足素数的性质 但某些合数（可称作伪素数）也满足素数的性质确定素性的测试,2023/9/17,华中农业大学信息学

25、院,55,Miller Rabin 算法,基于Fermat定理算法如下:TEST(n)is:1.找出整数 k,q,其中k 0,q 是奇数，使得(n1)=2kq 2.随机选择整数 a,1 a n1 3.if aq mod n=1 then 返回(“不确定);4.for j=0 to k 1 do 5.if(a2jq mod n=n-1)then 返回(“不确定)6.return(“合数),2023/9/17,华中农业大学信息学院,56,概率方面的考虑,如果Miller-Rabin测试返回“合数”，则该数一定不是素数；返回“不确定”，则该数可能是素数，也可能是伪素数遇到伪素数的概率 0.99999

26、9,2023/9/17,华中农业大学信息学院,57,素数的分布,数论中的素数定理可知：n附近的素数分布情况为，平均每 ln(n)个整数中有一个素数偶数和5的倍数，都不是素数，所以只需要测试 0.4ln(n)次如，要找2200左右的素数，则约需55次测试这里只是平均意义上的结论有时素数分布很密，有时很松,2023/9/17,华中农业大学信息学院,58,4 中国剩余定理Chinese Remainder Theorem,用于加速模运算 某一范围内的整数可通过它对两两互素的整数取模所得的余数来重构 使得非常大的数对M的模运算转化到更小的数上来进行运算,2023/9/17,华中农业大学信息学院,59,

27、中国剩余定理,可以多种方式实现CRT计算 A(mod M)首先依次计算所有 ai=A mod mi 确定常数 ci,其中 Mi=M/mi用下列式子得到结果:,2023/9/17,华中农业大学信息学院,60,中国剩余定理,2023/9/17,华中农业大学信息学院,61,应 用 举 例,计 算：120523=1651*73=(973+678)*73？(mod 1813)已知1813=37*49 且（37，49）=1,2023/9/17,华中农业大学信息学院,62,M=m1*m2=37*49(37,49)=1973可用较小的两个模数37和49重构，表示为（11，42）678可表示为（12，41）则1

28、651=973+678就可表示为（11+12 mod 37,42+41 mod 49）=(23,34)则120523=1651*73就可表示为（23*73 mod 37,34*73 mod 49）=(14,32),应 用 举 例,2023/9/17,华中农业大学信息学院,63,应用举例,孙子算经：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰二十三,设所求物数为 X,则 X 2（mod 3),X 3（mod 5),X 2（mod 7),术曰：三三数剩一置几何？答曰：五乘七乘二得之一百四。五五数剩一复置几何？答曰，三乘七得之二十一是也。七七数剩一又置几何？答曰，三乘五得

29、之十五是也。三乘五乘七，又得一百零五。,到了明代，数学家程大位用诗歌概括了这一算法:三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。这首诗的意思是：用3除所得的余数乘上70，加上用5除所得余数乘以21，再加上用7除所得的 余数乘上15，结果大于105就减去105的倍数，这样就知道所求的数了。,2023/9/17,华中农业大学信息学院,66,中国剩余定理,2023/9/17,华中农业大学信息学院,67,5.1 本原根,5 离散对数Discrete Logarithms,2023/9/17,华中农业大学信息学院,68,5.1 本原根,a(n)mod n=1 am=1(mod n),

30、GCD(a,n)=1一定存在，因为m=(n)，（(n)是可能的最高指数）m不一定最小一旦到达m,将会产生循环。最小的m，成为a的阶。如果一个数a的阶为(n)，则称a为n的本原根若p是素数,a是p的本原根，则a1,a2,a3,ap-1 是模p各不相同的；并不是所有整数模n都有本原根。只有n是形为2，4，p和2 p的整数才有本原根，其中p是奇素数，是正整数。,2023/9/17,华中农业大学信息学院,69,2023/9/17,华中农业大学信息学院,70,求 x，以满足 y=gx(mod p)可以写作 x=logg y(mod p)如果g是p的本原根，则x一定存在；否则，不一定存在,例如.x=log

31、3 4 mod 13 无解 x=log2 3 mod 13=4 指数运算相对容易，求离散对数问题是困难的,5.2 离散对数,2023/9/17,华中农业大学信息学院,71,定义：若m 1,(a,m)=1,则使得同余式 ai 1(mod m)成立的最小正整数i，叫做a对模m的离散对数。指数一定是欧拉函数的因子对任意整数b和模数p的本原根a，有唯一的幂i，使得b ai mod p,其中0 i p-1该指数i称为以a为底模p的离散对数，记为 dloga,p(b)离散对数不仅与模有关，而且与本原根有关。例如：2对模7的指数是3，对模11的指数是10，所以，2是模11的一个本原根，而不是模7的本原根；dlog2,9(8)=3,2023/9/17,华中农业大学信息学院,72,2023/9/17,西安电子科技大学 计算机学院,73,小 结,素数Fermat和Euler定理欧拉函数(n)素性测试（Miller-Rabin算法）中国剩余定理离散对数,2023/9/17,华中农业大学信息学院,74,谢 谢！,