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

2020/4/26,.,電子科技大學(xué)計算機科學(xué)與工程學(xué)院,計算系統(tǒng)與網(wǎng)絡(luò)安全ComputerSystemandNetworkSecurity,2020/4/26,.,子夏曰：“賢賢易色；事父母，能竭其力；事君，能致其身；與朋友交，言而有信。雖日未學(xué)，吾必謂之學(xué)矣?！比穗H關(guān)系：父子；君臣；朋友；夫妻,數(shù)論基礎(chǔ),2020/4/26,.,第2章信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）,2020/4/26,.,第2章信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）,2020/4/26,.,2.整除的基本性質(zhì)(N整數(shù)集)(1)a(a0),a|0,a|a(同理bN,1|b)(2)b|a,cb|ca(3)a|b,b|ca|c.（傳遞性）(4)a|b,a|ca|(xb+yc)(x,yN)(5)b|a且a0|b|a|(6)cb|ca,b|a,1.定義：設(shè)整數(shù)a和b,且a0，如果存在整數(shù)k使得b=ak，那么就說a整除a（或b能被a整除），記作a|b，或者說b是a的倍數(shù)。舉例：3|15,-15|60,整除定義及性質(zhì),2020/4/26,.,證明：（1）作一個整數(shù)序列（2）反證法,帶余數(shù)除法：如果a，b是兩個整數(shù)，其中b0，則存在兩個整數(shù)q和r，使得abqr（0rb）成立，且q和r是唯一的。,帶余數(shù)除法,2020/4/26,.,非負(fù)最小剩余的性質(zhì)：（1）=+（2）=-（3）=,定義（非負(fù)最小剩余）abqr（0rb）中r叫做非負(fù)最小剩余，常記做b=r（在不致引起混淆的情況下，b常常省略）,帶余數(shù)除法,2020/4/26,.,1.定義：一個大于1的整數(shù)p，只能被1或者是它本身整除,而不能被其他整數(shù)整除，則稱整數(shù)為素數(shù)(primenumber)，否則就叫做合數(shù)(composite)。eg素數(shù)（2，3，5，7，11，13等）合數(shù)（4，6，8，9，12等）,素數(shù)定義及素數(shù)個數(shù)定理,2020/4/26,.,2.補充定理(1)：設(shè)a是任一大于1的整數(shù)，則a的除1外的最小正因子q是素數(shù)，并且當(dāng)a是合數(shù)時：,素數(shù)補充定理,2020/4/26,.,2.補充定理(2)：若p是一個素數(shù)，a是任一整數(shù)，則有p|a或(p,a)=1,素數(shù)補充定理（續(xù)）,2020/4/26,.,素數(shù)補充定理（續(xù)）,2.補充定理：p為素數(shù)，且p|ab,那么p|a或p|b。更一般地，如果abz能夠被素數(shù)p整除，那么a,b,z中的某個數(shù)必能被p整除。,2020/4/26,.,3.素數(shù)個數(shù)定理（1）：素數(shù)的個數(shù)是無限的,原因：（1）N（N1）的除1外的最小正因數(shù)q是一個素數(shù)（2）如果q=pi，（i1,2,k),且q|N，因此q|(N-p1p2,.pk)，所以q|1，與q是素數(shù)矛盾。,素數(shù)個數(shù)定理及證明,證明：反證法假設(shè)正整數(shù)個數(shù)是有限的，設(shè)為p1,p2,.,pk令：p1p2pk+1=N(N1)則N有一個素數(shù)p，且ppi（i=1,2,k).故p是上述k個素數(shù)外的另外一個素數(shù)。因此與假設(shè)矛盾。,2020/4/26,.,素數(shù)定義及素數(shù)個數(shù)定理,3.素數(shù)個數(shù)定理（2）：設(shè)(x)是小于x的素數(shù)個數(shù)，則(x)x/lnx,即x時，比值(x)/(x/lnx)1eg:可以估算100位素數(shù)的個數(shù)：(10100)-(1099)10100/(ln10100)1099/(ln1099)3.9*1097.,2020/4/26,.,1.整數(shù)的唯一分解定理定理（算術(shù)基本定理）:設(shè)nZ,有分解式,n=p1e1p2e2.pmem,其中p1,p2,pmZ+是互不相同的素數(shù),e1,e2,emZ+,并且數(shù)對(p1,e1),(p2,e2),(pm,em)由n唯一確定（即如果不考慮順序，n的分解是唯一的）.,eg:504=23327,1125=3253,整數(shù)的唯一分解定理,2020/4/26,.,1.定義兩個整數(shù)a,b的最大公約數(shù)，就是能同時整除a和b的最大正整數(shù),記為gcd(a,b)，或(a,b).eg:gcd(5,7)=1，gcd(24,60)=12，,最大公約數(shù)定義及求法,2.求最大公約數(shù)的兩種方法：(1)因數(shù)分解：eg:1728=2632,4536=23347,gcd(1728,4536)=2332=72.,2020/4/26,.,(2)歐幾里得(Euclid)算法設(shè)a,bN,ab0,用以下方法可求出gcd(a,b).,最大公約數(shù)的歐幾里得算法,2020/4/26,.,Euclid算法實例：求gcd(132,108).,最大公約數(shù)的歐幾里得算法（續(xù)）,2020/4/26,.,歐幾里得算法（例1）,gcd（1180，482）2,求：gcd（1180，482）,最大公約數(shù)的歐幾里得算法（續(xù)）,2020/4/26,.,歐幾里得算法（例2）：求gcd(12345,1111),最大公約數(shù)的歐幾里得算法（續(xù)）,2020/4/26,.,歐幾里得算法抽象,規(guī)律：余數(shù)除數(shù)被除數(shù)忽略,最大公約數(shù)的歐幾里得算法（續(xù)）,2020/4/26,.,歐幾里得算法實現(xiàn),最大公約數(shù)的歐幾里得算法（續(xù)）,2020/4/26,.,特別a,b為素數(shù)時gcd(a,b)=1，存在ma+nb=1.上述求rn=ma+nb的方法叫做擴展的Euclid算法利用該方法我們可以求ax+by=d的解,這里d=(a,b),證明：根據(jù)Euclid算法a=bq1+r1b=r1q2+r2r1=r2q3+r3,rn-2=rn-1qn+rngcd(a,b)=rn=rn-2-rn-1qn=ma+nb,3.定理設(shè)a,bZ+,則存在m,nZ使得gcd(a,b)=ma+nb.,擴展的歐幾里得算法,2020/4/26,.,計算出了gcd(a,b);但是并沒有計算出兩個數(shù)m，n來，使得：ma+nb=gcd(a,b),擴展的歐幾里得算法的結(jié)果,計算出了gcd(a,b);計算出兩個數(shù)m，n來，使得：ma+nb=gcd(a,b),擴展的歐幾里得算法（續(xù)）,歐幾里得算法的結(jié)果,2020/4/26,.,利用該方法我們可以求密碼學(xué)方程ax+by=d的解,這里d=(a,b),例如:求132x+108y=12的解,解：12=gcd(132,108)12=108-424=108-4(132-1081)=1084132+4108=5*1084*132,擴展的歐幾里得算法（續(xù)）,2020/4/26,.,第2章信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）,2020/4/26,.,證明：必要性:設(shè)ab(modm),a=mp+r,b=mq+r,0rma-b=m(p-q),m|(a-b).充分性:設(shè)m|(a-b),a=mp+r,b=mq+s,0r,s1，如果gcd(a,n)=1,則:a(n)1modn.,eg:求7803的后三位數(shù)字解：7803（mod1000）的結(jié)果(1000)=1000(1-1/2)(1-1/5)=400，有7803(7400)273343(mod1000),費馬小定理和歐拉定理（續(xù)）,2020/4/26,.,推論（Fermat小定理）:p素數(shù),a是整數(shù)且不能被p整除,則:ap-11modp.,費馬小定理和歐拉定理（續(xù)）,例如：求253(mod11)=?由Fermat小定理:210=10241(mod11)253=(210)52315238(mod11),2020/4/26,.,（1）通常情況下，如果2n-11(modn),n為素數(shù),然而,也有例外:561=31117是合數(shù),但25601(mod561)。因此，如果2n-11(modn),那么n可能為素數(shù)。（2）但2n-1模n不等于1,那么n不可能為素數(shù)這為我們提供一種尋找素數(shù)的方法，給定一個n,計算2n-1模n是否等于1，如果不等于1，n為非素數(shù)，如果等于1，還需用更復(fù)雜的方法來判斷是否為素數(shù)，比如：(1)索洛維-斯特拉森(Solovay-Strassen)素性檢測算法(2)米勒-羅賓(Miller-Rabin)素性檢測算法(3)AKS算法,費馬小定理和歐拉定理的應(yīng)用,2020/4/26,.,解：（1）由費爾馬定理2100（mod1001）1（mod101）（2）243210(2100)4322102101024(mod101)=14,eg:計算243210（mod101）,歐拉定理的應(yīng)用,2020/4/26,.,7.一次同余式(1)定義:設(shè)mZ+,a,bZ,a0,我們把ax+b0(modm)稱為模數(shù)m的一次同余式.如果x0Z滿足:ax0+b0(modm)則稱xx0(modm)是同余式的解.eg:同余式2x+10(mod3)有解x0=1.同余式2x+10(mod4)無解.同余式2x+10(mod5)有解x0=2.,一次同余式,2020/4/26,.,(2)一次同余式的解定理1:設(shè)mZ+,a,bZ,a0,(a,m)=1,則同余式axb(modm)恰有一個解xba(m)-1(modm).eg:同余式2x+10(mod5)有解:x0=(-1)2(5)-1423322(mod5),一次同余式（續(xù)）,2020/4/26,.,定理2:設(shè)mZ+,a,bZ,a0,(a,m)=d,則同余式axb(modm)有解的充要條件是d|b.在d|b的條件下,同余式有d個解.eg:同余式2x3(mod4)無解d=(2,4)=23.同余式2x4(mod6)d=(2,6)=2|4有2個解:x=2,5.,一次同余式的解,2020/4/26,.,第2章信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）,2020/4/26,.,孫子算經(jīng)中記載著一道世界聞名的“孫子問題”：“今有無不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”孫子問題等同于下面這樣一個問題：已知x=2mod3，x=3mod5且x=2mod7，求整數(shù)x。,中國剩余定理,2020/4/26,.,中國剩余定理（續(xù)）,2020/4/26,.,中國剩余定理（續(xù)）,2020/4/26,.,中國剩余定理（續(xù)）,2020/4/26,.,中國剩余定理(孫子:SunZe,公元前450年,孫子定理)：設(shè)自然數(shù)m1,m2,mr兩兩互素，并記M=m1m2mr，則同余方程組:xb1(modm1)xb2(modm2).xbr(modmr)有唯一解：xb1*M1*y1+b2*M2*y2+br*Mr*yr(modM)Mi=M/mi,yi=Mi-1(modmi)(1ir),中國剩余定理（續(xù)）,2020/4/26,.,例如:求以下同余方程組的解：x5mod7x3mod11x10mod13,中國剩余定理解同余方程組,解：r=3,m1=7,m2=11,m3=13;b1=5,b2=3,b3=10;模M=m1m2m3=1001,M1=M/m1=m2m3=143,M2=91,M3=77.y1=M1-1(modm1)=143-1(mod7)=5,y2=4,y3=12.解為:x=b1M1y1+b2M2y2+b3M3y3(modM)=51435+3914+107712(mod1001)=13907(mod1001)=894驗證:x=894=1277+5=5(mod7),2020/4/26,.,中國剩余定理：,其中：m=miMiMiMi=1(modm),中國剩余定理（續(xù)）,2020/4/26,.,中國剩余定理（續(xù)）,2020/4/26,.,例如（孫子算經(jīng)）解法：表格法,中國剩余定理求解同余方程組,2020/4/26,.,中國剩余定理（續(xù)）,2020/4/26,.,中國剩余定理（續(xù)）,2020/4/26,.,中國剩余定理（續(xù)）,2020/4/26,.,第2章信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）,2020/4/26,.,計算Xa(modn),其中x,a,nZ+Eg:計算21234(mod789)一種有效的方法：2416282562162562492324923426434236721283672559225655923725123725802102458022861234=1024+128+64+16+2（1234=(10011010010)2）21234=286559367494481(mod789),模的冪運算,優(yōu)勢：模的冪運算可快速完成，并且不需要太大內(nèi)存,2020/4/26,.,模的冪運算（續(xù)）,但是，上述計算過程并不適合于計算機程序?qū)崿F(xiàn)。為此，可以采用“重復(fù)平方-乘”運算來進(jìn)行指數(shù)模運算。,2020/4/26,.,模的冪運算（續(xù)）,重復(fù)平方-乘算法,2020/4/26,.,第2章信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）,2020/4/26,.,整數(shù)的次數(shù),由歐拉定理知道：如果(a,m)1，m1，則a(n)1(modm)也就是說，如果(a,m)1，m1，則存在一個整數(shù)滿足:a1(modm),定義（整數(shù)的次數(shù)）：若(a,m)1，m1，則使得同余式a1(modm)成立的最小正整數(shù)叫做a對模m的次數(shù)。,2020/4/26,.,整數(shù)的次數(shù)（續(xù)）,定理：設(shè)a對模數(shù)m的次數(shù)為l，an1（modm），則l|n。,證明：如果結(jié)論不成立，則必有兩個整數(shù)q和r，使得：nqlr（0rl）而1ana(qlr)aqlarar(modm)，因此與l的定義相違背。,推論：設(shè)a對模數(shù)m的次數(shù)為l，則l|(m)。,2020/4/26,.,整數(shù)次數(shù)的計算：因為l|(m)，因此可以通過計算以下對模數(shù)m的值求出。,整數(shù)的次數(shù)（續(xù)）,例如：m7，a2(m)62322（mod7）423（mod7）1因此a對模數(shù)m的次數(shù)為3。,2020/4/26,.,整數(shù)次數(shù)的有效計算方法（1）：,整數(shù)的次數(shù)（續(xù)）,2020/4/26,.,整數(shù)次數(shù)的有效計算方法（1）：,整數(shù)的次數(shù)（續(xù)）,2020/4/26,.,整數(shù)次數(shù)的有效計算方法（2）：,整數(shù)的次數(shù)（續(xù)）,2020/4/26,.,整數(shù)的次數(shù)（續(xù)）,定理：設(shè)a對模數(shù)m的次數(shù)為l，1,a,a2,，al-1對模數(shù)m兩兩不同余。,證明：如果結(jié)論不成立，則有某對j，k（0jkl-1，使得：ajak（modm）因此：ak-j1（modm）而10,(g,m)=1,則g是m的一個原根的充要條件是：g，g2，g(m)組成模數(shù)m的一組縮系。,本原根判斷,定理說明：如果g是m的一個原根，則模數(shù)m的一組縮系可表示為形如定理中的幾何級數(shù)。,2020/4/26,.,2.定理：設(shè)對素數(shù)p而言，如果g是一個本原根(1)如果n是整數(shù)，那么gn1(modp)當(dāng)且僅當(dāng)n0(modp-1)(2)如果j和k都是整數(shù)，那么gjgk當(dāng)且僅當(dāng)jk(modp-1),本原根有關(guān)定理,2020/4/26,.,問題：是否所有的正整數(shù)都有原根？,本原根有關(guān)定理（續(xù)）,例如：m12(m)623，與m互素的正整數(shù)包括5，7，11。52（mod12）1因此，5對12的次數(shù)是272（mod12）1因此7對模數(shù)m的次數(shù)為2112（mod12）1因此11對模數(shù)m的次數(shù)為2因此m12沒有原根。,2020/4/26,.,定理（整數(shù)存在原根的必要條件）：設(shè)m1，若m有原根，則m必為下列諸數(shù)之一：2，4，pl，2pl（l1，p為奇素數(shù)）。,本原根有關(guān)定理（續(xù)）,定理（整數(shù)存在原根的充分條件）：設(shè)m2，4，pl，2pl（l1，p為奇素數(shù)）時，則m有原根。,定理（整數(shù)原根個數(shù)）：設(shè)m有一個原根g，則m恰有(m)個對模數(shù)m不同余的原根，這些原根由以下集合給出：,2020/4/26,.,本原根有關(guān)定理（續(xù)）,2020/4/26,.,原根的判斷：一般來說，判斷g是否時一個素數(shù)m的原根時，不需要逐一計算g1，g2，g(m)，而僅需要計算gt(modm），其中t|(m)。,本原根有關(guān)定理（續(xù)）,2020/4/26,.,本原根有關(guān)定理（續(xù)）,2020/4/26,.,本原根有關(guān)定理（續(xù)）,定理（原根的計算）：,2020/4/26,.,本原根有關(guān)定理（續(xù)）,2020/4/26,.,本原根有關(guān)定理（續(xù)）,2020/4/26,.,本原根有關(guān)定理（續(xù)）,定理（原根的計算）：,2020/4/26,.,本原根有關(guān)定理（續(xù)）,一個計算原根的算法：,2020/4/26,.,本原根有關(guān)定理（續(xù)）,2020/4/26,.,本原根有關(guān)定理（續(xù)）,2020/4/26,.,指數(shù),如果整數(shù)m0有一個元根g，g，g2，g(m)(或數(shù)1,g，g，g2，g(m)-1）組成模數(shù)m的一組縮系。,例如，3是模7的本原根，因此：313322336344355361上述六個數(shù)剛好是模數(shù)m的一組縮系。,2020/4/26,.,指數(shù)（續(xù)）,定義：任一整數(shù)n，（n，m）1，必有唯一的整數(shù)k（0k（m），滿足：ngk（modm）其中k叫做n對模數(shù)m的指數(shù)，記做kindgn（簡記為indn）(指數(shù)也叫做離散對數(shù))。,2020/4/26,.,指數(shù)（續(xù)）,2020/4/26,.,指數(shù)（續(xù)）,2020/4/26,.,指數(shù)（續(xù)）,2020/4/26,.,指數(shù)的性質(zhì)：設(shè)g是m的原根，如果(a,m)(b,m)1：,指數(shù)（續(xù)）,2020/4/26,.,指數(shù)（續(xù)）,2020/4/26,.,指數(shù)（續(xù)）,2020/4/26,.,指數(shù)（續(xù)）,2020/4/26,.,離散對數(shù)困難問題,基于離散對數(shù)困難性假設(shè)，EIGamal提出了EIgamal公鑰密碼體制。,2020/4/26,.,離散對數(shù)困難問題（續(xù)）,2020/4/26,.,第2章信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）,2020/4/26,.,模n逆矩陣,定理：一個平方矩陣是模n可逆的當(dāng)且僅當(dāng)它的行列式和n是互素的.證明：假設(shè)M平方矩陣在模n下有逆矩陣N,則MNI(modn)det(MN)det(M)det(N)det(I)1(modn)因為det(M)可逆(det(M),n)=1Eg:22矩陣,通常的求逆為：ab-1d-b=1/(ad-bc)cd-ca,2020/4/26,.,12假如要求(mod11)的逆34因為ad-bc=-2,需求-2(mod11)的逆，因為5(-2)1(mod11)124-24-2911/(-2)5(mod11)34-31-3175,模n逆矩陣（續(xù)）,2020/4/26,.,第2章信息安全數(shù)學(xué)基礎(chǔ)（數(shù)論）,2020/4/26,.,模n平方根,定義(二次剩余）設(shè)n是一個大于1的正整數(shù)，aZ,a0(modn).如果同余方程x2a(modn)有一個解1xn-1,則稱a是模數(shù)n的二次剩余，而x稱之為a模n的平方根。如果上述方程無解，則a稱之為模數(shù)n的非二次剩余。,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,.,模n平方根（續(xù)）,2020/4/26,