离散数学25修改

1离散数学DiscreteMathematics

汪荣贵教授合肥工业大学软件学院专用课件.037/26/20261第1页CHAPTER2

TheFoundations:Algorithms,theIntegers,andMatrices7/26/20262第2页2.1Algorithms算法2.2ComplexityofAlgorithms算法复杂性2.3TheIntegersandDivision整数和除法2.4IntegersandAlgorithm整数和算法2.5ApplicationsofNumberTheory数论应用2.6Matrices矩阵学习内容7/26/20263第3页若干有用结果线性同余中国余数定理大整数计算机算术运算伪素数公钥密码学RSA加密RSA解密用RSA做公钥系统数论应用7/26/20264第4页定理1若a和b为正整数，则存在整数s和t，使gcd（a，b）=sa+tb引理1假如a，b和c为正整数，使得gcd（a，b）=1且a|bc，那么a|c引理2假如p是素数，且p|a1a2…an，其中ai为整数，则对于某个i，p|ai定理2令m为整数，a，b和c为整数。假如ac≡bc（modm）且gcd（c，m）=1，那么a≡b（modm）。若干定理7/26/20265第5页线性同余形：为ax≡b（modm）同余式m为正整数，a和b为整数，x为变量假如aa-

≡1(modm)a-称为a模m逆线性同余7/26/20266第6页定理3假如a和m为互素整数，m>1,则存在a模m逆。而且这个逆模m是唯一。（即有小于m唯一正整数a-，它是a模m逆，且a任何别模m逆均和a-模m同余1）线性同余7/26/20267第7页证：由定理1及gcd（a，m）=1知有整数s和t，使sa+tm=1于是sa+tm=1(modm)因为tm=0（modm）所以sa≡1（modm）s为a模m逆7/26/20268第8页例求3模7逆解因为gcd(3,7)=1,由定理3知存在3模7逆7=2×3+1-2×3+1×7=1说明-2是3模1一个逆线性同余7/26/20269第9页

给出一个在a和m互素条件下求a模m逆方法：

求a和m线性组合使之等于1；这一线性组合中a系数就是a模m一个逆7/26/202610第10页例线性同余3x≡4(mod7)解是什么？解从上例知道-2是3模7逆。在同余式同乘以-2得-2×3x=-2×4（mod7）因为-6≡1(mod7)且-8≡6（mod7），所以若x是解，必有x≡-8≡6（mod7）。3x≡3×6=18≡4(mod7)6,13,20,…及-1，-8，-15线性同余7/26/202611第11页例一世纪时，中国数学家孙聪问道：某物不知其数，三分之余二，五分之与三，气分之余而，此物几何？这一问题能够翻译成：求同余方程组x≡2(mod3)x≡3(mod5)x≡2(mod7)解中国余数定理7/26/202612第12页解令m=3×5×7=105，M1=m/3=35,M2=m/5=21,M3=m/7=15.2是M1=35模3逆，因为35≡2（mod3）1是M2=21模5逆，因为21≡1(mod5)1也是M3=15模7逆，因为15≡1（mod7）于是这一方程组解是那些满足下式x：x≡a1M1y1+a2M2y2+a3M3y3=2×35×2+3×21×1+2×15×1（mod105）=233≡23(mod105)23是全部解中最小正整数，被3除时余2，被5除时余3，被7除时余27/26/202613第13页定理4令m1,m2,..,mn为两两互素正整数，则同余方程组x≡a1（modm1）x≡a2（modm2）x≡an（modmn）有唯一模m=m1m2…mn解。（即有一个解x，使0≤x<m，且全部其它解均与次解模m同余）中国余数定理7/26/202614第14页证实：要结构一个适合各方程解，首先对k=1,2,…,n,令MK=m/mk,即Mk是除mk以外全部模数乘积。因为i≠k时，mi和mk没有大于1公因子，所以gcd（mk，Mk）=1。从而由定理3知有Mk模mk逆，整数yk，使得Mkyk=1（modmk）要得到适当全部方程解，令x≡a1M1y1+a2M2y2+…+anMnyn7/26/202615第15页现在证实x就是这么一个解。首先注意因为只要j≠k，就有Mj=0（modmk），x和表示式除第k项以外各项模mk均同余于0.因为Mkyk≡1（modmk），我们看到，对k=1,2,…,n,都有x≡akMkyk≡ak(modmk)所以，x是这n个同余方程同一解7/26/202616第16页假定m1,m2,…,mn是大于或等于2且两两相素整数，令m为它们乘积。依据中国余数定理能够证实每个整数a，0≤a＜m，均可唯一地用一个n元组表示，这个n元组由a被mi除余数组成，i=1，2,..,n。也就是说，a能够唯一地表示为（amodm1,amodm2,…,amodmn）大整数计算机算术运算7/26/202617第17页例7求表示小于12非负整数有序偶，其中第1分量是用3除余数，第2分量是用4除以余数解：求出每个整数用3除和用4除余数，得以下表示：0=（0，0）4=（1，0）8=（2，0）1=（1，1）5=（2，1）9=（0，1）2=（2，2）6=（0，2）10=（1，2）3=（0，3）7=（1，3）11=（2，3）7/26/202618第18页要做大整数算术运算，我们选模数m1,m2,…,mn，其中每个mi都是大于2整数，在i≠j时gcd（mi，mj）=1，且m=m1.m2٠٠٠mn大于我们要做算术运算结果大整数运算能够再表示它们n元组分量上作运算来完成，n元组分量是用大整数除以mi余数，i=1，2,…,n。一旦计算出表示大整数算术运算结果n元组表示，就能够求解n个模mi同余方程（i=1，2,…,n）找出结果值。7/26/202619第19页做大整数算术运算这一方法有几个优点首先能够用来完成通常一台计算机上不能做大整数算术运算。其次，对不一样模数计算能够并行操作，加紧计算速度7/26/202620第20页例假定在某台处理器上做100以内整数算术运算比100以上整数运算快得多，那么只要把整数表示为模两两像素100以内整数余数多元组，就能够将差不多全部整数计算限制在100以内整数上。比如，能够以99，98，97和95为模数。（这些整数没有大于1公因数）依据中国余数定理，每个小于99٠98٠97٠95=89403930非负整数均可唯一地用该整数被这四个因数除除数表示。7/26/202621第21页例：计算机系统仅考虑100以内数处理。怎样对x=123684和y=413456进行相加运算？解思绪：取四个两两互质小于100数99、98、97、95，得到x+y同余数表示。再利用中国同余定理。7/26/202622第22页解123684mod99=33123684mod98=8，123684mod97=9及123684mod95=89123684表示为（33，8，9，89）类似413456可表示为（32，92，42，16）把4元组对应分量相加，再按对应模数减小各个分量。这么可得（33，8，9，89）+（32，92，42，16）=（65mod99，100mod98，51mod97，105mod95）=（65，2，51，10）求出（65，2，51，10）表示整数，必须解同余方程组7/26/202623第23页x≡65（mod99）x

≡2（mod98）x

≡51（mod97）x

≡10（mod95）见练习29证实，537140是方程组唯一小于89403930非负解，所以537140是要求和。7/26/202624第24页大整数算术运算模数最好选择是一组行为2k-1整数，其中k为正整数，这是因为很轻易完成模这种整数二进制算术，还轻易找到两两互素一组这种整数。7/26/202625第25页Fermat判别法

假如p是素数，a与p互素，那么实际上，大约2500年前，中国古代数学家就发觉了上述结论。他们由此得出：如果,则n为素数。该判别法运算量为O(log^3n).伪素数7/26/202626第26页经过编程计算发觉，反过来结论并不成立。比如，不过341=11x34为合数！称使得成立p为伪素数。7/26/202627第27页中国古代数学相信，n为整数充分必要条件是2n-1

≡1（modn）当只要是素数该同余必成立，是正确只有同余成立，n就是素数，是不正确法国数学家费马证实了当n为素数时该同余成立伪素数7/26/202628第28页定理5（费马小定理)假如p为一个质数，a不能被p整除整数，则有ap-1

1(modp)而且对每个整数a，我们有ap≡a（modp）

7/26/202629第29页例整数341是伪素数因为他是合数341=11×31而且练习23证实了2340≡1（mod341）7/26/202630第30页信息，也就是字符串，被译成数字，然后对每个字符对应数用移位或模26仿射变换转换为另一个数。这些方法都是私钥加密系统例子公钥密码学7/26/202631第31页20世纪70年代中期，密码学中引入了公钥密码系统概念。在这么一个系统中，每个人都能够有一个众所周知加密密钥，而解密密钥是保密，只有信息预期接收人能解密。加密密钥并不能让人轻易找到解密密钥7/26/202632第32页用RSA加密法时，信息被翻译成若干整数序列。为此能够先将每个字母翻译成整数，比如用凯撒密码翻译。这些整数再分成组，各组成为一个大整数，以代表一个字母段。加密过程是先把表示普通文字（即原信息）整数M转换为表示密码文字（即加密信息）整数C，C计算公式是C=Memodn加密后信息以一段段数字形式发送给预期接收者RSA加密7/26/202633第33页例用RSA密码系统为信息STOP加密，其中p=43，q=59，所以n=43×59=2537.另外e=13.注意gcd（e，(p-1)(q-1)）=gcd(13,42×58)=1解我们把STOP字母翻译成对应等价数码，然后按4个数字一组分段。这么得到18191415，用映射C=M13mod2537为每一段加密。快速取模乘法计算得181913mod2537及141513mod2537=2182.加密后信息为208121827/26/202634第34页假如知道解密密钥d，即e模(p-1)(q-1)=1逆数，就能够很快恢复原信息。（因为gcd（e,(p-1)(q-1)=1，这一逆数一定存在。），若de≡1(mod(p-1)(q-1)),则有整数k，使de=1+k(p-1)(q-1),由此知Cd=(Me)d=(Md)e=M1+k(p-q)(q-1)RSA解密7/26/202635第35页依据费马小定理（gcd(M,p)=gcd(M,q)=1,这一关系不只在极少情况下成立），Mp-1≡1(modp)及Mq-1≡1(modq)。于是Cd≡M*(MP-1)k(q-1)≡M*1≡M(modp)及Cd≡M*(Mq-1)k(p-1)≡M*1≡M(modq)因为gcd（p,q）=1,从中国余数定理知Cd≡M(modpq)7/26/202636第36页例我们收到加密信息是09810461。假如这是用上例中RSA密码加密，解密后原信息是什么？解该信息是用RSA密码系统n=43.59和指数13加密。练习题4证实d937是13模42.58=2436逆数。我们用937作为解码指数。于是要为数字段C解密，计算P=C937mod25377/26/202637第37页为解密上述信息，用快速指数取模算法计算0981937mod2537=0704及0461937mod2537=1115.从而原信息数码形式是07041115。翻译成因为字母HELP7/26/202638第38页仿射加密方法用

表示需要加密全部明文P集合，而且假定集合

上界是A。我们总用P表示明文，用E(P)或E表示与P对应密文。(ⅰ)取大正整数M>A，以及正整数a，b，a

，使得(a,M)=1，aa

1(modM)。(1)（注意：所以，明文P满足0

P<M。）(ⅱ)加密：对于明文P，计算E

aP

b(modM)，0

E<M。(2)(ⅲ)解密：对于密文E，计算P0

a

(E

b)(modM)，0

P0<M，(3)由式(3)，式(2)和式(1)，我们得到P0

a

(E

b)

a

((aP

b)

b)

aa

P

P(modM)因为0

P<M，0

P0<M，所以，由上式得到P0=P。7/26/202639第39页例已知明文所使用符号只是26个英文字母a，b，

，y，z，它们分别与整数00，01，

，24，25对应，又知道使用公式E

P

b(mod26)，0

E<26(4)对每个符号加密。已经知道明文字母e与密文字母u对应，试求出解密方法。解将已知e

u以及e

04，u

20代入式(4)，得到20

4

b(mod26)，所以b

16(mod26)，再由式(4)得到P

E

16

E

10(mod26)，0

P<26，这就是解密方法，也能够用下表说明：7/26/202640第40页EabcdefghijklmPklmnopqrstuvwEnopqrstuvwxyzPxyzabcdefghij7/26/202641第41页

普通地，对于由式(2)定义仿射加密方法，只要知道两对（不一样）相对应明文和密文P1，E1与P2，E2，就能够求出解密方法。实际上，由式(2)及已知对应关系，得到E1

aP1

b(modM)，E2

aP2

b(modM)，（4）所以E2

E1

a(P2

P1)(modM)。以x

ai(modM)，0

ai<M，1

i

r

表示同余方程x(P2

P1)

E2

E1(modM)全部解，而且记bi

E1–aiP1(modM)，0

bi<M，则ai与bi（1

i

r）就可能是式(2)中所使用a和b。

仿射解密方法7/26/202642第42页当(P2

P1,M)=1时，这么ai与bi只有一组，当(P2

P1,M)>1时，为了确定出正确a与b，首先，利用(a，M)=1删去一些ai与bi，