離散數(shù)學(xué)25修改

1、1Discrete Mathematics 汪榮貴 教授2010.038/28/20221CHAPTER 2 The Foundations: Algorithms, the Integers ,and Matrices8/28/202222.1 Algorithms算法2.2 Complexity of Algorithms算法的復(fù)雜性2.3 The Integers and Division整數(shù)和除法2.4 Integers and Algorithm整數(shù)和算法2.5 Applications of Number Theory數(shù)論的應(yīng)用2.6 Matrices矩陣 學(xué)習(xí)內(nèi)容8/28/202

2、23若干有用的結(jié)果線性同余中國余數(shù)定理大整數(shù)的計(jì)算機(jī)算術(shù)運(yùn)算偽素?cái)?shù)公鑰密碼學(xué)RSA加密RSA解密用RSA做公鑰系統(tǒng)數(shù)論應(yīng)用8/28/20224定理1 若a和b為正整數(shù)，則存在整數(shù)s和t，使gcd（a，b）=sa+tb引理1 如果a，b和c為正整數(shù)，使得gcd（a，b）=1且a|bc，那么a|c引理2 如果p是素?cái)?shù)，且p|a1a2an，其中ai為整數(shù)，則對(duì)于某個(gè)i，p|ai定理2 令m為整數(shù)，a，b和c為整數(shù)。如果acbc（mod m）且gcd（c，m）=1，那么ab（mod m）。 若干定理8/28/20225線性同余形： 為 axb（mod m）的同余式m為正整數(shù)，a和b為整數(shù)，x為變量如果

3、aa- 1(mod m) a- 稱為a的模m逆 線性同余8/28/20226定理3 如果a和m為互素的整數(shù)，m1,則存在a的模m逆。而且這個(gè)逆模m是唯一的。（即有小于m的唯一正整數(shù) a- ，它是a的模m逆，且a的任何別的模m逆均和a- 模m同余1） 線性同余8/28/20227證：由定理1及gcd（a，m）=1知有整數(shù)s和t，使 sa+tm=1于是 sa+tm=1(mod m)由于 tm=0（mod m）所以sa 1（mod m） s為a的模m逆8/28/20228例 求3模7的逆解 由于gcd(3,7)=1,由定理3知存在3模7的逆 7=23+1 -23+17=1說明-2是3模1的一個(gè)逆 線

4、性同余8/28/20229 給出一個(gè)在a和m互素的條件下求a的模m逆的方法： 求a和m的線性組合使之等于1；這一線性組合中a的系數(shù)就是a模m的一個(gè)逆8/28/202210例 線性同余3x4(mod 7)的解是什么？解 從上例知道-2是3模7的逆。在同余式同乘以-2得-23x=-24（mod 7）因?yàn)?61(mod 7)且-8 6（mod 7），所以若x是解，必有x -8 6（mod 7）。3x 36=18 4(mod 7)6,13,20,及-1，-8，-15 線性同余8/28/202211例 一世紀(jì)時(shí)，中國數(shù)學(xué)家孫聰問道：某物不知其數(shù)，三分之余二，五分之與三，氣分之余而，此物幾何？這一問題可以

5、翻譯成：求同余方程組x 2(mod 3)x 3(mod 5)x 2(mod 7) 的解 中國余數(shù)定理8/28/202212解 令m=357=105，M1=m/3=35,M2=m/5=21,M3=m/7=15.2是M1=35的模3逆，因?yàn)?52（mod 3）1是M2=21的模5的逆，因?yàn)?1 1(mod 5)1也是M3=15的模7逆，因?yàn)?5 1（mod 7）于是這一方程組的解是那些滿足下式的x：xa1M1y1+a2M2y2+a3M3y3=2352+3211+2151（mod 105）=233 23(mod 105)23是所有解中最小正整數(shù)，被3除時(shí)余2，被5除時(shí)余3，被7除時(shí)余28/28/20

6、2213定理4 令m1,m2,.,mn為兩兩互素的正整數(shù)，則同余方程組x a1（mod m1）x a2（mod m2）x an（mod mn）有唯一的模m=m1m2mn的解。（即有一個(gè)解x，使0 x A，以及正整數(shù)a，b，a ，使得(a, M ) = 1，aa 1 (mod M )。 (1)（注意：因此，明文P滿足0 P M。）() 加密：對(duì)于明文P，計(jì)算E aP b (mod M)，0 E M。 (2)() 解密：對(duì)于密文E，計(jì)算P0 a (E b) (mod M)，0 P0 M， (3)由式(3)，式(2)和式(1)，我們得到P0 a (E b) a(aP b) b) aaP P(mod

7、M)由于0 P M，0 P0 M，所以，由上式得到P0 = P。8/28/202239例 已知明文所使用的符號(hào)只是26個(gè)英文字母a，b，y，z，它們分別與整數(shù)00，01，24，25對(duì)應(yīng)，又知道使用公式E P b (mod 26)，0 E 26 (4)對(duì)每個(gè)符號(hào)加密。已經(jīng)知道明文字母e與密文字母u對(duì)應(yīng)，試求出解密方法。解 將已知的e u以及e 04，u 20代入式(4)，得到20 4 b (mod 26)，所以b 16 (mod 26)，再由式(4)得到P E 16 E 10 (mod 26)，0 P 26，這就是解密方法，也可以用下表說明：8/28/202240EabcdefghijklmPk

8、lmnopqrstuvwEnopqrstuvwxyzPxyzabcdefghij8/28/202241 一般地，對(duì)于由式(2)定義的仿射加密方法，只要知道兩對(duì)（不同的）相對(duì)應(yīng)的明文和密文P1，E1與P2，E2，就可以求出解密方法。事實(shí)上，由式(2)及已知的對(duì)應(yīng)關(guān)系，得到 E1 aP1 b (mod M)， E2 aP2 b (mod M)， （4）所以 E2 E1 a(P2 P1) (mod M)。以x ai (mod M)，0 ai M，1 i r 表示同余方程x(P2 P1) E2 E1 (mod M)的全部解，并且記bi E1 aiP1 (mod M)，0 bi 1時(shí)，為了確定出正確的a

9、與b， 首先，利用(a，M) = 1刪去某些ai與bi， 其次，用它們驗(yàn)證式（4）是否成立，并用它們?cè)囎g部分密文，就可以確定正確的a與b。將確定的a，b代入式(3)，就得到解密公式。8/28/202243例 已知明文由26個(gè)英文字母a，b，y，z（分別與00，01，24，25對(duì)應(yīng)）及符號(hào)“！”和“？”（分別與26和27對(duì)應(yīng)）組成，用這28個(gè)符號(hào)寫成的正常英文中，出現(xiàn)頻率最高的依次是！，e與t。在對(duì)一組密文做了統(tǒng)計(jì)分析之后，發(fā)現(xiàn)密文中出現(xiàn)頻率最高的三個(gè)符號(hào)依次是b，?與i，試求解密公式。8/28/202244解 設(shè)解密公式為P a E b (mod 28)，0 P 28，則由已知的符號(hào)與數(shù)字的對(duì)應(yīng)關(guān)系，比較出現(xiàn)頻率的高低，可以假定“!”與“e”分別對(duì)應(yīng)著“b”與“?”，于是26 a 1 b (mod 28)，4 a 27 b (mod 28)，將兩式相減，得到26a 22 (mod 28)。這個(gè)同余方程有兩個(gè)解：a1 11 (mod 28)，a2 25 (mod 28)，相應(yīng)的，b1 15 (mod 28)，b2 1 (mod 28)。8/28/202245這樣，得到了兩個(gè)可能的解密方法：() P 11E 15 (mod 28)，0