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

1）設(shè)a，b≠1）設(shè)a，b≠0,c≠0是三個(gè)整數(shù)。若c|b，b｜a，則c|a。（2）設(shè)a，b,c≠0是三個(gè)整數(shù)，若(p1)2中的一個(gè)數(shù)同余。且僅與一個(gè)數(shù)同余。例1利用定理判斷3.勒讓德符號(hào)定義1設(shè)p是素?cái)?shù)，定義勒讓．性質(zhì)定理4：任意兩個(gè)正整數(shù)，則存在整數(shù)，使得成立定理5：設(shè)是不全為零的整數(shù)．(i）若則（ii)若(且（2)若全為零，則任何整數(shù)都是它的公因數(shù)．這時(shí)，它們沒(méi)有最大公因數(shù)．3．求兩個(gè)正整數(shù)的最大公因數(shù)．信息安全數(shù)學(xué)基礎(chǔ)第一階段知識(shí)總結(jié)ba2整除的基本性質(zhì)3整除的相關(guān)定理，特別地,當(dāng)a，特別地,當(dāng)a是模m的原根，即ord(a)(m)時(shí),這(m)個(gè)數(shù)組成模m的簡(jiǎn)化剩余系m是模m的原根當(dāng)00(260)16666240240(mod77),設(shè)m=77,b=2，令a=1。將40寫成二進(jìn)制,余系中平方剩余與平方非剩余的個(gè)數(shù)各為(p—1）/2，且（p—1)/2個(gè)平方剩余與序列：12,22,,主要掌握二進(jìn)制、十進(jìn)制、十六進(jìn)制等的相互轉(zhuǎn)化.（1）若不全為零,則最大公因數(shù)存在并且一個(gè)互素剩余類．在與模互素的全部剩余類中，各取出一整數(shù)組成的系，叫做模的一組簡(jiǎn)化剩余系．在完全剩余系1k一定有解，且解是唯一的例1一個(gè)互素剩余類．在與?；ニ氐娜渴Ｓ囝愔?，各取出一整數(shù)組成的系，叫做模的一組簡(jiǎn)化剩余系．在完全剩余系1k一定有解，且解是唯一的例1計(jì)算21000000(mod77).解一利用2。4定理1（Euler定，特別地,當(dāng)a是模m的原根，即ord(a)(m)時(shí),這(m)個(gè)數(shù)組成模m的簡(jiǎn)化剩余系m是模m的原根當(dāng),c)=1,則c|b。（8）設(shè)p是素?cái)?shù),若p｜ab，則p｜a或p｜b（9）設(shè)a1,…，an是n個(gè)整數(shù)定理1：設(shè)任意三個(gè)不全為零的整數(shù),且則立則①最大公因數(shù)設(shè)定理6:若只需證①是一個(gè)則有下面的定理：是個(gè)正整數(shù)，則的一個(gè)公因數(shù)．②是的公因數(shù)中最大例dm)最大公因數(shù)設(shè)定理6:若只需證①是一個(gè)則有下面的定理：是個(gè)正整數(shù)，則的一個(gè)公因數(shù)．②是的公因數(shù)中最大例dm)成立的最小正整數(shù)e叫做a對(duì)模m的指數(shù)，記作ord(a)m.2．指數(shù)的性質(zhì)定理1設(shè)m>1是整數(shù)，m是正整數(shù)，若同余式x2a(modm),(a,m)1有解，則a叫做模m的平方剩余（二次剩余）；否則,式x2a(modp),(a,p)1定理1(歐拉判別條件)設(shè)p是奇素?cái)?shù)，（a，p）=1，則(i）a是模③④設(shè)是,:若定理3：若則:定理4:若定理:若定理3：若則:定理4:若定理5：若定理6：若,則且且則則定理7：若定理8：若定理9設(shè)整數(shù)n有十進(jìn)少減少1，且是有限整數(shù),故經(jīng)過(guò)有限次帶余除法后,總可以得到一個(gè)余數(shù)是零的情況，即由（1)知，定理2:(7)設(shè)p是奇素?cái)?shù)，如果整數(shù)a，1b滿足a≡b（modp)，則abpp（8)(1)p1（9）互倒定律任一整數(shù)n>1都可以表示成素?cái)?shù)的乘積,且在不考慮乘積順序的情況下,該表達(dá)式是唯一的。即n=p1…psn則又2．形成完全剩余系的充要條件．定理2:個(gè)整數(shù)形成模的完全剩余系的充要條件是：2．形成完全剩余系的充要條件．定理2:個(gè)整數(shù)形成模的完全剩余系的充要條件是：3．完全剩余系的性質(zhì)．定式x2a(modp),(a,p)1定理1(歐拉判別條件)設(shè)p是奇素?cái)?shù)，（a，p）=1，則(i）a是模能否導(dǎo)出2．由能否導(dǎo)出兩兩互素？2．最大公因數(shù)的存在性（1）若不全為零,則最大公因數(shù)，則的最大存在并3．（wilson）設(shè)p是一個(gè)素?cái)?shù).則(p1)!1(modp)〈四>模重復(fù)平方計(jì)算法主要掌握運(yùn)用該方則且〈一〉、同余的定義．<二>、性質(zhì)．在模的剩余類則個(gè)整數(shù)中各取一個(gè)數(shù)稱為模的一組完全剩余系．任意個(gè)連續(xù)的整數(shù)一定構(gòu)成模的一組完全剩余系．000k+…+a1000+a,0≤a〈1000（在模的剩余類則個(gè)整數(shù)中各取一個(gè)數(shù)稱為模的一組完全剩余系．任意個(gè)連續(xù)的整數(shù)一定構(gòu)成模的一組完全剩余系．000k+…+a1000+a,0≤a〈1000（a0+a2+…）(a1+a3+…）例1：求7除的余數(shù)m是正整數(shù)，若同余式x2a(modm),(a,m)1有解，則a叫做模m的平方剩余（二次剩余）；否則,且僅當(dāng)(d,(m))13．原根存在的條件定理1設(shè)p是奇素?cái)?shù)，則模p的原根存在.定理2設(shè)g是模p的一個(gè)且kk—11且且則則定理10設(shè)整數(shù)n有1000進(jìn)制表示式:k則則1(modp);并且當(dāng)a是模1(modp);并且當(dāng)a是模p的平方剩余時(shí),同余式（1）恰有二解。定理2設(shè)p是奇素?cái)?shù),則模p的簡(jiǎn)化剩個(gè)類中的一個(gè)，且僅屬于一個(gè)．（2）中任意兩個(gè)整數(shù)屬于同一類的充要條件是〈二〉、完全剩余系1．定義2：理）及模重復(fù)平方計(jì)算法直接計(jì)算。因?yàn)?7＝7·11，(77)(7)(11)60,所以由2.4定理1（<一〉、剩余類．則a’〈三>簡(jiǎn)化剩余系40＝23＋25,運(yùn)用模重復(fù)平方法，我們依次計(jì)算如下：(1）n0,計(jì)算a00（2)n1=0，計(jì)算a1｜a｜.（ii)若b|a，則40＝23＋25,運(yùn)用模重復(fù)平方法，我們依次計(jì)算如下：(1）n0,計(jì)算a00（2)n1=0，計(jì)算a1｜a｜.（ii)若b|a，則bc|ac。(iii）若b｜a，則1〈|b｜≤｜a|。3整除的相關(guān)定理（理及性質(zhì)定理1設(shè)m>1是整數(shù)，a是與m互素的整數(shù)。則1a0,a1,,aordm(a)1模m兩兩不同余a，b都是非零整數(shù).若a｜b，b｜a，則a=±b（6)設(shè)a,b，c是三個(gè)整數(shù)，且b≠0，c≠0,如果則aa1s11ppp定理8設(shè)m1，m2是互素的兩個(gè)正整數(shù)，如果x1,x2分別遍歷模m1和m2的簡(jiǎn)化剩余系，則m2x1+m1x2遍歷模m1m2的簡(jiǎn)化剩余系。k〈四>模重復(fù)平方計(jì)算法少減少1，且是有限整數(shù),故經(jīng)過(guò)有限次帶余除法后,總可以得到一個(gè)余數(shù)是零的情況，即由（少減少1，且是有限整數(shù),故經(jīng)過(guò)有限次帶余除法后,總可以得到一個(gè)余數(shù)是零的情況，即由（1)知，定理2:sa+tb。（4）若整數(shù)a1，…,an…,s，整數(shù)都是整數(shù)c≠0的倍數(shù)，則對(duì)任意n個(gè)整數(shù)nn（5)設(shè)數(shù)只有1和它的本身，我們就稱它為素?cái)?shù)，否則就稱為合數(shù)．2．性質(zhì)定理1：設(shè)是大于1的整數(shù),則至少有一個(gè)amm性質(zhì)3設(shè)m〉1是整數(shù),a是與m互素的整數(shù)設(shè)d≥0，為整數(shù)，則ord(a)ord(a)m二原根1ba1m第三章同余式）（，（n式又叫做模m的n次同余式.≡b（modm）的全部解為數(shù)只有1和它的本身，我們就稱它為素?cái)?shù)，否則就稱為合數(shù)．2．性質(zhì)定理1：設(shè)是大于1的整數(shù),數(shù)只有1和它的本身，我們就稱它為素?cái)?shù)，否則就稱為合數(shù)．2．性質(zhì)定理1：設(shè)是大于1的整數(shù),則至少有一個(gè)義1:設(shè)是一個(gè)給定的正整數(shù)．則定理1:設(shè)叫做模的剩余類．是模的剩余類，則有（1）中每一個(gè)整數(shù)必屬于這m2的簡(jiǎn)化剩余系，則m2x1+m1x2遍歷模m1m2的簡(jiǎn)化剩余系。，則n有標(biāo)準(zhǔn)因數(shù)分解式為npap|m是正整數(shù)，若同余式x2a(modm),(a,m)1有解，則a叫做模m的平方剩余（二次剩余）；否則,13531x1m)1xkm)k24解二令x21000000x1122abb2b 2421的整數(shù)，則一次同余式ax≡1(modm1的整數(shù)，則一次同余式ax≡1(modm）有唯一解x≡a’(modm）.定理3設(shè)m是一個(gè)正整數(shù),a是00(260)16666240240(mod77),設(shè)m=77,b=2，令a=1。將40寫成二進(jìn)制,c|a,c|b，則c｜a±b（3）設(shè)a,b，c是三個(gè)整數(shù)。若c|a，c｜b則對(duì)任意整數(shù)s，t，有c|求解：6．求兩個(gè)正整數(shù)的最大公因數(shù)的線性組合（重點(diǎn)掌握)方法一運(yùn)用輾轉(zhuǎn)相除法求最大公因數(shù)的逆過(guò)程；方令m7,m11,mmm77,Mm11,Mm7因?yàn)?7=7·11，所以計(jì)算因?yàn)?7=7·11，所以計(jì)算x（mod77）因?yàn)镋uler定理給出b(mod11)22(7)261(化剩余系，則也遍歷模的簡(jiǎn)化剩余系定理8設(shè)m1，m2是互素的兩個(gè)正整數(shù)，如果x1,x2分別遍歷模m1和理）及模重復(fù)平方計(jì)算法直接計(jì)算。因?yàn)?7＝7·11，(77)(7)(11)60,所以由2.4定理1（余系中平方剩余與平方非剩余的個(gè)數(shù)各為(p—1）/2，且（p—1)/2個(gè)平方剩余與序列：12,22,,2第四章二次同余式與平方剩余，（2m是正整數(shù)，若同余式x2a(modm),(a,m)1有解，則a叫做模m的平方剩余（二次剩余）；否則,sa+tb。（4）若整數(shù)a1，…,an…,s，整數(shù)都是整數(shù)m是正整數(shù)，若同余式x2a(modm),(a,m)1有解，則a叫做模m的平方剩余（二次剩余）；否則,sa+tb。（4）若整數(shù)a1，…,an…,s，整數(shù)都是整數(shù)c≠0的倍數(shù)，則對(duì)任意n個(gè)整數(shù)nn（5)設(shè)mod7),7M'1(mod11)，得到12M'2,M'8故x≡2·11·2+8·7·1≡100≡2數(shù)，則3．求兩個(gè)以上整數(shù)的最小公倍數(shù)定理3：設(shè)只需證：①是②設(shè)是例1求是個(gè)正整數(shù)，若則的一個(gè)公倍數(shù)，ap,pp（2）11pp2ap任一整數(shù)n>1都可以表示成素?cái)?shù)的乘積,且在不考慮乘積順序的情況下,該表達(dá)式是唯一的。即n=p1…ps00(260)16666240240(mod77),設(shè)m=77,b=2，令a=1。將40寫成二進(jìn)制,1k一定有解，且解是唯一的例1計(jì)算21000000(mod77).解一利用2。4定理1（Euler定1的整數(shù)，則一次同余式ax≡1(modm）有唯一解x≡a’(modm）.定理3設(shè)m是一個(gè)正整數(shù),a是p228任一整數(shù)n>1都可以表示成素?cái)?shù)的乘積,且在不考慮乘積順序的情況下,該表達(dá)式是唯一的。即n=p1…ps00(260)16666240240(mod77),設(shè)m=77,b=2，令a=1。將40寫成二進(jìn)制,1k一定有解，且解是唯一的例1計(jì)算21000000(mod77).解一利用2。4定理1（Euler定1的整數(shù)，則一次同余式ax≡1(modm）有唯一解x≡a’(modm）.定理3設(shè)m是一個(gè)正整數(shù),a是p22853218235qppqa2p1（9）互倒定律若p，q是互素奇素?cái)?shù)，則235所以(((135則a叫做模m的原根,c)=1,則c|b。（8）設(shè)p是素?cái)?shù),若,c)=1,則c|b。（8）設(shè)p是素?cái)?shù),若p｜ab，則p｜a或p｜b（9）設(shè)a1,…，an是n個(gè)整數(shù)m〉1是整數(shù)，a是與m互素的整數(shù)，則ord(a)|(m)m性質(zhì)