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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上信息安全數(shù)學(xué)基礎(chǔ)第一階段知識(shí)總結(jié)第一章 整數(shù)的可除性一 整除的概念和歐幾里得除法1 整除的概念定義1 設(shè)a、b是兩個(gè)整數(shù)，其中b0如果存在一個(gè)整數(shù) q 使得等式 a=bq 成立，就稱b整除a或者a被b整除，記作b|a ，并把b叫作a的因數(shù)，把a(bǔ)叫作b的倍數(shù).這時(shí)，q也是a的因數(shù)，我們常常將q寫成ab或否則，就稱b不能整除a或者a不能被b整除，記作a b.2整除的基本性質(zhì)(1)當(dāng)b遍歷整數(shù)a的所有因數(shù)時(shí)，-b也遍歷整數(shù)a的所有因數(shù).(2)當(dāng)b遍歷整數(shù)a的所有因數(shù)時(shí)，a/b也遍歷整數(shù)a的所有因數(shù).(3)設(shè)b，c都是非零整數(shù)， (i)若b|a，則|b|a|. (ii)若b|

2、a，則bc|ac.(iii)若b|a，則1<|b|a|.3整除的相關(guān)定理(1) 設(shè)a，b0，c0是三個(gè)整數(shù).若c|b，b|a，則c|a.(2) 設(shè)a，b，c0是三個(gè)整數(shù)，若c|a，c|b，則c|a±b(3) 設(shè)a，b，c是三個(gè)整數(shù).若c|a，c|b則對(duì)任意整數(shù)s，t，有c|sa+tb.(4) 若整數(shù)a1 , ,an都是整數(shù)c0的倍數(shù)，則對(duì)任意n個(gè)整數(shù)s1，sn，整數(shù) 是c的倍數(shù)(5) 設(shè)a，b都是非零整數(shù).若a|b，b|a，則a=±b(6) 設(shè)a, b , c是三個(gè)整數(shù)，且b0，c 0，如果(a , c)=1,則 (ab , c)=(b , c)(7) 設(shè)a , b

3、, c是三個(gè)整數(shù)，且c0，如果cab , (a , c) = 1, 則c | b.(8) 設(shè)p 是素?cái)?shù)，若p |ab , 則p |a或p|b(9) 設(shè)a1 , ,an是n個(gè)整數(shù)，p是素?cái)?shù)，若p| a1 an ,則p一定整除某一個(gè)ak 二 整數(shù)的表示主要掌握二進(jìn)制、十進(jìn)制、十六進(jìn)制等的相互轉(zhuǎn)化.三 最大公因數(shù)和最小公倍數(shù)(一)最大公因數(shù)1最大公因數(shù)的概念定義：設(shè)是個(gè)整數(shù)，若使得 ，則稱為的一個(gè)因數(shù)公因數(shù)中最大的一個(gè)稱為的最大公因數(shù)記作.若 ,則稱 互素若,則稱兩兩互素思考：1由兩兩互素，能否導(dǎo)出 2由 能否導(dǎo)出兩兩互素？2最大公因數(shù)的存在性(1)若 不全為零，則最大公因數(shù)存在并且 (2)若全為零

4、，則任何整數(shù)都是它的公因數(shù)這時(shí)，它們沒(méi)有最大公因數(shù)3求兩個(gè)正整數(shù)的最大公因數(shù)定理1：設(shè)任意三個(gè)不全為零的整數(shù)，且 則輾轉(zhuǎn)相除法 由帶余除法 得 (1) 因?yàn)槊窟M(jìn)行一次帶余除法，余數(shù)至少減少1，且是有限整數(shù)，故經(jīng)過(guò)有限次帶余除法后，總可以得到一個(gè)余數(shù)是零的情況，即 由(1)知， 定理2：任意兩個(gè)正整數(shù),則是(1)中最后一個(gè)不等于零的余數(shù)定理3：任意兩個(gè)正整數(shù)的任意公因數(shù)都是的因數(shù)4性質(zhì)定理4：任意兩個(gè)正整數(shù)，則存在整數(shù)，使得成立定理5：設(shè)是不全為零的整數(shù)(i)若則 (ii)若則 (iii)若是任意整數(shù)，則 從上面定理我們很容易得到下面幾個(gè)常用結(jié)論： 且 5求兩個(gè)以上正整數(shù)的最大公因數(shù)設(shè) 則有下面

5、的定理：定理6：若 是個(gè)正整數(shù)，則只需證是的一個(gè)公因數(shù) 是的公因數(shù)中最大一個(gè)例 求 解： 6求兩個(gè)正整數(shù)的最大公因數(shù)的線性組合（重點(diǎn)掌握） 方法一 運(yùn)用輾轉(zhuǎn)相除法求最大公因數(shù)的逆過(guò)程；方法二 補(bǔ)充的方法方法三 運(yùn)用列表法求解(二) 最小公倍數(shù)1最小公倍數(shù)的定義定義： 是 個(gè)整數(shù)，如果對(duì)于整數(shù)，有 ,那么叫做的一個(gè)公倍數(shù)在 的一切公倍數(shù)中最小一個(gè)正整數(shù)，叫做最小公倍數(shù)記作 2最小公倍數(shù)的性質(zhì)定理1：設(shè)是任給的兩個(gè)正整數(shù)，則 (i)的所有公倍數(shù)都是的倍數(shù) (ii) 定理2：設(shè)正整數(shù)是的一個(gè)公倍數(shù)，則3求兩個(gè)以上整數(shù)的最小公倍數(shù)定理3：設(shè)是個(gè)正整數(shù), 若 則 只需證：是 的一個(gè)公倍數(shù)，即,設(shè)是的任一

6、公倍數(shù),則 例1 求 解： 又 四 素?cái)?shù) 算術(shù)基本定理1素?cái)?shù)、合數(shù)的概念定義：一個(gè)大于1的整數(shù)，如果它的正因數(shù)只有1和它的本身，我們就稱它為素?cái)?shù)，否則就稱為合數(shù)2性質(zhì)定理1：設(shè)是大于1的整數(shù)，則至少有一個(gè)素因數(shù)，并且當(dāng)是合數(shù)時(shí)，若是它大于1的最小正因數(shù)，則定理2 設(shè)n是一個(gè)正整數(shù)，如果對(duì)所有地素?cái)?shù)，都有p n,則n一定是素?cái)?shù). 求素?cái)?shù)的基本方法：愛(ài)拉托斯散篩法。定理3：設(shè)是素?cái)?shù)，是任意整數(shù)，則(i) 或 (ii) 若 則或3素?cái)?shù)的個(gè)數(shù)定理4：素?cái)?shù)的個(gè)數(shù)是無(wú)窮的4 算術(shù)基本定理定理 5 任一整數(shù)n>1都可以表示成素?cái)?shù)的乘積，且在不考慮乘積順序的情況下，該表達(dá)式是唯一的.即n= p1 ps

7、, p1 ps , (1)其中pi 是素?cái)?shù)，并且若n = q1 qt , q1 qt , 其中qj 是素?cái)?shù)，則 s= t , pi = qj, 1 i s. 推論1：設(shè)是任一大于1的整數(shù)，且 為素?cái)?shù)，且 則是的正因數(shù)的充分必要條件是 推論2：且 為素?cái)?shù)則 第二章 同余一 同余概念和基本性質(zhì)<一>、同余的定義定義： 如果用去除兩個(gè)整數(shù)所得的余數(shù)相同，則 稱整數(shù)關(guān)于模同余，記作 如果余數(shù)不同，則稱關(guān)于模不同余，記作.定理1：整數(shù)關(guān)于模同余充分必要條件是 <二>、性質(zhì)定理2：同余關(guān)系是一種等價(jià)關(guān)系，即滿足(1)自反性： (2)對(duì)稱性：若 (3)傳遞性：若 定理3：若 則： 定

8、理4：若 且 則 定理5：若 且 則 定理6：若，則定理7：若 且 則 定理8：若 則定理9 設(shè)整數(shù)n有十進(jìn)制表示式：n = ak 10k + ak-1 10k-1 + + a1 10 + a0 , 0ai <10則 3 | n的充分必要條件是 3 | ak + + a0 ;而9 |n 的充分必要條件是 9 | ak + + a0 .定理10 設(shè)整數(shù)n有1000進(jìn)制表示式： n = ak 1000k + + a1 1000 + a0 , 0ai <1000則7(或 11，或13)|n的充分必要條件是7(或11，或13)能整除整數(shù)( a0 + a2 + ) ( a1 + a3 + )

9、 例1：求7除的余數(shù)解： 除的余數(shù)為4例2：求的個(gè)位數(shù)解： 的個(gè)位數(shù)為二 完全剩余系和互素剩余系<一>、剩余類1定義1：設(shè)是一個(gè)給定的正整數(shù) 則叫做模的剩余類定理1：設(shè)是模的剩余類，則有(1)中每一個(gè)整數(shù)必屬于這個(gè)類中的一個(gè),且僅屬于一個(gè)(2)中任意兩個(gè)整數(shù)屬于同一類的充要條件是 <二>、完全剩余系1定義2：在模的剩余類中各取一個(gè)數(shù) 則個(gè)整數(shù)稱為模的一組完全剩余系任意個(gè)連續(xù)的整數(shù)一定構(gòu)成模的一組完全剩余系2形成完全剩余系的充要條件定理2：個(gè)整數(shù)形成模的完全剩余系的充要條件是： 3完全剩余系的性質(zhì)定理3：若 則當(dāng)遍歷模的完全剩余系時(shí)，則 也遍歷模的完全剩余系定理4 設(shè)m是

10、一個(gè)正整數(shù)，a是滿足(a,m)=1的整數(shù)，則存在整數(shù)a1 a<m,使得aa1(mod m)定理5： 若 當(dāng)分別遍歷模的完全剩余系時(shí),則也遍歷模的完全剩余系例1：?jiǎn)柺欠駱?gòu)成模的完全剩余系？解： 是的一個(gè)排列 能構(gòu)成模的一組完全剩余系<三> 簡(jiǎn)化剩余系1、簡(jiǎn)化剩余類 、簡(jiǎn)化剩余系概念定義3：若模的某一剩余類里的數(shù)與互素，則把它稱為模的一 個(gè)互素剩余類在與?；ニ氐娜渴Ｓ囝愔校魅〕鲆徽?數(shù)組成的系，叫做模的一組簡(jiǎn)化剩余系在完全剩余系中所有與?；ニ氐恼麛?shù)構(gòu)成模的簡(jiǎn)化剩余系2簡(jiǎn)化剩余系的個(gè)數(shù)定義4：歐拉函數(shù)是定義在正整數(shù)集上的函數(shù)，的值等于 序列與互素的個(gè)數(shù)為素?cái)?shù)定理6：個(gè)整數(shù)構(gòu)成模

11、的簡(jiǎn)化剩余系的充要條件是 定理7：若遍歷模的簡(jiǎn)化剩余系，則也遍歷模的簡(jiǎn)化剩余系定理8設(shè) m1 ，m2 是互素的兩個(gè)正整數(shù)，如果x1 , x2 分別遍歷模 m1 和 m2 的簡(jiǎn)化剩余系，則m2x1 + m1x2 遍歷模m1 m2 的簡(jiǎn)化剩余系.定理9：若 ，則 <三>歐拉定理 費(fèi)馬小定理 威爾遜定理1 歐拉定理 設(shè)m是大于1的整數(shù)，如果a是滿足(a , m)=1的整數(shù)，則 2費(fèi)馬定理 設(shè)p是一個(gè)素?cái)?shù)，則對(duì)任意整數(shù)a ,我們有 ap a (mod p)3（wilson）設(shè)p是一個(gè)素?cái)?shù).則 <四>模重復(fù)平方計(jì)算法主要掌握運(yùn)用該方法解題過(guò)程第三章 同余式1同余式的定義定義1 設(shè)

12、m是一個(gè)正整數(shù)，設(shè)f(x)為多項(xiàng)式其中ai 是整數(shù)，則 f(x) 0( mod m ) (1)叫作模m同余式 . 若 0 (mod m), 則n叫做f(x)的次數(shù)，記作degf .此時(shí)，(1)式又叫做模m的n次同余式.2同余式的解、解數(shù)及通解表達(dá)式定理 1 設(shè)m是一個(gè)正整數(shù)，a是滿足a m的整數(shù)則一次同余式 axb (mod m)有解的充分必要條件是(a , m)|b ,而且， 當(dāng)同余式有解時(shí)，其解數(shù)為d =( a , m).定理2設(shè)m是一個(gè)正整數(shù)，a是滿足(a,m)=1的整數(shù)，則一次同余式 ax 1(mod m)有唯一解xa(mod m).定理3 設(shè)m是一個(gè)正整數(shù)，a是滿足(a,m)|b的整

13、數(shù)，則一次同余式 ax b(mod m) 的全部解為3中國(guó)剩余定理定理1 (中國(guó)剩余定理)設(shè)是k個(gè)兩兩互素的正整數(shù)，則對(duì)任意的整數(shù)，同余式組一定有解，且解是唯一的例1 計(jì)算 解一 利用 2.4定理 1(Euler定理 )及模重復(fù)平方計(jì)算法直接計(jì)算. 因?yàn)?77·11，所以由2.4定理1(Euler定理)，又16666·6040，所以，設(shè)m=77,b=2,令a=1.將40寫成二進(jìn)制，4023 25 ，運(yùn)用模重復(fù)平方法，我們依次計(jì)算如下：(1) (2) n1 = 0, 計(jì)算 (3) n2 = 0, 計(jì)算 (4) n3 = 1, 計(jì)算 (5) n4 = 0 , 計(jì)算 (6) n6

14、 = 1 , 計(jì)算 最后，計(jì)算出 解二 令，因?yàn)?7=7·11，所以計(jì)算x(mod 77)等價(jià)于求解同余式組 因?yàn)镋uler定理給出，以及=·6+4，所以.令 ，分別求解同余式 ，得到 故x2·11·2+8·7·110023(mod 77)因此， 23(mod 77)例2：解同余式組 解： 原同余式組有解且同解于 兩兩互素 同余式組有惟一解 原同余式組的解為 第四章 二次同余式與平方剩余1二次同余式的定義定義1 設(shè)m是正整數(shù)，若同余式有解，則a叫做模m的平方剩余(二次剩余)；否則，a叫做模m的平方非剩余(或二次非剩余).2. 模為奇素

15、數(shù)的平方剩余和平方非剩余討論模為素?cái)?shù)p的二次同余式 定理1（歐拉判別條件）設(shè)p是奇素?cái)?shù)，(a, p)=1, 則( i ) a是模p的平方剩余的充分必要條件是 (ii) a是模p的平方非剩余的充分必要條件是并且當(dāng)a是模p的平方剩余時(shí)，同余式(1)恰有二解.定理2 設(shè)p是奇素?cái)?shù)，則模p的簡(jiǎn)化剩余系中平方剩余與平方非剩余的個(gè)數(shù)各為(p-1)/2,且(p-1)/2個(gè)平方剩余與序列：中的一個(gè)數(shù)同余.且僅與一個(gè)數(shù)同余.例1 利用定理判斷3.勒讓德符號(hào)定義1 設(shè)p是素?cái)?shù)，定義勒讓德符號(hào)如下：歐拉判別法則 設(shè)p是奇素?cái)?shù)，則對(duì)任意整數(shù)a,常用定理及結(jié)論設(shè)p是奇素?cái)?shù)，則(1) (2) (3) (4) (5) (6

16、) 設(shè)(a, p) =1, 則 (7) 設(shè)p是奇素?cái)?shù)，如果整數(shù)a, b滿足a b(mod p),則 (8)(9)互倒定律 若p,q是互素奇素?cái)?shù)，則例1 ，而所以第五章 指數(shù)與原根一 指數(shù)1指數(shù)的定義定義1 設(shè)m>1是整數(shù) ，a是與m互素的正整數(shù)，則使得成立的最小正整數(shù)e叫做a對(duì)模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ù)(i) 若ba(mod m),則(ii)設(shè)使得則 .性質(zhì)2 設(shè)m>1是整數(shù)，a是與m互素的整數(shù)，則 的充分必要條件是性質(zhì)3 設(shè)m>1是整數(shù)，a是與m互素的整數(shù)設(shè)d0,為整數(shù)，則二 原根1 原根的定義定義 若(a,m)=1, 如果a對(duì)模m的指數(shù)是，即則a叫做模m的原根2原根的相關(guān)定理及性質(zhì)定理1 設(shè)m>1是整數(shù) ，a是與m互素的整數(shù).則 模m兩兩不同余，特別地，當(dāng)a是模m的原根，即時(shí)，這個(gè)數(shù)組成模m的簡(jiǎn)化剩余系定理2 設(shè)m>1是整數(shù)，g是模m的原根，設(shè)d0為整數(shù)，則是模m的原根當(dāng)且僅當(dāng)3 原根存在的條件定理