信息安全數(shù)學基礎(chǔ)第一階段知識總結(jié)

信息安全數(shù)學基礎(chǔ)第一階段知識總結(jié)第一章整數(shù)得可除性一整除得概念與歐幾里得除法1整除得概念定義1設(shè)a、b就是兩個整數(shù)，其中b≠0如果存在一個整數(shù)q使得等式a=bｑ成立，就稱b整除a或者ａ被ｂ整除，記作b|a,并把b叫作a得因數(shù),把a叫作b得倍數(shù)、這時，q也就是a得因數(shù),我們常常將ｑ寫成a/b或否則,就稱b不能整除a或者a不能被b整除,記作ab、2整除得基本性質(zhì)(1)當b遍歷整數(shù)a得所有因數(shù)時,－b也遍歷整數(shù)a得所有因數(shù)、（2)當ｂ遍歷整數(shù)a得所有因數(shù)時,a/b也遍歷整數(shù)a得所有因數(shù)、（3)設(shè)b，c都就是非零整數(shù)，(i）若b|a,則|b|｜|ａ|、(ｉｉ)若ｂ｜a,則ｂｃ|aｃ、(iii)若b|a,則1〈|b｜≤|ａ|、3整除得相關(guān)定理（1)設(shè)a,ｂ≠0,c≠０就是三個整數(shù)、若c｜b,b|a,則ｃ|a、(２)設(shè)a，b，c≠０就是三個整數(shù),若ｃ|ａ,ｃ|b,則ｃ｜a±b(3）設(shè)a，b,c就是三個整數(shù)、若c｜a，ｃ|b則對任意整數(shù)s，t,有c|ｓa+tb、(４）若整數(shù)a１,…,aｎ都就是整數(shù)c≠0得倍數(shù)，則對任意n個整數(shù)s１,…,ｓｎ，整數(shù)就是c得倍數(shù)（5）設(shè)a，b都就是非零整數(shù)、若a|b,ｂ|a,則a=±b(6)設(shè)a,ｂ，c就是三個整數(shù),且b≠0,c≠0,如果(a,c）=1,則(ab,ｃ)＝（ｂ，c）(7)設(shè)ａ，b,c就是三個整數(shù),且ｃ≠0，如果c｜ａb，（a,ｃ）＝1,則c｜b、（8）設(shè)ｐ就是素數(shù)，若ｐ|ab,則p|a或p|b（9）設(shè)a1，…,an就是n個整數(shù)，p就是素數(shù),若ｐ｜a1…an，則p一定整除某一個ａk二整數(shù)得表示主要掌握二進制、十進制、十六進制等得相互轉(zhuǎn)化、三最大公因數(shù)與最小公倍數(shù)（一)最大公因數(shù)1．最大公因數(shù)得概念定義:設(shè)就是個整數(shù),若使得,則稱為得一個因數(shù)。公因數(shù)中最大得一個稱為得最大公因數(shù)。記作、若，則稱互素。若,則稱兩兩互素。?思考:１.由兩兩互素，能否導出2。由能否導出兩兩互素？２。最大公因數(shù)得存在性（1)若不全為零,則最大公因數(shù)存在并且(2)若全為零,則任何整數(shù)都就是它得公因數(shù)。這時,它們沒有最大公因數(shù)．3.求兩個正整數(shù)得最大公因數(shù)。定理1：設(shè)任意三個不全為零得整數(shù)，且則輾轉(zhuǎn)相除法由帶余除法得（1）……因為每進行一次帶余除法，余數(shù)至少減少1，且就是有限整數(shù),故經(jīng)過有限次帶余除法后,總可以得到一個余數(shù)就是零得情況，即由(1)知，

定理2：任意兩個正整數(shù),則就是(１）中最后一個不等于零得余數(shù).定理３:任意兩個正整數(shù)得任意公因數(shù)都就是得因數(shù)。4.性質(zhì)定理4:任意兩個正整數(shù),則存在整數(shù)，使得成立?定理5:設(shè)就是不全為零得整數(shù)。（ｉ)若則(ii)若則(ｉii)若就是任意整數(shù)，則從上面定理我們很容易得到下面幾個常用結(jié)論:①②且?③④5.求兩個以上正整數(shù)得最大公因數(shù)

設(shè)則有下面得定理:

定理6:若就是個正整數(shù),則只需證①就是得一個公因數(shù)．②就是得公因數(shù)中最大一個例求解:6．求兩個正整數(shù)得最大公因數(shù)得線性組合（重點掌握)方法一運用輾轉(zhuǎn)相除法求最大公因數(shù)得逆過程;方法二補充得方法方法三運用列表法求解（二）最小公倍數(shù)１.最小公倍數(shù)得定義?定義：就是個整數(shù)，如果對于整數(shù),有,那么叫做得一個公倍數(shù).在得一切公倍數(shù)中最小一個正整數(shù)，叫做最小公倍?數(shù).記作。

2.最小公倍數(shù)得性質(zhì)。?定理1:設(shè)就是任給得兩個正整數(shù)，則（ｉ)得所有公倍數(shù)都就是得倍數(shù).(ii)定理２：設(shè)正整數(shù)就是得一個公倍數(shù)，則3。求兩個以上整數(shù)得最小公倍數(shù)定理３:設(shè)就是個正整數(shù),若

則只需證:①就是得一個公倍數(shù)，即,②設(shè)就是得任一公倍數(shù)，則例1求

解:又???四素數(shù)算術(shù)基本定理1．素數(shù)、合數(shù)得概念?定義:一個大于1得整數(shù)，如果它得正因數(shù)只有１與它得本身,我們就稱它為素數(shù)，否則就稱為合數(shù)。2.性質(zhì)?定理1:設(shè)就是大于1得整數(shù),則至少有一個素因數(shù)，并且當就是合數(shù)時，若就是它大于1得最小正因數(shù),則定理2設(shè)n就是一個正整數(shù)，如果對所有地素數(shù),都有pn，則n一定就是素數(shù)、求素數(shù)得基本方法：愛拉托斯散篩法。定理3:設(shè)就是素數(shù),就是任意整數(shù)，則(i)或(ii)若則或3．素數(shù)得個數(shù)?定理4：素數(shù)得個數(shù)就是無窮得.4。算術(shù)基本定理定理5任一整數(shù)ｎ〉1都可以表示成素數(shù)得乘積，且在不考慮乘積順序得情況下，該表達式就是唯一得、即n=ｐ1…pｓ，p1≤…≤ps,(1)其中pi就是素數(shù),并且若ｎ=q1…qｔ,q1≤…≤qt，其中qj就是素數(shù),則ｓ=t,pi=ｑj,１≤i≤ｓ、推論1:設(shè)就是任一大于1得整數(shù),且為素數(shù)，且則就是得正因數(shù)得充分必要條件就是

推論２：且為素數(shù).則第二章同余一同余概念與基本性質(zhì)〈一>、同余得定義.?定義:如果用去除兩個整數(shù)所得得余數(shù)相同,則稱整數(shù)關(guān)于模同余，記作如果余數(shù)不同，則稱關(guān)于模不同余，記作、定理１：整數(shù)關(guān)于模同余充分必要條件就是〈二〉、性質(zhì)。?定理2：同余關(guān)系就是一種等價關(guān)系,即滿足(１)自反性:(2）對稱性:若(3)傳遞性：若

定理3:若則:定理４:若且則定理５:若且則定理６：若,則?定理7:若且則

定理8:若則定理9設(shè)整數(shù)n有十進制表示式：n=ａk１0k+ａk—1１0k—1+…+a1１0+a0，0≤ａi<10則3|n得充分必要條件就是3|ak+…+a0;而９｜n得充分必要條件就是9|ak+…+a0、定理10設(shè)整數(shù)n有１000進制表示式:ｎ＝ａk１０００ｋ＋…+a110０0+ａ0,0≤ai〈10０0則7(或11，或1３）|n得充分必要條件就是７(或11，或1３)能整除整數(shù)(a0＋a2+…）–(a1+a3+…）例１:求７除得余數(shù).

解:除得余數(shù)為4。

例2:求得個位數(shù).

解:得個位數(shù)為。

二完全剩余系與互素剩余系<一>、剩余類.?1。定義１：設(shè)就是一個給定得正整數(shù).則叫做模得剩余類。?定理１：設(shè)就是模得剩余類，則有（1）中每一個整數(shù)必屬于這個類中得一個,且僅屬于一個.(2）中任意兩個整數(shù)屬于同一類得充要條件就是?<二>、完全剩余系?1.定義2：在模得剩余類中各取一個數(shù)則個整數(shù)稱為模得一組完全剩余系。任意個連續(xù)得整數(shù)一定構(gòu)成模得一組完全剩余系.2.形成完全剩余系得充要條件．?定理2:個整數(shù)形成模得完全剩余系得充要條件就是：?3．完全剩余系得性質(zhì)．

定理３：若則當遍歷模得完全剩余系時,則?也遍歷模得完全剩余系。定理4設(shè)ｍ就是一個正整數(shù),a就是滿足(a,m）=1得整數(shù),則存在整數(shù)a’1≤a’〈ｍ，使得aa’≡１(modｍ）定理5：若當分別遍歷模得完全剩余系時,則也遍歷模得完全剩余系.例1:問就是否構(gòu)成模得完全剩余系?

解：

就是得一個排列。能構(gòu)成模得一組完全剩余系．

〈三〉簡化剩余系?1、簡化剩余類、簡化剩余系概念.?定義３:若模得某一剩余類里得數(shù)與互素,則把它稱為模得一?個互素剩余類。在與模互素得全部剩余類中，各取出一整

數(shù)組成得系,叫做模得一組簡化剩余系。在完全剩余系中所有與?；ニ氐谜麛?shù)構(gòu)成模得簡化剩余系.2.簡化剩余系得個數(shù).?定義4:歐拉函數(shù)就是定義在正整數(shù)集上得函數(shù),得值等于?序列與互素得個數(shù)。為素數(shù)定理６:個整數(shù)構(gòu)成模得簡化剩余系得充要條件就是

定理7：若遍歷模得簡化剩余系,則也遍歷模得

簡化剩余系定理8設(shè)m1,m2就是互素得兩個正整數(shù),如果x１,ｘ２分別遍歷模m1與m2得簡化剩余系,則m2x１+m1x2遍歷模m1ｍ2得簡化剩余系、定理9：若，則〈三＞歐拉定理費馬小定理威爾遜定理歐拉定理設(shè)m就是大于1得整數(shù)，如果a就是滿足(ａ，m)=1得整數(shù)，則2.費馬定理設(shè)p就是一個素數(shù)，則對任意整數(shù)a,我們有ａp≡ａ(modp）3．(wilsoｎ）設(shè)p就是一個素數(shù)、則<四〉模重復平方計算法主要掌握運用該方法解題過程第三章同余式1.同余式得定義定義1設(shè)m就是一個正整數(shù),設(shè)ｆ(x）為多項式其中ａi就是整數(shù),則ｆ（x)≡0（moｄm）（1)叫作模ｍ同余式、若0（mｏdm),則ｎ叫做f（x)得次數(shù),記作deｇf、此時，（1）式又叫做模ｍ得ｎ次同余式、2.同余式得解、解數(shù)及通解表達式定理1設(shè)m就是一個正整數(shù),ａ就是滿足am得整數(shù)則一次同余式ａｘ≡ｂ(ｍodｍ）有解得充分必要條件就是（a，ｍ)|b，而且，當同余式有解時,其解數(shù)為d=（ａ，m)、定理2設(shè)ｍ就是一個正整數(shù)，a就是滿足(ａ，m)=1得整數(shù)，則一次同余式aｘ≡１（modm)有唯一解ｘ≡a’(mｏdm)、定理3設(shè)m就是一個正整數(shù),a就是滿足（a，ｍ）|ｂ得整數(shù),則一次同余式ax≡b（modｍ)得全部解為3.中國剩余定理定理1（中國剩余定理)設(shè)就是k個兩兩互素得正整數(shù)，則對任意得整數(shù),同余式組一定有解，且解就是唯一得例1計算解一利用２、4定理1（Eulｅｒ定理）及模重復平方計算法直接計算、因為77=7·11,所以由２、4定理１（Ｅｕler定理),,又1000000=166６６·60+40,所以,設(shè)ｍ=77，b=2,令a=1、將40寫成二進制,40＝2３+２5,運用模重復平方法,我們依次計算如下:（1）（2)n1=0，計算（3）n2=0，計算(4）n3=1,計算(5)n4＝0,計算（6)ｎ６=1，計算最后，計算出解二令,因為７7=7·11，所以計算x(moｄ77)等價于求解同余式組因為Eulｅr定理給出,以及１000000＝16６666·6+4，所以、令，分別求解同余式,得到故x≡2·11·2+8·7·1≡1００≡２3(mｏd77）因此,2≡23(ｍoｄ７7）例2:解同余式組?解:原同余式組有解且同解于兩兩互素同余式組有惟一解。

原同余式組得解為第四章二次同余式與平方剩余1。二次同余式得定義定義１設(shè)m就是正整數(shù),若同余式有解，則ａ叫做模ｍ得平方剩余（二次剩余）;否則，a叫做模m得平方非剩余（或二次非剩余)、模為奇素數(shù)得平方剩余與平方非剩余討論模為素數(shù)ｐ得二次同余式定理１（歐拉判別條件)設(shè)p就是奇素數(shù)，（ａ,p)=1,則(ｉ）a就是模p得平方剩余得充分必要條件就是(ｉｉ）a就是模p得平方非剩余得充分必要條件就是并且當ａ就是模p得平方剩余時,同余式（１)恰有二解、定理２設(shè)ｐ就是奇素數(shù),則模ｐ得簡化剩余系中平方剩余與平方非剩余得個數(shù)各為（p—１)／2,且(p—1)/2個平方剩余與序列：中得一個數(shù)同余、且僅與一個數(shù)同余、例1利用定理判斷3、勒讓德符號定義1設(shè)p就是素數(shù),定義勒讓德符號如下:歐拉判別法則設(shè)ｐ就是奇素數(shù)，則對任意整數(shù)a,常用定理及結(jié)論設(shè)ｐ就是奇素數(shù),則(1)(2)（3）（4)（５)(６)設(shè)（a，ｐ)=1，則(7）設(shè)p就是奇素數(shù)，如果整數(shù)ａ，ｂ滿足a≡b(modp)，則(8）(９）互倒定律若p,ｑ就是互素奇素數(shù),則例1,而所以第五章指數(shù)與原根一指數(shù)1．指數(shù)得定義定義1設(shè)m〉1就是整數(shù)，a就是與m互素得正整數(shù),則使得成立得最小正整數(shù)e叫做a對模ｍ得指數(shù),記作、2.指數(shù)得性質(zhì)定理1設(shè)m>1就是整數(shù),a就是與m互素得整數(shù)，則整數(shù)d使得得充分必要條件就是、定理1之推論設(shè)m〉1就是整數(shù)，ａ就是與ｍ互素得整數(shù)，則性質(zhì)1設(shè)m>1就是整數(shù),a就是與m互素得整數(shù)若b≡ａ(mｏdm)，則(ｉi)設(shè)使得則、性質(zhì)2設(shè)m＞1就是整數(shù)，a就是與m互素得整數(shù),則得充分必要條件就是性質(zhì)3設(shè)m〉1就是整數(shù)，a就是與m互素得整數(shù)設(shè)ｄ≥0，為整數(shù),則二原根原根得定義定義若（a,m)=1,如果a對模m得指數(shù)就是,即則ａ叫做模ｍ得原根2.原根得相關(guān)定理及性質(zhì)定理1設(shè)m〉１就是整數(shù),a就是與ｍ互素得整數(shù)、則模m兩兩不同余,特別地，當a就是模m得原根，即時,這個數(shù)組成模m得簡化剩余系定理2設(shè)m＞1就是整數(shù),ｇ就是模m得原根，設(shè)d≥0為整數(shù)，則就是模m得原根當