1、2/13/2022 2:56 PM12.2 數(shù)論數(shù)論 Number Theory1、算術(shù)基本定理、算術(shù)基本定理2、同余關(guān)系、同余關(guān)系3、密碼學(xué)基礎(chǔ)、密碼學(xué)基礎(chǔ)2/13/2022 2:56 PM2 以整數(shù)集為典型代數(shù)系統(tǒng)的數(shù)論知識(shí)一直被認(rèn)為是以整數(shù)集為典型代數(shù)系統(tǒng)的數(shù)論知識(shí)一直被認(rèn)為是既神秘又古老。雖然絕大多數(shù)人自小學(xué)生起就開(kāi)始認(rèn)識(shí)它，既神秘又古老。雖然絕大多數(shù)人自小學(xué)生起就開(kāi)始認(rèn)識(shí)它，而一些數(shù)學(xué)家卻一輩子踏著它往皇冠上攀。現(xiàn)在，計(jì)算機(jī)而一些數(shù)學(xué)家卻一輩子踏著它往皇冠上攀。現(xiàn)在，計(jì)算機(jī)終于給數(shù)論這門(mén)再純潔不過(guò)的數(shù)學(xué)分支揚(yáng)起了應(yīng)用的帆。終于給數(shù)論這門(mén)再純潔不過(guò)的數(shù)學(xué)分支揚(yáng)起了應(yīng)用的帆。我們這里介紹

2、的雖然只是初等數(shù)論的基礎(chǔ)知識(shí)，但它們?cè)谖覀冞@里介紹的雖然只是初等數(shù)論的基礎(chǔ)知識(shí)，但它們?cè)谟?jì)算機(jī)的數(shù)據(jù)表示、數(shù)據(jù)傳輸以及電子商務(wù)應(yīng)用中的數(shù)據(jù)計(jì)算機(jī)的數(shù)據(jù)表示、數(shù)據(jù)傳輸以及電子商務(wù)應(yīng)用中的數(shù)據(jù)保密等方面起著非常重要的作用。保密等方面起著非常重要的作用。 1、算術(shù)基本定理、算術(shù)基本定理2/13/2022 2:56 PM3定義定義1 設(shè)設(shè)a,b,c是任意的三個(gè)整數(shù)，若滿(mǎn)足是任意的三個(gè)整數(shù)，若滿(mǎn)足a=bc則稱(chēng)則稱(chēng)b（或（或c）是）是a的的因子因子/factor，a是是b（或（或c）的）的倍倍數(shù)數(shù)/multiple，b(或或c)能能整除整除（也稱(chēng)（也稱(chēng)除盡除盡/divides）a。記為記為 b a 和和

3、c a。特別地，若特別地，若ba且且b1，則稱(chēng)，則稱(chēng)b是是a的直因子。的直因子。2/13/2022 2:56 PM4定理定理1 . 設(shè)設(shè)a、b、c 是任意三個(gè)整數(shù)，則下列各式成立是任意三個(gè)整數(shù)，則下列各式成立（1） 若若b a, 則下列各式成立則下列各式成立 (b0) (b) a, b (a), (b) (a), b a （2） 若若c b且且b a (c0,b0), 則則c a（3） 若若b a (b0), 則則b ac（4） 若若b a且且b c (b0), 則則b (ac)（5） 若若a b且且b a (a0,b0), 則則a=b2/13/2022 2:56 PM5定理定理2 設(shè)設(shè)a,b

4、是兩個(gè)整數(shù)，是兩個(gè)整數(shù)，b0，則恰存在兩個(gè)，則恰存在兩個(gè)整數(shù)整數(shù)q、r使?jié)M足使?jié)M足 a=bq+r 其中其中0r=2)是任意整數(shù)，若有是任意整數(shù)，若有 d|a1, d| a2, , d| an則稱(chēng)則稱(chēng)d是是a1,a2,an的的公因子公因子/common divisor。 若若d是是a1,a2,an的一個(gè)公因子，對(duì)的一個(gè)公因子，對(duì)a1,a2,an的任一的任一個(gè)公因子個(gè)公因子c，存在，存在c d，則稱(chēng)，則稱(chēng)d是是a1,a2,an的的最大公因子最大公因子/greatest common divisor ，記為，記為(a1,a2,an )。或。或 gcd （ a1,a2,an ）或）或GCD （ a1,

5、a2,an ）2/13/2022 2:56 PM7定理定理3 設(shè)設(shè)a、b I 且滿(mǎn)足且滿(mǎn)足 a=b*q+r這里這里 a b，0 rb ，則，則 gcd(a,b) = gcd(b,r)2/13/2022 2:56 PM8定理定理4 任意兩個(gè)整數(shù)都存在最大公因子。任意兩個(gè)整數(shù)都存在最大公因子。求兩個(gè)整數(shù)的最大公因子的歐幾里德算法求兩個(gè)整數(shù)的最大公因子的歐幾里德算法（Euclid，也稱(chēng)輾轉(zhuǎn)相除法）。，也稱(chēng)輾轉(zhuǎn)相除法）。設(shè)設(shè)a、b是任意兩個(gè)整數(shù)，是任意兩個(gè)整數(shù)， a=qi b+ ri i=0、1、2、2/13/2022 2:56 PM9例例1：求：求133 和和301 的最大公因子的最大公因子k012

6、34qk2314rk3528702/13/2022 2:56 PM10定理定理5 設(shè)設(shè)a、b是正整數(shù)，則存在整數(shù)是正整數(shù)，則存在整數(shù)s、t，滿(mǎn)足，滿(mǎn)足 s*a + t*b = gcd（a，b）s*t+t*b：gcd(a,b)的的線性組合線性組合表達(dá)表達(dá)/ linear combination例例2、 求求gcd(252,198)的的線性組合線性組合表達(dá)。表達(dá)。2/13/2022 2:56 PM11定理定理5推論推論 設(shè)設(shè)a、b是整數(shù)，則存在整數(shù)是整數(shù)，則存在整數(shù)s、t，滿(mǎn)足，滿(mǎn)足 s*a + t*b = gcd（a，b）2/13/2022 2:56 PM12定理定理6 設(shè)設(shè)a、b、c是正整數(shù)，

7、且滿(mǎn)足是正整數(shù)，且滿(mǎn)足gcd（a，b）=1，a|bc，則，則 a|c定理定理6 證明思路：利用定理證明思路：利用定理5和定理和定理1（3）（）（4）2/13/2022 2:56 PM13定義定義3 若一個(gè)大于若一個(gè)大于1的正整數(shù)的正整數(shù)p除了除了1和和p之外沒(méi)有其它之外沒(méi)有其它正因子，則稱(chēng)正因子，則稱(chēng)p是一個(gè)是一個(gè)質(zhì)數(shù)質(zhì)數(shù)（或（或素?cái)?shù)素?cái)?shù)/prime）。一個(gè)既不）。一個(gè)既不是質(zhì)數(shù)也不是是質(zhì)數(shù)也不是1的正整數(shù)稱(chēng)為的正整數(shù)稱(chēng)為合數(shù)合數(shù)/composite。定義定義4 設(shè)設(shè)b是是a的一個(gè)因子，如果的一個(gè)因子，如果b本是質(zhì)數(shù)，則稱(chēng)本是質(zhì)數(shù)，則稱(chēng)b是是a的一個(gè)的一個(gè)質(zhì)因子質(zhì)因子/ prime facto

8、r 。2/13/2022 2:56 PM14質(zhì)數(shù)的存在性：質(zhì)數(shù)的存在性：設(shè)設(shè)a是一個(gè)大于是一個(gè)大于1的整數(shù)，則的整數(shù)，則a的大于的大于1的最小因子必的最小因子必是質(zhì)數(shù)。是質(zhì)數(shù)。質(zhì)數(shù)的判定：質(zhì)數(shù)的判定：判斷一個(gè)正整數(shù)是否為質(zhì)數(shù)的局部比較方法。判斷一個(gè)正整數(shù)是否為質(zhì)數(shù)的局部比較方法。設(shè)設(shè)a是一個(gè)大于是一個(gè)大于1的正整數(shù)，只要考慮所有的正整數(shù)，只要考慮所有=1 )這里這里p1 ,p2, ,pk是質(zhì)數(shù)。是質(zhì)數(shù)。2/13/2022 2:56 PM18推論推論2（質(zhì)數(shù)分解定理）（質(zhì)數(shù)分解定理） 任意一個(gè)整數(shù)任意一個(gè)整數(shù)n(n0,n1)可以唯一地表示為可以唯一地表示為 p1r1 p2r2 pkrk這里這里p

9、1 ,p2, ,pk是質(zhì)數(shù)，是質(zhì)數(shù)，r1,r2,rk是正整數(shù)。是正整數(shù)。2/13/2022 2:56 PM19定理定理9（歐幾里德定理）（歐幾里德定理） 所有質(zhì)數(shù)組成的集合是一個(gè)無(wú)限集。所有質(zhì)數(shù)組成的集合是一個(gè)無(wú)限集。例例3、 求整數(shù)求整數(shù)9892的質(zhì)數(shù)標(biāo)準(zhǔn)分解式。的質(zhì)數(shù)標(biāo)準(zhǔn)分解式。2/13/2022 2:56 PM20例例4 金庫(kù)內(nèi)有金庫(kù)內(nèi)有3根同樣粗細(xì)的金條，分別長(zhǎng)根同樣粗細(xì)的金條，分別長(zhǎng)135、243和和558（單位英寸）。現(xiàn)在要把它們截成相等的小（單位英寸）。現(xiàn)在要把它們截成相等的小段，要求小段要最長(zhǎng)。問(wèn)一共可以把這些金條分成幾段，要求小段要最長(zhǎng)。問(wèn)一共可以把這些金條分成幾段，每段幾英

10、寸。段，每段幾英寸。2/13/2022 2:56 PM212、同余關(guān)系、同余關(guān)系定義定義1 設(shè)設(shè)m是一個(gè)正整數(shù)，對(duì)任意兩個(gè)整數(shù)是一個(gè)正整數(shù)，對(duì)任意兩個(gè)整數(shù)a、b，若，若a-b能被能被m整除，則稱(chēng)整除，則稱(chēng)a與與b是是（模（模m）同余的）同余的，或，或（模（模m）合同的合同的/congruent by modulo m ，記為，記為 a b ( mod m) 在在m確定的情況下，簡(jiǎn)記為確定的情況下，簡(jiǎn)記為 a b 。2/13/2022 2:56 PM22定理定理1 設(shè)設(shè)m是一個(gè)正整數(shù)，是一個(gè)正整數(shù)，a、bI，則則a b（mod m)當(dāng)且僅當(dāng)存在一個(gè)整數(shù)當(dāng)且僅當(dāng)存在一個(gè)整數(shù)k 使使 a = km

11、+ b定理定理1證明：證明： a b（mod m) m | (a b) km = a - b a = km+b2/13/2022 2:56 PM23定理定理 2 設(shè)設(shè)m是一個(gè)正整數(shù)，是一個(gè)正整數(shù)，a、b、c、dI，若若a b（mod m)，c d（mod m), 則有則有（1）a c b d (mod m)（2）a c b d (mod m)2/13/2022 2:56 PM24Hashing Function / 哈希函數(shù)哈希函數(shù) 設(shè)一個(gè)查找表設(shè)一個(gè)查找表S有有n個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素S=R1, R2, , Rn。對(duì)于每個(gè)指。對(duì)于每個(gè)指定的定的Ri，設(shè)，設(shè)key是其關(guān)鍵字的值。則建立一個(gè)從是其

12、關(guān)鍵字的值。則建立一個(gè)從Ri.key到到Ri的存貯地的存貯地址函數(shù)址函數(shù)H為為H(Ri. key)=addr(Ri)稱(chēng)稱(chēng)H為為哈希函數(shù)哈希函數(shù)（Hash），函數(shù)值），函數(shù)值H(Ri. key)稱(chēng)為稱(chēng)為哈希地址哈希地址。按。按該方法所建立的表稱(chēng)為該方法所建立的表稱(chēng)為哈希表哈希表。2/13/2022 2:56 PM25定理定理 3 設(shè)設(shè)m是一個(gè)正整數(shù)，是一個(gè)正整數(shù)，a、b、cI，若若ac bc（mod m)，gcd(c, m) = 1 則有則有 a b (mod m)2/13/2022 2:56 PM26定理定理 3證明：證明： 因?yàn)橐驗(yàn)閍c bc（mod m) 有有 m| ac-bc 即即 m|

13、 (a-b)c。 又有定義又有定義gcd(c, m) = 1 則根據(jù)上節(jié)定理則根據(jù)上節(jié)定理6，得到，得到m| (a-b)，即，即 a b (mod m)2/13/2022 2:56 PM27定義定義2 設(shè)設(shè)m是一個(gè)正整數(shù)，對(duì)任意兩個(gè)整數(shù)是一個(gè)正整數(shù)，對(duì)任意兩個(gè)整數(shù)a、b和變和變量量x，若存在，若存在 a x b ( mod m) 則稱(chēng)則稱(chēng)a與與b是是（模（模m）線性同余的）線性同余的/linear congruent （by modulo m）。 當(dāng)當(dāng)b = 1時(shí)，時(shí)，x的解稱(chēng)為的解稱(chēng)為a （模（模m）的逆）的逆/inverse of a modulo m，記為記為 2/13/2022 2:5

14、6 PM28定理定理4 設(shè)設(shè)a與與m互質(zhì)，互質(zhì)，m 1，則，則a 的逆存在。的逆存在。 證明：因?yàn)樽C明：因?yàn)間cd(a, m) = 1 即存在即存在s,t I sa + tm = 1 從而從而 sa + tm 1 ( mod m) 又因?yàn)橛忠驗(yàn)閠m 0 ( mod m) ，根據(jù)定理，根據(jù)定理2（1） 得到得到sa 1 ( mod m) ，s 是是a 的逆。的逆。2/13/2022 2:56 PM29定理定理4推論推論 設(shè)設(shè)a與與m互質(zhì)且互質(zhì)且a、m 為正整數(shù)，為正整數(shù)，ma, 則存在則存在b滿(mǎn)足滿(mǎn)足 ab 1（mod m）2/13/2022 2:56 PM30定理定理5（中國(guó)同余定理（中國(guó)同余

15、定理/孫子定理）孫子定理）例例3：x 2 ( mod 3) x 3 ( mod 5) x 2 ( mod 7)2/13/2022 2:56 PM31例例4：計(jì)算機(jī)系統(tǒng)僅考慮：計(jì)算機(jī)系統(tǒng)僅考慮100以?xún)?nèi)的數(shù)的處理。以?xún)?nèi)的數(shù)的處理。如何對(duì)如何對(duì)x=123684 和和 y = 413456進(jìn)行相加運(yùn)算？進(jìn)行相加運(yùn)算？解的思路：解的思路：取四個(gè)兩兩互質(zhì)的取四個(gè)兩兩互質(zhì)的100的數(shù)的數(shù)99、98、97、95，得到得到x+y的同余數(shù)表達(dá)。再利用中國(guó)同余定理。的同余數(shù)表達(dá)。再利用中國(guó)同余定理。2/13/2022 2:56 PM32定理定理6（Fermat小定理小定理) 設(shè)設(shè)p是一個(gè)質(zhì)數(shù)，是一個(gè)質(zhì)數(shù)，a與與p

16、互質(zhì)，則有互質(zhì)，則有 ap-1 1 ( mod p) 證明思路：考慮多項(xiàng)式證明思路：考慮多項(xiàng)式(1+1+1)p的展開(kāi)式因的展開(kāi)式因子。子。 ap a ( mod p) 2/13/2022 2:56 PM33定理定理6推論推論 設(shè)設(shè)m是是p和和q兩個(gè)質(zhì)數(shù)之積，兩個(gè)質(zhì)數(shù)之積，a與與m互互質(zhì)，則有質(zhì)，則有 a(p-1)(q-1) 1 ( mod m) 證明思路：分別對(duì)證明思路：分別對(duì)p和和q利用定理利用定理6，再利用定理，再利用定理2（2）。）。2/13/2022 2:56 PM34RSA Decryption(Rivest, Schamir, Adleman) 思路：利用質(zhì)數(shù)分解的巨大工作量來(lái)達(dá)到

17、安全思路：利用質(zhì)數(shù)分解的巨大工作量來(lái)達(dá)到安全的目標(biāo)。的目標(biāo)。2/13/2022 2:56 PM35收?qǐng)?bào)方收?qǐng)?bào)方公開(kāi)通訊公開(kāi)通訊發(fā)報(bào)方發(fā)報(bào)方1.確定確定p、q、a、k0.待發(fā)：待發(fā)：x1、x2、xn2、發(fā)出、發(fā)出m、a、km、a、k3、發(fā)出、發(fā)出ci xia (mod m)i=1,2,nc1、c2、cn4、由、由 ci解出解出xi：x cd(mod m)2/13/2022 2:56 PM36例例5：p=47 和和 q = 59 m=pq=2773, (p-1)(q-1)=2668, a=157, d=17, k=2 x=3 3157 441(mod 2773) 44117 3(mod 2773)2/13/2022 2:56 PM37小小 結(jié)結(jié)1、整數(shù)的因子、公因子、整數(shù)的因子、公因子、GCD -EUCLID算法、算法、 GCD的線性