第2章 信息安全數(shù)學(xué)基礎(chǔ)(數(shù)論)

1、2021-12-15編輯ppt電子科技大學(xué)電子科技大學(xué) 計算機科學(xué)與工程學(xué)院計算機科學(xué)與工程學(xué)院 計算系統(tǒng)與網(wǎng)絡(luò)安全計算系統(tǒng)與網(wǎng)絡(luò)安全Computer System and Network SecurityComputer System and Network Security2021-12-15編輯pptl子夏曰：子夏曰：“賢賢易賢賢易色色；事父母，能竭其力；事君，；事父母，能竭其力；事君，能致其身；與朋友交，言而有信。雖日未學(xué)，吾能致其身；與朋友交，言而有信。雖日未學(xué)，吾必謂之學(xué)矣。必謂之學(xué)矣?！眑人際關(guān)系：父子；君臣；朋友；夫妻人際關(guān)系：父子；君臣；朋友；夫妻數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)2021-1

2、2-15編輯ppt第第2章章 信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）2021-12-15編輯ppt第第2章章 信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）2021-12-15編輯ppt2.整除的基本性質(zhì)整除的基本性質(zhì)( N 整數(shù)集整數(shù)集) (1) a(a0), a|0,a|a (同理同理 b N,1|b) (2) b|a, cb|ca (3) a|b, b|c a|c.（傳遞性）（傳遞性） (4) a|b, a|c a|(xb+yc) (x,y N) (5) b|a 且且a0 |b|a| (6) cb|ca, b|a1.定義：定義： 設(shè)整數(shù)設(shè)整數(shù)a和和b,且且a 0，如果存在整數(shù)

3、，如果存在整數(shù)k使得使得b=ak， 那么就說那么就說a整除整除a（或（或b能被能被a整除）整除），記作，記作a|b，或者說，或者說b是是a的倍數(shù)。的倍數(shù)。 舉例：舉例：3|15,-15|60整除定義及性質(zhì)整除定義及性質(zhì)2021-12-15編輯ppt證明：證明：（1）作一個整數(shù)序列）作一個整數(shù)序列（2）反證法）反證法帶余數(shù)除法：帶余數(shù)除法： 如果如果a，b是兩個整數(shù)，其中是兩個整數(shù)，其中b0，則存在兩個整數(shù)，則存在兩個整數(shù)q和和r，使得，使得abqr（0rb）成立，且）成立，且q和和r是唯一的。是唯一的。帶余數(shù)除法帶余數(shù)除法2021-12-15編輯ppt非負最小剩余的性質(zhì)：非負最小剩余的性質(zhì)：（

4、1） = + （2） = - （3） = 定義（非負最小剩余）定義（非負最小剩余） abqr（0rb）中）中r叫做非負最小剩余，常記做叫做非負最小剩余，常記做b=r（在不致引起混淆的情況下，（在不致引起混淆的情況下，b常常省略）常常省略）帶余數(shù)除法帶余數(shù)除法2021-12-15編輯ppt1.定義：定義： 一個大于一個大于1的整數(shù)的整數(shù)p，只能被只能被1或者是它本身整除或者是它本身整除,而不能而不能被其他整數(shù)整除，則稱整數(shù)為素數(shù)被其他整數(shù)整除，則稱整數(shù)為素數(shù)(prime number)，否，否則就叫做合數(shù)則就叫做合數(shù)(composite)。 eg 素數(shù)（素數(shù)（2，3，5，7，11，13等）等）

5、合數(shù)（合數(shù)（4，6，8，9，12等）等） 素數(shù)定義及素數(shù)個數(shù)定理素數(shù)定義及素數(shù)個數(shù)定理2021-12-15編輯ppt2.補充定理補充定理(1)：設(shè)：設(shè)a是任一大于是任一大于1的整數(shù)，則的整數(shù)，則a的的除除1外的最小正因子外的最小正因子q是素數(shù)，并且當(dāng)是素數(shù)，并且當(dāng)a是合數(shù)是合數(shù)時：時：素數(shù)補充定理素數(shù)補充定理qa2021-12-15編輯ppt2.補充定理補充定理(2)：若：若p是一個素數(shù)，是一個素數(shù)，a是任一整數(shù)，是任一整數(shù)，則有則有p|a或或(p,a)=1素數(shù)補充定理（續(xù)）素數(shù)補充定理（續(xù)）2021-12-15編輯ppt素數(shù)補充定理（續(xù)）素數(shù)補充定理（續(xù)）2.補充定理：補充定理： p為素數(shù)，

6、且為素數(shù)，且p|ab,那么那么p|a或或p|b。 更一般地，如果更一般地，如果abz能夠被素數(shù)能夠被素數(shù)p整除，那么整除，那么a,b,z中的某個數(shù)必能被中的某個數(shù)必能被p整除。整除。2021-12-15編輯ppt3.素數(shù)個數(shù)定理（素數(shù)個數(shù)定理（1）：）： 素數(shù)的個數(shù)是無限的素數(shù)的個數(shù)是無限的原因：原因：（1）N（N1）的除）的除1外的最小正因數(shù)外的最小正因數(shù)q是一個素數(shù)是一個素數(shù)（2）如果）如果q=pi，（，（i1,2,k), 且且q|N，因此，因此q|(N- p1p2,.pk)，所以，所以q|1，與，與q是素數(shù)矛盾。是素數(shù)矛盾。素數(shù)個數(shù)定理及證明素數(shù)個數(shù)定理及證明證明：反證法證明：反證法假設(shè)

7、正整數(shù)個數(shù)是有限的，設(shè)為假設(shè)正整數(shù)個數(shù)是有限的，設(shè)為p1,p2,.,pk令：令：p1p2pk+1=N (N1)則則N有一個素數(shù)有一個素數(shù)p，且，且ppi（i=1,2,k).故故p是上述是上述k個素數(shù)外的另外一個素數(shù)。個素數(shù)外的另外一個素數(shù)。因此與假設(shè)矛盾。因此與假設(shè)矛盾。2021-12-15編輯ppt素數(shù)定義及素數(shù)個數(shù)定理素數(shù)定義及素數(shù)個數(shù)定理3.素數(shù)個數(shù)定理（素數(shù)個數(shù)定理（2）：）： 設(shè)設(shè) (x)是小于是小于x的素數(shù)個數(shù)，則的素數(shù)個數(shù)，則 (x) x / lnx, 即即x時，比值時，比值 (x) /(x / lnx) 1 eg:可以估算可以估算100位素數(shù)的個數(shù)：位素數(shù)的個數(shù)： (10100

8、) - (1099) 10100/(ln10100) 1099/(ln1099) 3.9 * 1097.2021-12-15編輯ppt1.整數(shù)的唯一分解定理定理（算術(shù)基本定理）整數(shù)的唯一分解定理定理（算術(shù)基本定理）: 設(shè)設(shè)nZ, 有分解式有分解式, n = p1e1p2e2.pmem,其中其中p1, p2, pmZ+是互不相同的素數(shù)是互不相同的素數(shù), e1,e2,emZ+, 并且數(shù)對并且數(shù)對(p1, e1), (p2, e2),(pm, em)由由n唯一確定（即唯一確定（即如果不考慮順序，如果不考慮順序，n的分解是唯一的）的分解是唯一的）.eg: 504=23327, 1125 = 3253整

9、數(shù)的唯一分解定理整數(shù)的唯一分解定理2021-12-15編輯ppt1.定義定義 兩個整數(shù)兩個整數(shù)a,b的最大公約數(shù)，就是能同時整除的最大公約數(shù)，就是能同時整除a和和b的最的最大正整數(shù)大正整數(shù),記為記為gcd(a,b)， 或或(a,b). eg: gcd(5,7) = 1， gcd(24,60) = 12，最大公約數(shù)定義及求法最大公約數(shù)定義及求法2. 求最大公約數(shù)的兩種方法：求最大公約數(shù)的兩種方法： (1)因數(shù)分解：因數(shù)分解： eg:1728 = 2632,4536 = 23347, gcd(1728, 4536) = 2332=72.2021-12-15編輯ppt(2)歐幾里得歐幾里得(Eucl

10、id)算法算法 設(shè)設(shè)a, b N, ab0, 用以下方法可求出用以下方法可求出 gcd(a,b).最大公約數(shù)的歐幾里得算法最大公約數(shù)的歐幾里得算法. ,)gcd( ,0 , . )gcd( ,0 ,)gcd( ,0 ,)gcd()gcd( ,0 ,1111123223332121122211111nnnnnnnnnnnnrqrr,rrrrrqrr,rrrrrqrr,rrrrrqrbb,ra,bbrrbqa2021-12-15編輯pptEuclid算法實例：求算法實例：求 gcd(132, 108).12 ,12224)12,4gcd(2 ,12244108)24gcd(108 ,2410811

11、32)108gcd(132 ,最大公約數(shù)的歐幾里得算法（續(xù)）最大公約數(shù)的歐幾里得算法（續(xù)）2021-12-15編輯pptl歐幾里得算法（例歐幾里得算法（例1）11802 4822164822 216502164 50 1650 3 16216208gcd（1180，482）2求：求：gcd（1180，482）最大公約數(shù)的歐幾里得算法（續(xù)）最大公約數(shù)的歐幾里得算法（續(xù)）2021-12-15編輯pptl歐幾里得算法（例歐幾里得算法（例2）：求）：求gcd(12345,1111)123451111111112345441 0gcd 12345111111123495123424645114（，）最大

12、公約數(shù)的歐幾里得算法（續(xù)）最大公約數(shù)的歐幾里得算法（續(xù)）2021-12-15編輯pptl歐幾里得算法抽象歐幾里得算法抽象112 1213 2324 342111b.gcd( , )kk kkkkkkaqbrq rrrq rrrq rrrq rrrqra br規(guī)律：余數(shù)除數(shù)被除數(shù)忽略最大公約數(shù)的歐幾里得算法（續(xù)）最大公約數(shù)的歐幾里得算法（續(xù)）2021-12-15編輯pptl歐幾里得算法實現(xiàn)歐幾里得算法實現(xiàn)1011112gcd( , ):;101(,.,):gcd( , )mmmrmrmmm mmmma bra rb mwhilerdoqrrq rmmreturnq qqrcommenta br算

13、法最大公約數(shù)的歐幾里得算法（續(xù)）最大公約數(shù)的歐幾里得算法（續(xù)）2021-12-15編輯ppt特別特別a, b為素數(shù)時為素數(shù)時gcd(a,b)=1，存在，存在 ma+nb=1. 上述求上述求 rn = ma+nb的方法叫做的方法叫做擴展的擴展的Euclid算法算法 利用該方法我們可以求利用該方法我們可以求ax+by=d的解的解,這里這里d= (a,b) 證明：根據(jù)證明：根據(jù)Euclid算法算法 a=bq1+r1 b=r1q2+r2 r1=r2q3+r3 , rn-2 = rn-1qn+rn gcd(a,b)= r n = rn-2 - rn-1qn = = ma+nb3.定理定理 設(shè)設(shè)a, bZ

14、+, 則存在則存在m, nZ使得使得gcd(a,b)=ma+nb. 擴展的歐幾里得算法擴展的歐幾里得算法2021-12-15編輯pptl計算出了計算出了gcd(a,b);l但是并沒有計算出兩個數(shù)但是并沒有計算出兩個數(shù)m，n來，使得：來，使得：lma+nb=gcd(a,b)擴展的歐幾里得算法的結(jié)果擴展的歐幾里得算法的結(jié)果l計算出了計算出了gcd(a,b);l計算出兩個數(shù)計算出兩個數(shù)m，n來，使得：來，使得：lma+nb=gcd(a,b)擴展的歐幾里得算法（續(xù)）擴展的歐幾里得算法（續(xù)）歐幾里得算法的結(jié)果歐幾里得算法的結(jié)果2021-12-15編輯ppt利用該方法我們可以求密碼學(xué)方程利用該方法我們可以

15、求密碼學(xué)方程ax+by=d的的解解,這里這里d= (a,b)例如例如: 求求132x+108y = 12的解的解 解：解： 12=gcd(132,108) 12 = 108-4 24 = 108-4 (132-108 1) = 108 4 132 +4 108 =5*108 4*132擴展的歐幾里得算法（續(xù)）擴展的歐幾里得算法（續(xù)）2021-12-15編輯ppt第第2章章 信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）2021-12-15編輯ppt證明：證明：必要性必要性:設(shè)設(shè)ab (mod m), a=mp+r, b=mq+r, 0rm a-b=m(p-q), m|(a-b).充分性充分性

16、:設(shè)設(shè)m|(a-b), a=mp+r, b=mq+s, 0r, sm a-b=m(p-q)+(r-s) m|(r-s) 0|r-s|0， C1，Cm-1是模數(shù)是模數(shù)m的剩余類，則有：的剩余類，則有：（1）每一個整數(shù)恰好包含在某一個類）每一個整數(shù)恰好包含在某一個類Cj中（中（0jm-1）（2）兩個整數(shù)）兩個整數(shù)x和和y屬于同一個類的充要條件是屬于同一個類的充要條件是xy（mod m）剩余類和完全剩余系（續(xù)）剩余類和完全剩余系（續(xù)）2021-12-15編輯ppt定義（完全剩余系）：定義（完全剩余系）： 在模數(shù)在模數(shù)m的剩余類的剩余類 C1，Cm-1中各取一數(shù)中各取一數(shù)aj（j=0，1，m-1），此

17、），此m個數(shù)個數(shù)a0，a1，am-1稱為模數(shù)稱為模數(shù)m的一組完全剩余系。的一組完全剩余系。剩余類和完全剩余系（續(xù)）剩余類和完全剩余系（續(xù)）例如：例如：m3 C00，3，6，9， C11，4，7，10， C2 2，5，8，11，則則a00，a11，a22就是模就是模m的一組完全剩余系。的一組完全剩余系。2021-12-15編輯ppt定理（完全剩余系）：定理（完全剩余系）： m個整數(shù)組成模數(shù)個整數(shù)組成模數(shù)m的一組完全剩余系的充要條件是的一組完全剩余系的充要條件是兩兩對模數(shù)兩兩對模數(shù)m不同余。不同余。剩余類和完全剩余系（續(xù)）剩余類和完全剩余系（續(xù)）定義（非負最小完全剩余系）定義（非負最小完全剩余系）

18、 由由0， 1，2，m-1組成的剩余系稱為模數(shù)組成的剩余系稱為模數(shù)m的非負的非負最小完全剩余系。最小完全剩余系。2021-12-15編輯ppt定理（完全剩余系）：定理（完全剩余系）： 設(shè)（設(shè)（k, m）1，a0，a1，am-1是模數(shù)是模數(shù)m的一組完的一組完全剩余系，則：全剩余系，則： ka0， ka1，kam-1也是模數(shù)也是模數(shù)m的一組完全剩余系。的一組完全剩余系。剩余類和完全剩余系（續(xù)）剩余類和完全剩余系（續(xù)）2021-12-15編輯ppt（1）剩余類可能包含多個集合（）剩余類可能包含多個集合（ 即：模數(shù)即：模數(shù)m的的剩余類是多個集合）剩余類是多個集合）（2）完全剩余系專指一個集合）完全剩余

19、系專指一個集合剩余類和完全剩余系（續(xù)）剩余類和完全剩余系（續(xù)）定義（定義（模數(shù)模數(shù)m互素的剩余類）互素的剩余類） 如果一個模數(shù)如果一個模數(shù)m的剩余類里面的數(shù)與的剩余類里面的數(shù)與m互素，互素，就稱之為與模數(shù)就稱之為與模數(shù)m互素的剩余類?；ニ氐氖Ｓ囝?。例如：例如：m3 C11，4，7，10， C2 2，5，8，11，都是模都是模m互素的剩余類?；ニ氐氖Ｓ囝?。2021-12-15編輯ppt定義（定義（縮系）縮系） 在與模數(shù)在與模數(shù)m互素的全部剩余類中，各取一個數(shù)所組成互素的全部剩余類中，各取一個數(shù)所組成的集合叫做模數(shù)的集合叫做模數(shù)m的一組縮系。的一組縮系。剩余類和完全剩余系（續(xù)）剩余類和完全剩余系（

20、續(xù)）例如：例如：m3 C11，4，7，10， C2 2，5，8，11，是模是模m互素的剩余類，而互素的剩余類，而C 4，5是模數(shù)是模數(shù)m的一的一組縮系。組縮系。問題：縮系含有多少個數(shù)？問題：縮系含有多少個數(shù)？2021-12-15編輯ppt歐拉函數(shù)的求法：歐拉函數(shù)的求法： （1）如果）如果n是素數(shù)，則是素數(shù)，則?(n)=n-1 （2）npq，其中，其中p，q為素數(shù)，則為素數(shù)，則?(n)=(p-1)(q-1) （3）1.定義（歐拉函數(shù)）定義（歐拉函數(shù)） 歐拉函數(shù)歐拉函數(shù)?(n)是一個定義在正整數(shù)上的函數(shù)，是一個定義在正整數(shù)上的函數(shù)， ?(n) 的的值等于序列值等于序列0，1，2，n1中與中與n互素

21、的數(shù)的個數(shù)?；ニ氐臄?shù)的個數(shù)。費馬小定理和歐拉定理費馬小定理和歐拉定理12111( )(1)(1).(1)ipppnnin.12iqqq12i12如果 ppp （p ，p，p 為素數(shù)），則：2021-12-15編輯ppt定理（縮系中數(shù)的個數(shù)）定理（縮系中數(shù)的個數(shù)） 模數(shù)模數(shù)m的縮系含有的縮系含有?(n)個數(shù)。個數(shù)。費馬小定理和歐拉定理（續(xù)）費馬小定理和歐拉定理（續(xù)）例如：例如： m3， ?(m)2，因而，因而C 1，2含有兩含有兩個數(shù)。個數(shù)。定理（縮系）定理（縮系） 若若a1，a2，a ?(m)是是?(m)個與個與m互素的整數(shù)，則互素的整數(shù)，則a1，a2，a?(m)是模數(shù)是模數(shù)m的一組縮系的充要

22、條件是它們兩的一組縮系的充要條件是它們兩兩對模數(shù)兩對模數(shù)m不同余不同余。2021-12-15編輯ppt定理：若（定理：若（a，m）1，x通過模數(shù)通過模數(shù)m的縮系，則的縮系，則ax也通過模數(shù)也通過模數(shù)m的縮系。的縮系。費馬小定理和歐拉定理（續(xù)）費馬小定理和歐拉定理（續(xù)）證明：證明： 當(dāng)當(dāng)x通過模數(shù)通過模數(shù)m的縮系，則的縮系，則ax通過通過?(m)個整數(shù)，由于個整數(shù)，由于（a，m）=1，（，（x，m）=1，因此（，因此（ax，m）=1。 若若ax1ax2（mod m），可知），可知x1x2（mod m），與假設(shè)），與假設(shè)x通過模數(shù)通過模數(shù)m的縮系矛盾，故的縮系矛盾，故ax通過模數(shù)通過模數(shù)m的縮系。

23、的縮系。2021-12-15編輯ppt(2)歐拉定理歐拉定理 設(shè)設(shè)m1，如果，如果gcd(a, n) = 1,則則:a?(n) 1mod n. eg: 求求7803的后三位數(shù)字的后三位數(shù)字 解：解： 7803（mod 1000）的結(jié)果）的結(jié)果 ?(1000) = 1000(1-1/2)(1-1/5) = 400， 有有7803 (7400)273 343 (mod 1000)費馬小定理和歐拉定理（續(xù)）費馬小定理和歐拉定理（續(xù)）2021-12-15編輯ppt推論（推論（ Fermat小定理）小定理）: p素數(shù)素數(shù),a是整數(shù)且不能被是整數(shù)且不能被p整除整除,則則:a p-1 1 mod p. 費馬

24、小定理和歐拉定理（續(xù)）費馬小定理和歐拉定理（續(xù)）例如：例如： 求求 253 (mod 11) = ? 由由Fermat小定理小定理: 210 = 1024 1 (mod 11) 253 = (210)523 1523 8 (mod 11) 2021-12-15編輯ppt （1）通常情況下，如果）通常情況下，如果2n-1 1 (mod n),n為素數(shù)為素數(shù),然而然而,也有例外也有例外: 561 = 3 11 17是合數(shù)是合數(shù),但但2560 1 (mod 561)。因此，如果。因此，如果2n-1 1 (mod n),那么那么n可能為素數(shù)。可能為素數(shù)。 （2）但）但2n-1 模模n 不等于不等于 1

25、,那么那么n不可能為素數(shù)不可能為素數(shù) 這為我們提供一種尋找素數(shù)的方法，給定一個這為我們提供一種尋找素數(shù)的方法，給定一個n, 計計算算2n-1 模模n 是否等于是否等于 1，如果不等于，如果不等于1， n為非素數(shù)，為非素數(shù)，如果等于如果等于1，還需用更復(fù)雜的方法來判斷是否為素數(shù)，還需用更復(fù)雜的方法來判斷是否為素數(shù)，比如：比如： (1)索洛維索洛維-斯特拉森斯特拉森(Solovay-Strassen)素性檢測算法素性檢測算法 (2)米勒米勒-羅賓羅賓(Miller-Rabin)素性檢測算法素性檢測算法 (3) AKS算法算法費馬小定理和歐拉定理的應(yīng)用費馬小定理和歐拉定理的應(yīng)用2021-12-15編

26、輯ppt 解：解：（1）由費爾馬定理）由費爾馬定理2100（mod 1001）1（mod 101）（2）243210 (2100) 432210 210 1024 (mod 101)=14eg: 計算計算243210 （mod 101）歐拉定理的應(yīng)用歐拉定理的應(yīng)用2021-12-15編輯ppt7.一次同余式一次同余式 (1)定義定義: 設(shè)設(shè)mZ+, a, bZ, a0, 我們把我們把 ax+b0 (mod m) 稱為模數(shù)稱為模數(shù)m的一次同余式的一次同余式. 如果如果x0Z滿足滿足: ax0+b0 (mod m) 則稱則稱xx0 (mod m)是同余式的解是同余式的解.eg : 同余式同余式2x

27、+1 0 (mod 3) 有解有解x0=1. 同余式同余式2x+1 0 (mod 4) 無解無解. 同余式同余式2x+1 0 (mod 5) 有解有解x0=2.一次同余式一次同余式2021-12-15編輯ppt(2)一次同余式的解一次同余式的解 定理定理1: 設(shè)設(shè)mZ+, a, bZ, a0, (a, m)=1, 則同余式則同余式 axb (mod m)恰有一個解恰有一個解xba ?(m)-1 (mod m). eg:同余式同余式2x+10 (mod 5) 有解有解: x0=(-1)2 ?(5)-1 423 322 (mod 5) 一次同余式（續(xù)）一次同余式（續(xù)）2021-12-15編輯ppt

28、 定理定理2: 設(shè)設(shè)mZ+, a, bZ, a0, (a, m)=d, 則同余式則同余式axb(mod m) 有解的充要條件是有解的充要條件是d|b. 在在d|b的條件下的條件下, 同余式有同余式有d個解個解. eg: 同余式同余式2x 3 (mod 4)無解無解 d=(2,4)=23. 同余式同余式2x 4 (mod 6) d=(2,6)=2|4 有有2個解個解: x=2, 5. 一次同余式的解一次同余式的解2021-12-15編輯ppt第第2章章 信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）2021-12-15編輯ppt孫子算經(jīng)孫子算經(jīng)中記載著一道世界聞名的中記載著一道世界聞名的“孫子

29、問題孫子問題”：“今有無不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，今有無不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？七七數(shù)之剩二，問物幾何？”孫子問題等同于下面這樣一個問題：孫子問題等同于下面這樣一個問題： 已知已知 x=2mod3，x=3mod5且且x=2mod7，求整數(shù)，求整數(shù)x。中國剩余定理中國剩余定理2021-12-15編輯ppt中國剩余定理（續(xù)）中國剩余定理（續(xù)）2021-12-15編輯ppt中國剩余定理（續(xù)）中國剩余定理（續(xù)）2021-12-15編輯ppt中國剩余定理（續(xù)）中國剩余定理（續(xù)）2021-12-15編輯ppt中國剩余定理中國剩余定理(孫子孫子: Sun Z

30、e, 公元前公元前450年年,孫子定理孫子定理)： 設(shè)自然數(shù)設(shè)自然數(shù)m1,m2,mr兩兩互素，并記兩兩互素，并記M=m1m2mr，則，則同余方程組同余方程組: x b1(mod m1) x b2(mod m2) . . x br(mod mr) 有唯一解：有唯一解： x b1*M1*y1+b2*M2*y2+br*Mr*yr (mod M) Mi = M/mi ,yi = Mi-1 (mod mi) (1 i r) 中國剩余定理（續(xù)）中國剩余定理（續(xù)）2021-12-15編輯ppt例如例如:求以下同余方程組的解：求以下同余方程組的解： x 5 mod 7 x 3 mod 11 x 10 mod

31、13中國剩余定理解同余方程組中國剩余定理解同余方程組解：解： r=3,m1=7,m2=11,m3=13;b1=5,b2=3,b3=10; 模模M = m1 m2 m3 = 1001, M1 =M/ m1 = m2 m3 = 143, M2 =91, M3 =77. y1 = M1-1(mod m1) = 143-1(mod 7) = 5, y2=4, y3=12. 解為解為: x = b1 M1 y1 + b2 M2 y2 + b3 M3 y3 (mod M) = 5 143 5 + 3 91 4 + 10 77 12 (mod 1001) =13907 (mod 1001) = 894驗證驗

32、證: x = 894 = 127 7+5 = 5 (mod 7) 2021-12-15編輯ppt中國剩余定理：中國剩余定理： 除數(shù)除數(shù)余數(shù)余數(shù)最小公倍數(shù)最小公倍數(shù)衍數(shù)衍數(shù)乘率乘率各總各總答數(shù)答數(shù)m1b1m=m1m2mkM1M1M1M1b1X=MiMibi (mod m)m2b2M2M2M2M2b2mkbkMkMkMkMkbk其中：其中：m=miMiMiMi=1 (mod m)中國剩余定理（續(xù)）中國剩余定理（續(xù)）2021-12-15編輯ppt中國剩余定理（續(xù)）中國剩余定理（續(xù)）2021-12-15編輯ppt例如（孫子算經(jīng)）解法：表格法例如（孫子算經(jīng)）解法：表格法除數(shù)除數(shù) 余數(shù)余數(shù)最小公倍數(shù)最小公

33、倍數(shù)衍數(shù)衍數(shù)乘率乘率各總各總答數(shù)答數(shù)323x5x7=1055x7M1=2 35x2x21406330233537x3M2=1 21x1x3723x5M3=1 15x1x2中國剩余定理求解同余方程組中國剩余定理求解同余方程組2021-12-15編輯ppt中國剩余定理（續(xù)）中國剩余定理（續(xù)）2021-12-15編輯ppt中國剩余定理（續(xù)）中國剩余定理（續(xù)）2021-12-15編輯ppt中國剩余定理（續(xù)）中國剩余定理（續(xù)）2021-12-15編輯ppt第第2章章 信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）2021-12-15編輯ppt計算計算Xa ( mod n) ,其中其中 x, a, n

34、Z+ Eg:計算計算21234 (mod 789) 一種有效的方法：一種有效的方法： 24 16 28 256 216 2562 49 232 492 34 264 342 367 2128 3672 559 2256 5592 37 2512 372 580 21024 5802 286 1234 = 1024+128+64+16+2 （1234 = (10011010010)2） 21234 = 286 559 367 49 4 481 (mod 789)模的冪運算模的冪運算優(yōu)勢：優(yōu)勢：模的冪運算可快速完成，并且模的冪運算可快速完成，并且不需要太大內(nèi)存不需要太大內(nèi)存2021-12-15編輯

35、ppt模的冪運算（續(xù)）模的冪運算（續(xù)）22/ 2 (2-1) / 2 (yyyyyyy表 示 除 以 取 整 ， 即 ：是 偶 數(shù)（是 奇 數(shù) ）但是，上述計算過程并不適合于計算機程序?qū)嵉?，上述計算過程并不適合于計算機程序?qū)崿F(xiàn)。為此，可以采用現(xiàn)。為此，可以采用“重復(fù)平方重復(fù)平方-乘乘”運算來運算來進行指數(shù)模運算。進行指數(shù)模運算。2222() () (yyyxyxxxy因此：是偶數(shù)是奇數(shù)）2021-12-15編輯ppt模的冪運算（續(xù)）模的冪運算（續(xù)）重復(fù)平方重復(fù)平方-乘算法乘算法 求模指數(shù)運算的重復(fù)平方-乘算法 輸入：整數(shù) x，y，n：x0，y?0，n1 輸出：(mod )yxn 算法描述：

36、00 mod_exp(x,y, n) 01 if y=0 return(1) 02 if y (mod 2)=0 return(mod_exp(x2(mod n), y2, n)（mod n） 03 return(x mod_exp(x2(mod n), y2, n)(mod n) 2021-12-15編輯ppt第第2章章 信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）2021-12-15編輯ppt整數(shù)的次數(shù)整數(shù)的次數(shù)由歐拉定理知道：如果由歐拉定理知道：如果(a, m)1，m1，則，則a?(n) 1(mod m)也就是說，如果也就是說，如果(a, m)1，m1，則存在一個整數(shù)，則存在一個整數(shù)

37、滿足滿足:a 1(mod m)定義（整數(shù)的次數(shù)）：定義（整數(shù)的次數(shù)）： 若若(a, m)1，m1，則使得同余式，則使得同余式 a 1(mod m)成立的成立的最小正整數(shù)最小正整數(shù)叫做叫做a對模對模m的的次數(shù)次數(shù)。2021-12-15編輯ppt整數(shù)的次數(shù)（續(xù)）整數(shù)的次數(shù)（續(xù)）定理：設(shè)定理：設(shè)a對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為l，an1（mod m），則），則l|n。證明：證明： 如果結(jié)論不成立，則必有兩個整數(shù)如果結(jié)論不成立，則必有兩個整數(shù)q和和r，使得：，使得： nqlr（0rl） 而而1 an a(qlr) aqlar ar (mod m)，因此與，因此與l的定義相的定義相違背。違背。 推論：設(shè)

38、推論：設(shè)a對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為l，則，則l|?(m)。2021-12-15編輯ppt整數(shù)次數(shù)的計算：整數(shù)次數(shù)的計算： 因為因為l|?(m)，因此可以通過計算以下對模數(shù)，因此可以通過計算以下對模數(shù)m的值求出。的值求出。整數(shù)的次數(shù)（續(xù)）整數(shù)的次數(shù)（續(xù)）例如：例如：m7，a2(m)62322（mod 7）423（mod 7）1因此因此a對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為3。s1212s,.dd .dmdddaaa， （其中，是 （）的諸因子）2021-12-15編輯ppt整數(shù)次數(shù)的有效計算方法（整數(shù)次數(shù)的有效計算方法（1）：）：整數(shù)的次數(shù)（續(xù)）整數(shù)的次數(shù)（續(xù)）1212.killlklimppp

39、mp如果是的標(biāo)準(zhǔn)分解式，整數(shù)a對模數(shù)m的次數(shù)等于整數(shù)a對模數(shù)的諸次數(shù)的最小公倍數(shù)。1212a1,2,.,),.,0|(1,2,.,),.,iiiliiklddilddiikfpikdfffapamdmdddamapfdikdfff證 明 ： 設(shè)表 示 對 模 數(shù)（1(mod )1(mod )如 果不 是 模 數(shù)的 次 數(shù) ， 則 設(shè) 其 次 數(shù) 為1(mod )1(mod )與是的 最 小 公 倍 數(shù) 矛 盾 。2021-12-15編輯ppt整數(shù)次數(shù)的有效計算方法（整數(shù)次數(shù)的有效計算方法（1）：）：整數(shù)的次數(shù)（續(xù)）整數(shù)的次數(shù)（續(xù)）amam例如：設(shè) 2， 45，求 對 的次數(shù)。解 ：45 5 9

40、2對 模 數(shù) 5的 次 數(shù) 是 42對 模 數(shù) 9的 次 數(shù) 是 6因 此 2對 模 數(shù) 45的 次 數(shù) 為 ：4,6=12。2021-12-15編輯ppt整數(shù)次數(shù)的有效計算方法（整數(shù)次數(shù)的有效計算方法（2）：）：整數(shù)的次數(shù)（續(xù)）整數(shù)的次數(shù)（續(xù)）211212|1 2 jjfijjjjjjpapffffpfpafjifpfji定理（次數(shù)的求法之二）設(shè) 是一個素數(shù)， 對模數(shù)的次數(shù)是，則：=或=；又設(shè)，則有：10102apaf例如：設(shè) 7， 2，求 對模數(shù)的次數(shù)。122410410127148,2| 4822128fff解 ：， 所 以 ：2021-12-15編輯ppt整數(shù)的次數(shù)（續(xù)）整數(shù)的次數(shù)（續(xù)

41、）定理：設(shè)定理：設(shè)a對模數(shù)對模數(shù)m的的次數(shù)次數(shù)為為l，1,a, a2,，al-1對對模數(shù)模數(shù)m兩兩不同余。兩兩不同余。證明：證明： 如果結(jié)論不成立，則有某對如果結(jié)論不成立，則有某對j，k（0jkl-1，使得：，使得： aj ak（mod m） 因此：因此： ak-j 1（mod m） 而而1k-j0,(g,m)=1, 如果整數(shù)如果整數(shù)g對對m的的次數(shù)次數(shù)為為?(m) ，則，則g叫做叫做m的一個的一個本原根本原根（或（或原根原根）. eg: 3是模是模7的的本原根本原根 因為因為3 ?(7) 36 1(mod 7) 本原根定義本原根定義2021-12-15編輯ppt本原根定義（續(xù)）本原根定義（續(xù)

42、）例如：例如：m7，a2(m)62322（mod 7）423（mod 7）1因此：因此： a對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為3 (m) 所以：所以： 2不是不是7的本元根。的本元根。2021-12-15編輯ppt定理（原根）定理（原根） 設(shè)整數(shù)設(shè)整數(shù)m0,(g,m)=1,則則g是是m的一個原根的充要的一個原根的充要條件是：條件是： g，g2，g?(m)組成模數(shù)組成模數(shù)m的一組縮系。的一組縮系。本原根判斷本原根判斷定理說明：如果定理說明：如果g是是m的一個原根，則模數(shù)的一個原根，則模數(shù)m的一的一組縮系可表示為形如定理中的幾何級數(shù)。組縮系可表示為形如定理中的幾何級數(shù)。2021-12-15編輯ppt2

43、.定理：定理： 設(shè)對素數(shù)設(shè)對素數(shù)p而言，如果而言，如果g是一個是一個本原根本原根 (1)如果如果n是是整數(shù)，那么整數(shù)，那么gn 1(mod p)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) n0(mod p-1) (2)如果如果j和和k都是整數(shù)，那么都是整數(shù)，那么gj gk當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)j k(mod p-1)本原根有關(guān)定理本原根有關(guān)定理2021-12-15編輯ppt問題：是否所有的正整數(shù)都有原根？問題：是否所有的正整數(shù)都有原根？本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)）例如：例如：m12(m)623，與，與m互素的正整數(shù)包括互素的正整數(shù)包括5，7，11。52（mod 12）1因此，因此，5對對12的次數(shù)是的次數(shù)是272

44、（mod 12）1因此因此7對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為2112（mod 12）1因此因此11對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為2因此因此m12沒有原根。沒有原根。2021-12-15編輯ppt定理（整數(shù)存在原根的必要條件）：定理（整數(shù)存在原根的必要條件）： 設(shè)設(shè)m1，若，若m有原根，則有原根，則m必為下列諸數(shù)之一：必為下列諸數(shù)之一：2，4，pl，2pl（l1，p為奇素數(shù)）。為奇素數(shù)）。本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)）定理（整數(shù)存在原根的充分條件）：定理（整數(shù)存在原根的充分條件）： 設(shè)設(shè)m2，4，pl，2pl（l1，p為奇素數(shù)）時，則為奇素數(shù)）時，則m有原有原根。根。定理（整數(shù)原根個數(shù)）

45、：定理（整數(shù)原根個數(shù)）： 設(shè)設(shè)m有一個原根有一個原根g，則，則m恰有恰有?(?(m)個對模數(shù)個對模數(shù)m不同余不同余的原根，這些原根由以下集合給出：的原根，這些原根由以下集合給出：|1( ),( , ( ) 1tSgtmtm 2021-12-15編輯ppt本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)） 17gmmmmm1( ),( , ( ) 13 mod733 mod75mtmtm 例如，已知 3是 7的一個原根，求 的所有元根。解：（ ）62 3（ ）（6）2因此 有兩個元根。滿足條件的t=1,5即 有兩個元根，分別為3和52021-12-15編輯ppt原根的判斷：原根的判斷： 一般來說，判斷一般

46、來說，判斷g是否時一個素數(shù)是否時一個素數(shù)m的原根時，的原根時，不需要逐一計算不需要逐一計算g1，g2，g?(m)，而僅需要計，而僅需要計算算gt(modm），其中），其中t|?(m)。本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)）2021-12-15編輯ppt本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)） 23gmm4 mod74 mod7)24 mod7) 14 mod71m16例如，判斷 4是否是 7的一個原根解：（ ）62 3滿足條件t| (m)的t=1,2,3,6（）4（）因此4不是 的本元根。2021-12-15編輯ppt本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)）定理（原根的計算）：定理（原根的計

47、算）： 12( )2.11(mod )(1,2,., )ismqmmqqqgmgmgm is設(shè)，（ ）的所有不同的素因子是 ， ， ，（ ， ），則 是 的一個原根的充要條件是： 3121220812412525)20,812mod4140112mod411811241gmmqqmmqqm例如，證明 是 的原根。證明：（ ），（）（）由定理是 的一個原根。2021-12-15編輯ppt本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)） 12gm6 2 32,33;2mod7mod763 m 7mqqmm1223例如，判斷 3是否是 7的原根。解：（ ）所以（ ）（ ）qq3 （）2 13 （）1因此 是

48、 的原根。2021-12-15編輯ppt本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)） 12gmm2,33;2mod7mod7m=7qqmm1223例如，判斷 4是否是 7的一個原根解：（ ）62 3所以（ ）（ ）qq4 （）2 14 （）1因此4不是的本元根。2021-12-15編輯ppt本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)）定理（原根的計算）：定理（原根的計算）： 1 ,1,2,.,papd dpd設(shè) 對模數(shù)奇素數(shù) 的次數(shù)是（ ），則：a都不是 的原根。 12.1,12.dadpdddpadpd證明：因為 （ ， ， ）對模數(shù) 的次數(shù)為，而（ ， ）所以 （ ， ， ）都不是 的原根。（ ，

49、 ）2021-12-15編輯ppt本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)）一個計算原根的算法：一個計算原根的算法： 2112.1221112, 2,., 2(3)1111dppppaapddppdpp （）列出數(shù)， ， （）取 ，計算 對 的次數(shù) ，如果 ，2就是 的原根，算法結(jié)束；如果，在步驟中列出的數(shù)中除去以下各數(shù)：在步驟（）列出的數(shù)中再取一個，重復(fù)步驟（），直到步驟（）縮列出的數(shù)僅剩下（ ）個。2021-12-15編輯ppt41例如：求出 的原根。本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)）1解：（ ）列出1，2，3，.，40 （1）（2）取2，因為2對模數(shù)41的次數(shù)為20，因此（1）式中除

50、去以下各數(shù)：2，4，8，16，32，23，5，10，20，40，39，37，33，25，9，18，36，31，21，1得到：3，6，7，11，12，13，14，15，17，19，22，24，26，27，28，29，30，34，35，382021-12-15編輯ppt本原根有關(guān)定理（續(xù)）本原根有關(guān)定理（續(xù)） 41例如：求出 的原根。解(續(xù)）：（3）取3，因為3對模數(shù)41的次數(shù)為8，因此在（1）式中除去以下各數(shù)：3，9，27，40，38，32，14，1其中1，9，32，40在第一次已經(jīng)除去，得到：6，7，11，12，13，15，17，19，22，24，26，28，29，30，34，35這剩下的（4

51、0）16個數(shù)就是41的原根。2021-12-15編輯ppt指數(shù)指數(shù)如果整數(shù)如果整數(shù)m0有一個元根有一個元根g，g，g2，g?(m)(或數(shù)或數(shù)1,g，g，g2，g?(m)-1）組成模數(shù)）組成模數(shù)m的一組縮系。的一組縮系。例如，例如， 3是模是模7的的本原根，因此本原根，因此： 31 3 32 2 33 6 34 4 35 5 36 1 上述六個數(shù)剛好是模數(shù)上述六個數(shù)剛好是模數(shù)m的一組縮系。的一組縮系。2021-12-15編輯ppt指數(shù)（續(xù)）指數(shù)（續(xù)）定義：任一整數(shù)定義：任一整數(shù)n，（，（n，m）1，必有唯一的整，必有唯一的整數(shù)數(shù)k（0k ?（m），滿足：），滿足： ngk（mod m） 其中其中

52、k叫做叫做n對模數(shù)對模數(shù)m的指數(shù)，記做的指數(shù)，記做kindgn（簡（簡記為記為ind n） (指數(shù)也叫做指數(shù)也叫做離散對數(shù)離散對數(shù))。2021-12-15編輯pptxg mod m (mod )xngm對于已知元根g和模數(shù)m，求任意整數(shù)n的離散對數(shù)k,可以通過得到：指數(shù)（續(xù)）指數(shù)（續(xù)）2021-12-15編輯ppt( )(13) 12(1,2,.,12)(0( ) 2 (mod13)iiikimn ikkmn例：g=2是m=13的元根,。求的離散對數(shù)：指數(shù)（續(xù)）指數(shù)（續(xù)）2021-12-15編輯ppt指數(shù)（續(xù)）指數(shù)（續(xù)）2021-12-15編輯ppt指數(shù)的性質(zhì)：設(shè)指數(shù)的性質(zhì)：設(shè)g是是m的原根，

53、如果的原根，如果(a,m)(b,m)1：11g11()( )(mod ( )(2)(mod ( )(1)(3)1 0,1( )(4)( 1)(2)2(5)mind a(mod ( )nggind abinda ind bmindanindamnindindgmindmgind a ind gm（）設(shè) 也是 的一個原根，則指數(shù)（續(xù)）指數(shù)（續(xù)）2021-12-15編輯ppt(mod13)()( )(mod ( )(mod13)311(mod12)3(mod12)ind abinda ind bmindindxindindx3x113x11例：求解同余方程3x 11(mod13)解：上述方程與gg同

54、解。因為所以方程gg與同解，其指數(shù)為8，因此x=8即是方程解。指數(shù)（續(xù)）指數(shù)（續(xù)）2021-12-15編輯ppt55(mod12)5939(mod12)39(mod12)8,11,75indindindxindxx33例：求解同余方程x(mod13)解：解上述方程只需要解3indx。因為所以所以indx=3,7,11是的解。因此是方程x(mod13)的解。指數(shù)（續(xù)）指數(shù)（續(xù)）2021-12-15編輯ppt3(mod ( )(1)23(mod12)nindanindamnxindindx例：求解冪同余方程2(mod13)解：因為所以的解就是原方程的解。ind2=4,ind3=9所以2x=8(mo

55、d 12)即x=4就是原方程的解。指數(shù)（續(xù)）指數(shù)（續(xù)）2021-12-15編輯ppt離散對數(shù)困難問題離散對數(shù)困難問題0-1(mod ),kpykpygppp gy猜想（離散對數(shù)困難問題）對于一個奇素數(shù) ，整數(shù) ，存在唯一的滿足。選擇一個適當(dāng)大的 ，如果已知和 ，計算離散對數(shù)k是十分困難的?；陔x散對數(shù)困難性假設(shè)，基于離散對數(shù)困難性假設(shè)，EIGamal提出了提出了EIgamal公鑰公鑰密碼體制。密碼體制。2021-12-15編輯ppt離散對數(shù)困難問題（續(xù)）離散對數(shù)困難問題（續(xù)）21()(mod)()()attatatttmyypmb gmb gmb bm2021-12-15編輯ppt第第2章章

56、信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）2021-12-15編輯ppt模模n逆矩陣逆矩陣定理：一個平方矩陣是模定理：一個平方矩陣是模n可逆的可逆的當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 它的行它的行列式和列式和n是互素的是互素的. 證明：假設(shè)證明：假設(shè)M平方矩陣在模平方矩陣在模n下下有逆矩陣有逆矩陣N,則則 MN I(mod n) det(MN) det(M)det(N) det(I) 1 (mod n) 因為因為 det(M)可逆可逆 (det(M),n)=1Eg:2 2矩陣矩陣,通常的求逆為：通常的求逆為： a b -1 d -b = 1/(ad-bc) c d -c a 2021-12-15編輯ppt

57、 1 2假如要求假如要求 (mod11)的的逆逆 3 4 因為因為ad-bc = -2,需求需求-2 (mod11)的的逆，因為逆，因為5 (-2) 1 (mod11) 1 2 4 -2 4 -2 9 1 1/(-2) 5 (mod11) 3 4 -3 1 -3 1 7 5模模n逆矩陣（續(xù)）逆矩陣（續(xù)）2021-12-15編輯ppt第第2章章 信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）2021-12-15編輯ppt模模n平方根平方根定義定義(二次剩余）二次剩余） 設(shè)設(shè)n是一個大于是一個大于1的正整數(shù)，的正整數(shù)， aZ, a 0 (mod n). 如果同余方程如果同余方程 x2a (mod n) 有一個解有一個解1xn-1, 則稱則稱a是是模數(shù)模數(shù)n的的二次剩余二次剩余，而，而x稱之為稱之為a模模n的