信息安全数学基础第一阶段知识总结信息安全数学基础第一阶段知识总结第一章整数得可除性一整除得概念与欧几里得除法1 整除得概念定义1 设a、b就是两个整数，其中b≠0如果存在一个整数q 使得等式a=bｑ成立，就称b整除a或者ａ被ｂ整除，记作b|a ,并把b 叫作a得因数,把a叫作b得倍数、这时，q也就是a得因数,我们常常将ｑ写成a/b或否则,就称b不能整除a或者a不能被b整除,记作a b、2整除得基本性质(1)当b遍历整数a得所有因数时,－b也遍历整数a得所有因数、（2)当ｂ遍历整数a得所有因数时,a/b也遍历整数a得所有因数、（3)设b，c都就是非零整数，(i）若b|a,则|b|｜|ａ|、(ｉｉ)若ｂ｜a,则ｂｃ|aｃ、(iii)若b|a,则1〈|b｜≤|ａ|、3整除得相关定理（1)设a,ｂ≠0,c≠０就是三个整数、若c｜b,b|a,则ｃ|a、(２)设a，b，c≠０就是三个整数,若ｃ|ａ,ｃ|b,则ｃ｜a±b(3）设a，b,c就是三个整数、若c｜a，ｃ|b则对任意整数s，t,有c|ｓa+tb、(４）若整数a１, …,aｎ都就是整数c≠0得倍数，则对任意n个整数s１,…,ｓｎ，整数就是c得倍数（5）设a，b都就是非零整数、若a|b,ｂ|a,则a=±b(6)设a,ｂ，c就是三个整数,且b≠0,c ≠0,如果(a , c）=1,则(ab , ｃ)＝（ｂ，c）(7) 设ａ，b , c就是三个整数,且ｃ≠0，如果c｜ａb，（a , ｃ）＝1, 则c｜b、（8）设ｐ就是素数，若ｐ|ab ,则p |a或p|b（9）设a1，…,a n就是n个整数，p就是素数,若ｐ｜a1…a n，则p一定整除某一个ａk二整数得表示主要掌握二进制、十进制、十六进制等得相互转化、三最大公因数与最小公倍数（一)最大公因数1．最大公因数得概念定义:设就是个整数,若使得,则称为得一个因数。

公因数中最大得一个称为得最大公因数。

记作、若，则称互素。

若,则称两两互素。

?思考:１.由两两互素，能否导出2。

由能否导出两两互素？２。

最大公因数得存在性（1)若不全为零,则最大公因数存在并且(2)若全为零,则任何整数都就是它得公因数。

这时,它们没有最大公因数．3.求两个正整数得最大公因数。

定理1：设任意三个不全为零得整数，且则辗转相除法由带余除法得（1）……因为每进行一次带余除法，余数至少减少1，且就是有限整数,故经过有限次带余除法后,总可以得到一个余数就是零得情况，即由(1)知，定理2：任意两个正整数,则就是(１）中最后一个不等于零得余数. 定理３:任意两个正整数得任意公因数都就是得因数。

4.性质定理4:任意两个正整数,则存在整数，使得成立定理5:设就是不全为零得整数。

（ｉ)若则(ii)若则(ｉii)若就是任意整数，则从上面定理我们很容易得到下面几个常用结论:①② 且?③④5.求两个以上正整数得最大公因数设则有下面得定理:定理6:若就是个正整数,则只需证①就是得一个公因数．②就是得公因数中最大一个例求解:6．求两个正整数得最大公因数得线性组合（重点掌握)方法一运用辗转相除法求最大公因数得逆过程;方法二补充得方法方法三运用列表法求解（二）最小公倍数１.最小公倍数得定义定义：就是个整数，如果对于整数,有,那么叫做得一个公倍数.在得一切公倍数中最小一个正整数，叫做最小公倍?数.记作。

2.最小公倍数得性质。

定理1:设就是任给得两个正整数，则（ｉ)得所有公倍数都就是得倍数.(ii)定理２：设正整数就是得一个公倍数，则3。

求两个以上整数得最小公倍数定理３:设就是个正整数, 若则只需证:①就是得一个公倍数，即,②设就是得任一公倍数，则例1 求解:又?四素数算术基本定理1．素数、合数得概念定义:一个大于1得整数，如果它得正因数只有１与它得本身,我们就称它为素数，否则就称为合数。

2.性质定理1:设就是大于1得整数,则至少有一个素因数，并且当就是合数时，若就是它大于1得最小正因数,则定理2设n就是一个正整数，如果对所有地素数,都有p n，则n一定就是素数、求素数得基本方法：爱拉托斯散筛法。

定理3:设就是素数,就是任意整数，则(i) 或(ii) 若则或3．素数得个数定理4：素数得个数就是无穷得.4。

算术基本定理定理5任一整数ｎ〉1都可以表示成素数得乘积，且在不考虑乘积顺序得情况下，该表达式就是唯一得、即n= ｐ1… pｓ，p1≤… ≤p s , (1)其中p i就是素数,并且若ｎ= q1…qｔ, q1≤… ≤q t，其中q j就是素数,则ｓ= t , p i = ｑj, １≤i ≤ｓ、推论1:设就是任一大于1得整数,且为素数，且则就是得正因数得充分必要条件就是推论２：且为素数.则第二章同余一同余概念与基本性质〈一>、同余得定义.定义: 如果用去除两个整数所得得余数相同,则称整数关于模同余，记作如果余数不同，则称关于模不同余，记作、定理１：整数关于模同余充分必要条件就是〈二〉、性质。

定理2：同余关系就是一种等价关系,即满足(１)自反性:(2）对称性:若(3)传递性：若定理3:若则:定理４:若且则定理５:若且则定理６：若,则定理7:若且则定理8:若则定理9设整数n有十进制表示式：n = ａk１0k+ ａk—1１0k—1 + … + a1１0 + a0，0≤ａi <10则 3 | n得充分必要条件就是3 | a k+ …+ a0 ;而９｜n 得充分必要条件就是9 | a k+ … + a0、定理10设整数n有１000进制表示式:ｎ＝ａk１０００ｋ＋…+ a1 10０0 + ａ0 , 0≤a i〈10０0 则7(或11，或1３）|n得充分必要条件就是７(或11，或1３)能整除整数( a0 ＋a2 + …）–( a1 + a3 + …）例１:求７除得余数.解:除得余数为4。

例2:求得个位数.解:得个位数为。

二完全剩余系与互素剩余系<一>、剩余类.1。

定义１：设就是一个给定得正整数.则叫做模得剩余类。

定理１：设就是模得剩余类，则有（1）中每一个整数必属于这个类中得一个,且仅属于一个.(2）中任意两个整数属于同一类得充要条件就是?<二>、完全剩余系1.定义2：在模得剩余类中各取一个数则个整数称为模得一组完全剩余系。

任意个连续得整数一定构成模得一组完全剩余系.2.形成完全剩余系得充要条件．定理2:个整数形成模得完全剩余系得充要条件就是：3．完全剩余系得性质．定理３：若则当遍历模得完全剩余系时,则?也遍历模得完全剩余系。

定理4 设ｍ就是一个正整数,a就是满足(a,m）=1得整数,则存在整数a’1≤a’〈ｍ，使得aa’≡１(modｍ）定理5：若当分别遍历模得完全剩余系时,则也遍历模得完全剩余系.例1:问就是否构成模得完全剩余系?解：就是得一个排列。

能构成模得一组完全剩余系．〈三〉简化剩余系1、简化剩余类、简化剩余系概念.定义３:若模得某一剩余类里得数与互素,则把它称为模得一?个互素剩余类。

在与模互素得全部剩余类中，各取出一整数组成得系,叫做模得一组简化剩余系。

在完全剩余系中所有与模互素得整数构成模得简化剩余系.2.简化剩余系得个数.定义4:欧拉函数就是定义在正整数集上得函数,得值等于?序列与互素得个数。

为素数定理６:个整数构成模得简化剩余系得充要条件就是定理7：若遍历模得简化剩余系,则也遍历模得简化剩余系定理8设m1 ,m2就是互素得两个正整数,如果x１, ｘ２分别遍历模m1与m2得简化剩余系,则m2x１+m1x2遍历模m1ｍ2得简化剩余系、定理9：若，则∏∏--=-===n p knp a ka ap p n p n n p p pn n s |1|1)11()11()11()(101 ?则有标准因数分解式为设正整数定理〈三＞欧拉定理费马小定理威尔逊定理1．欧拉定理设m 就是大于1得整数，如果a 就是满足(ａ，m)=1得整数，则2.费马定理设p 就是一个素数，则对任意整数a ,我们有ａp ≡ａ(mod p ） 3．(wilso ｎ）设p 就是一个素数、则 <四〉模重复平方计算法主要掌握运用该方法解题过程第三章同余式1.同余式得定义定义1 设m 就是一个正整数,设ｆ(x ）为多项式其中ａi 就是整数,则ｆ（x) ≡0（ mo ｄ m ）（1)叫作模ｍ同余式、若0 （m ｏd m), 则ｎ叫做f （x)得次数,记作de ｇf 、此时，（1）式又叫做模ｍ得ｎ次同余式、 2.同余式得解、解数及通解表达式定理 1 设m 就是一个正整数,ａ就是满足a m 得整数则一次同余式ａｘ≡ｂ (ｍod ｍ）有解得充分必要条件就是（a ，ｍ)|b ，而且，当同余式有解时,其解数为d =（ａ， m)、定理2设ｍ就是一个正整数，a 就是满足(ａ，m)=1得整数，则一次同余式 a ｘ≡ １（mod m)有唯一解ｘ≡a ’(m ｏd m)、定理3 设m 就是一个正整数,a 就是满足（a ，ｍ）|ｂ得整数,则一次同余式ax ≡ b （mod ｍ) 得全部解为.1)m ,a (,,1,0t )m mod ()m ,a (m t ))m ,a (m mod ()m ,a (a )m ,a(b x 1-=+???? ????? ???≡- 3.中国剩余定理定理1 （中国剩余定理)设就是k 个两两互素得正整数，则对任意得整数,同余式组一定有解，且解就是唯一得例1 计算解一利用２、4定理 1（Eul ｅｒ定理）及模重复平方计算法直接计算、因为77=7·11,所以由２、4 定理１（Ｅｕler 定理),,又1000000=166６６·60+40,所以)77 mod (22)2(2404016666601000000≡?=,设ｍ=77，b=2,令a=1、将40写成二进制,40＝2３ + ２5 ,运用模重复平方法,我们依次计算如下: （1）)77(mod 4,1,02100≡≡≡==b b a a n 计算（2) n 1 = 0，计算)77 mod (16b b ,1a a 21201≡≡≡=（3） n 2 = 0，计算 )77 mod (25b b ,1a a 22312≡≡≡= (4）n 3 = 1, 计算)77 mod (9b b ,25b a a 234323≡≡≡?=(5) n 4 ＝ 0 , 计算)77 mod (4b b ,25a a 24534≡≡≡=（6) ｎ６ = 1 ，计算最后，计算出解二令,因为７7=7·11，所以计算x(mo ｄ 77) 等价于求解同余式组因为Eul ｅr 定理给出 ,以及１000000＝16６666·6+4，所以)7 mod (22)2(2b 4166666610000001≡?≡≡、令，分别求解同余式)11 mod (17M ),7 mod (111M '2'1≡≡,得到故x ≡2·11·2+8·7·1≡1００≡２3(m ｏd 77）因此,2 ≡23(ｍo ｄ７7）例2:解同余式组解: 原同余式组有解且同解于两两互素同余式组有惟一解。