信息安全數(shù)學(xué)基礎(chǔ)第一階段知識總結(jié)第一章整數(shù)的可除性一整除的概念和歐幾里得除法整除的概念定義1設(shè)a、b是兩個整數(shù)，其中b≠0如果存在一個整數(shù)q使得等式a=bq成立，就稱b整除a或者a被b整除，記作b｜a，并謝謝閱讀b叫作a的因數(shù)，把a叫作b的倍數(shù).這時,q也是a的因數(shù)，我們常常將q寫成a／b或感謝閱讀否則,就稱b不能整除a或者a不能被b整除，記作ab。謝謝閱讀整除的基本性質(zhì)（1)當(dāng)b遍歷整數(shù)a的所有因數(shù)時,—b也遍歷整數(shù)a的所有因數(shù)。精品文檔放心下載（2）當(dāng)b遍歷整數(shù)a的所有因數(shù)時,a/b也遍歷整數(shù)a的所有因數(shù)。感謝閱讀（3)設(shè)b,c都是非零整數(shù)，(i）若b|a，則|b｜|｜a|.（ii)若b|a，則bc|ac.（iii）若b|a，則1<｜b|≤|a｜.整除的相關(guān)定理（1）設(shè)a,b≠0，c≠0是三個整數(shù)。若c|b，b｜a，則c｜a.感謝閱讀（2）設(shè)a，b，c≠0是三個整數(shù)，若c|a，c|b,則c|a±b感謝閱讀(3)設(shè)a，b，c是三個整數(shù)。若c｜a,c｜b則對任意整數(shù)s，t，有c|sa+tb.(4）若整數(shù)a1,…，an都是整數(shù)c≠0的倍數(shù)，則對任意n個整數(shù)s1，…，感謝閱讀sn，整數(shù) 是c的倍數(shù)（5)設(shè)a，b都是非零整數(shù).若a｜b，b｜a，則a=±b謝謝閱讀(6)設(shè)a，b,c是三個整數(shù)，且b≠0，c≠0，如果（a,c）=1，則(ab,c）=（b,c）精品文檔放心下載(7)設(shè)a,b，c是三個整數(shù)，且c≠0，如果c｜ab，(a,c)=1,則c｜精品文檔放心下載b.(8）設(shè)p（9)設(shè)a1

是素數(shù)，若,…，an是

pn

｜ab，則p|a或p｜b個整數(shù),p是素數(shù)，若p｜

a1

…an

，則

p

一定整除某一個ak二整數(shù)的表示主要掌握二進制、十進制、十六進制等的相互轉(zhuǎn)化.三最大公因數(shù)和最小公倍數(shù)（一)最大公因數(shù)1．最大公因數(shù)的概念定義：設(shè)是個整數(shù)，若使得,則稱為的一個因數(shù)．公因數(shù)中最大的一精品文檔放心下載個稱為的最大公因數(shù)．記作。若，則稱互素．若，則稱兩兩互素．思考：1．由兩兩互素，能否導(dǎo)出2．由能否導(dǎo)出兩兩互素?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ù),則是(1）中最后一個不等于零的余數(shù)．謝謝閱讀定理3:任意兩個正整數(shù)的任意公因數(shù)都是的因數(shù)．4．性質(zhì)定理4：任意兩個正整數(shù)，則存在整數(shù)，使得成立定理5：設(shè)是不全為零的整數(shù)．（i）若則（ii）若則（iii)若是任意整數(shù)，則從上面定理我們很容易得到下面幾個常用結(jié)論：①且③④5．求兩個以上正整數(shù)的最大公因數(shù)設(shè)則有下面的定理：定理6：若是個正整數(shù)，則只需證①是的一個公因數(shù)．②是的公因數(shù)中最大一個例求解：6．求兩個正整數(shù)的最大公因數(shù)的線性組合(重點掌握)方法一運用輾轉(zhuǎn)相除法求最大公因數(shù)的逆過程；方法二補充的方法方法三運用列表法求解（二）最小公倍數(shù)1．最小公倍數(shù)的定義定義：是個整數(shù)，如果對于整數(shù)，有,那么叫做的一個公倍數(shù)．在的一切公倍數(shù)中最小一個正整數(shù),叫做最小公倍數(shù)．記作．感謝閱讀2．最小公倍數(shù)的性質(zhì)．定理1：設(shè)是任給的兩個正整數(shù)，則（i）的所有公倍數(shù)都是的倍數(shù)．(ii)定理2:設(shè)正整數(shù)是的一個公倍數(shù)，則3．求兩個以上整數(shù)的最小公倍數(shù)定理3：設(shè)是個正整數(shù)，若則只需證：①是的一個公倍數(shù),即,②設(shè)是的任一公倍數(shù)，則例1求解:又四素數(shù)算術(shù)基本定理1．素數(shù)、合數(shù)的概念定義：一個大于1的整數(shù)，如果它的正因數(shù)只有1和它的本身，我們就稱它為素數(shù)，否則就稱為合數(shù)．謝謝閱讀2．性質(zhì)定理1:設(shè)是大于1的整數(shù)，則至少有一個素因數(shù)，并且當(dāng)是合數(shù)時，若是它大于1的最小正因數(shù)，則精品文檔放心下載定理2設(shè)n是一個正整數(shù)，如果對所有地素數(shù)，都有精品文檔放心下載n,則n一定是素數(shù)。求素數(shù)的基本方法：愛拉托斯散篩法。定理3：設(shè)是素數(shù)，是任意整數(shù)，則感謝閱讀或（ii)若則或3．素數(shù)的個數(shù)定理4：素數(shù)的個數(shù)是無窮的．4．算術(shù)基本定理定理5任一整數(shù)n>1都可以表示成素數(shù)的乘積,且在不考慮乘積順序的情況下,該表達式是唯一的。即謝謝閱讀n=p1…ps,p1≤…≤ps,(1)其中pi是素數(shù),并且若n=q1 …qt，q1≤…≤qt,其中qj是素數(shù),精品文檔放心下載則s=t,pi=qj, 1≤i≤s.感謝閱讀推論1：設(shè)是任一大于1的整數(shù)，且為素數(shù)，且則是的正因數(shù)的充分必要條件是推論2:且感謝閱讀為素數(shù)．則第二章同余一同余概念和基本性質(zhì)<一〉、同余的定義．定義：如果用去除兩個整數(shù)所得的余數(shù)相同，則稱整數(shù)關(guān)于模同余，記作如果余數(shù)不同,則稱關(guān)于模不同余，記作.定理1：整數(shù)關(guān)于模同余充分必要條件是精品文檔放心下載<二>、性質(zhì)．定理2：同余關(guān)系是一種等價關(guān)系，即滿足(1）自反性：（2）對稱性：若(3）傳遞性：若定理3：若則：定理4：若且則定理5：若且則定理6:若，則定理7：若且則定理8：若則定理9設(shè)整數(shù)n有十進制表示式:n=a10+a10+…+a10+a,0≤a<10則3｜n的kk—1kk-11;0i充分必要條件是3|a+…+ak0+…+a。而9｜n的充分必要條件是9|ak0定理10設(shè)整數(shù)n有1000進制表示式:n=a1000k+…+a1000+a，0≤a〈1000k10i則7(或11，或13)｜n的充分必要條件是7(或11，或13)能整除整數(shù)精品文檔放心下載(a0+a2+…)–（a1+a3+…）精品文檔放心下載例1:求7除的余數(shù)．解：除的余數(shù)為4．例2：求的個位數(shù)．解：的個位數(shù)為．二完全剩余系和互素剩余系<一>、剩余類．1．定義1：設(shè)是一個給定的正整數(shù)．則叫做模的剩余類．定理1：設(shè)是模的剩余類，則有（1）中每一個整數(shù)必屬于這個類中的一個，且僅屬于一個．（2）中任意兩個整數(shù)屬于同一類的充要條件是感謝閱讀<二>、完全剩余系1．定義2：在模的剩余類中各取一個數(shù)則個整數(shù)稱為模的一組完全剩余系．精品文檔放心下載任意個連續(xù)的整數(shù)一定構(gòu)成模的一組完全剩余系．2．形成完全剩余系的充要條件．定理2：個整數(shù)形成模的完全剩余系的充要條件是:3．完全剩余系的性質(zhì)．定理3：若則當(dāng)遍歷模的完全剩余系時，則也遍歷模的完全剩余系．定理4設(shè)m是一個正整數(shù)，a是滿足(a，m）=1的整數(shù)，則存在整數(shù)a’感謝閱讀1≤a’〈m,使得aa’≡1（mod m）定理5：若當(dāng)分別遍歷模的完全剩余系時，則也遍歷模的完全剩余系．謝謝閱讀例1：問是否構(gòu)成模的完全剩余系？解：是的一個排列．能構(gòu)成模的一組完全剩余系．〈三〉簡化剩余系1、簡化剩余類、簡化剩余系概念．定義3：若模的某一剩余類里的數(shù)與互素，則把它稱為模的一個互素剩余類．在與模互素的全部剩余類中,各取出一整數(shù)組成的系，叫做模的一組簡化剩余系．謝謝閱讀在完全剩余系中所有與模互素的整數(shù)構(gòu)成模的簡化剩余系．謝謝閱讀2．簡化剩余系的個數(shù)．定義4：歐拉函數(shù)是定義在正整數(shù)集上的函數(shù),的值等于精品文檔放心下載序列與互素的個數(shù)．為素數(shù)定理6：個整數(shù)構(gòu)成模的簡化剩余系的充要條件是定理7：若遍歷模的簡化剩余系，則也遍歷模的謝謝閱讀簡化剩余系定理8設(shè)m1，m2是互素的兩個正整數(shù),如果x1,x2分別遍歷模 m1精品文檔放心下載m2的簡化剩余系，則m2x1+m1x2遍歷模m1m2的簡化剩余系.定理9:若，則謝謝閱讀<三>歐拉定理費馬小定理威爾遜定理1． 歐拉定理設(shè)m是大于1的整數(shù)，如果a是滿足(a，m)=1的整謝謝閱讀數(shù)，則2．費馬定理 設(shè)p是一個素數(shù),則對任意整數(shù)a，我們有感謝閱讀ap≡a（modp)3．（wilson）設(shè)p是一個素數(shù)。則<四>模重復(fù)平方計算法主要掌握運用該方法解題過程第三章同余式1．同余式的定義定義1設(shè)m是一個正整數(shù)，設(shè)f（x)為多項式謝謝閱讀其中ai是整數(shù),則f（x)≡0（modm）(1)叫作模m同余式.若謝謝閱讀(modm),則n叫做f(x）的次數(shù)，記作degf。此時，(1）式又叫做模m的n次同余式.謝謝閱讀2．同余式的解、解數(shù)及通解表達式定理1設(shè)m是一個正整數(shù)，a是滿足am的整數(shù)則一次同余式謝謝閱讀ax≡b(modm)有解的充分必要條件是(a，m)|b，而且,當(dāng)同余式有解時,其解數(shù)為d=（a,m).感謝閱讀定理2設(shè)m是一個正整數(shù)，a是滿足(a，m）=1的整數(shù)，則一次同余謝謝閱讀ax≡1（modm）有唯一解x≡a’(modm）.精品文檔放心下載定理3設(shè)m是一個正整數(shù),a是滿足(a，m）｜b的整數(shù),則一次同余式謝謝閱讀ax≡b(modm)的全部解為3．中國剩余定理定理1（中國剩余定理)設(shè)是k個兩兩互素的正整數(shù),則對任意的整數(shù)，謝謝閱讀同余式組一定有解，且解是唯一的1計算解一利用2。4定理1（Euler定理)及模重復(fù)平方計算法直接計算.精品文檔放心下載因為77＝7·11，所以由2。4定理1(Euler定理），，又1000000＝16666·60＋40，所以，設(shè)m=77,b=2，令a=1。40寫成二進制,40＝23＋25，運用模重復(fù)平方法,我們依次計算如下:精品文檔放心下載（1)（2) n1=0，計算（3) n2=0，計算（4） n3=1，計算n4=0,計算n6=1，計算最后，計算出解二令,因為77=7·11,所以計算x(mod77)精品文檔放心下載等價于求解同余式組因為Euler定理給出，以及1000000=166666·6+4，所以。,分別求解同余式,得到x≡2·11·2+8·7·1≡100≡23（mod77)謝謝閱讀因此,21000000≡23(mod 77)例2：解同余式組解:原同余式組有解且同解于兩兩互素同余式組有惟一解．原同余式組的解為第四章二次同余式與平方剩余1．二次同余式的定義定義1設(shè)m是正整數(shù)，若同余式有解，則a叫做模m的平方剩余（二次剩余)；否則,a叫做模m的平謝謝閱讀方非剩余（或二次非剩余)。模為奇素數(shù)的平方剩余和平方非剩余討論模為素數(shù)p的二次同余式定理1（歐拉判別條件）設(shè)p是奇素數(shù)，（a,p)=1，則感謝閱讀i）a是模p的平方剩余的充分必要條件是（ii）a是模p的平方非剩余的充分必要條件是并且當(dāng)a是模p的平方剩余時,同感謝閱讀余式（1）恰有二解.定理2設(shè)p是奇素數(shù)，則模p的簡化剩余系中平方剩余與平方非剩余的個數(shù)各為(p-1)/2,且（p—1)/2個平方剩余與序列：中的一個數(shù)同余。且僅與一個數(shù)同余。謝謝閱讀1利用定理判斷3。勒讓德符號定義1設(shè)p是素數(shù)，定義勒讓德符號如下：歐拉判別法則設(shè)p是奇素數(shù),則對任意整數(shù)a,常用定理及結(jié)論p是奇素數(shù)，則（1）(2)(3)(4)(5)設(shè)（a，p）=1，則（7）設(shè)p是奇素數(shù)，如果整數(shù)a,b滿足a≡b(mod p），則（8）（9)互倒定律若p，q是互素奇素數(shù)，則1，而所以第五章指數(shù)與原根一指數(shù)1．指數(shù)的定義定義1設(shè)m>1是整數(shù),a是與m互素的正整數(shù)，則使得成立的最小精品文檔放心下載正整數(shù)e叫做a對模m的指數(shù),記作。2．指數(shù)的性質(zhì)定理1設(shè)m〉1是整數(shù)，a是與m互素的整數(shù)，則整數(shù)d使得的充分必要條件是。精品文檔放心下載定理1之推論設(shè)m〉1是整數(shù)，a是與m互素的整數(shù),則性質(zhì)1設(shè)m〉1是整數(shù)，a是與m互素的整數(shù)感謝閱讀若b≡a（modm)，則（ii）設(shè)使得則。性質(zhì)2設(shè)m〉1是整數(shù)，a是與m互素的整數(shù)，則的充分必要條件謝謝閱讀是性質(zhì)3設(shè)m>1是整數(shù),a是與m互素的整數(shù)設(shè)d≥0,為整數(shù)，則二原根感謝閱讀1． 原根的定義定義若（a，m)=1，如果a對模m的指數(shù)是，即則a叫做模m的原謝謝閱讀根2．原根的相關(guān)定理及性質(zhì)定理1設(shè)m〉1是整數(shù),a是與m互素的整數(shù)。則模m兩兩不同余，特別地，當(dāng)a是模m的原根，即時，這個數(shù)組成模m的簡化剩余系定理2設(shè)m>1是整數(shù)，g是模m的原根，設(shè)d≥0為整數(shù)，則是模m的原根當(dāng)且僅當(dāng)謝謝閱讀3． 原根存在的條件定理1設(shè)p是奇素數(shù)，則模p的原根存在.定理2