信息安全数学基础第一阶段知识总结

信息安全数学基础第一阶段知识总结第一章整数得可除性一整除得概念与欧几里得除法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整除,记作ab、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，…,an就是n个整数，p就是素数,若ｐ｜a1…an，则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就是一个正整数，如果对所有地素数,都有pn，则n一定就是素数、求素数得基本方法：爱拉托斯散筛法。定理3:设就是素数,就是任意整数，则(i)或(ii)若则或3．素数得个数ﻫ定理4：素数得个数就是无穷得.4。算术基本定理定理5任一整数ｎ〉1都可以表示成素数得乘积，且在不考虑乘积顺序得情况下，该表达式就是唯一得、即n=ｐ1…pｓ，p1≤…≤ps,(1)其中pi就是素数,并且若ｎ=q1…qｔ,q1≤…≤qt，其中qj就是素数,则ｓ=t,pi=ｑ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|ak+…+a0;而９｜n得充分必要条件就是9|ak+…+a0、定理10设整数n有１000进制表示式:ｎ＝ａk１０００ｋ＋…+a110０0+ａ0,0≤ai〈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：若，则〈三＞欧拉定理费马小定理威尔逊定理欧拉定理设m就是大于1得整数，如果a就是满足(ａ，m)=1得整数，则2.费马定理设p就是一个素数，则对任意整数a,我们有ａp≡ａ(modp）3．(wilsoｎ）设p就是一个素数、则<四〉模重复平方计算法主要掌握运用该方法解题过程第三章同余式1.同余式得定义定义1设m就是一个正整数,设ｆ(x）为多项式其中ａi就是整数,则ｆ（x)≡0（moｄm）（1)叫作模ｍ同余式、若0（mｏdm),则ｎ叫做f（x)得次数,记作deｇf、此时，（1）式又叫做模ｍ得ｎ次同余式、2.同余式得解、解数及通解表达式定理1设m就是一个正整数,ａ就是满足am得整数则一次同余式ａｘ≡ｂ(ｍodｍ）有解得充分必要条件就是（a，ｍ)|b，而且，当同余式有解时,其解数为d=（ａ，m)、定理2设ｍ就是一个正整数，a就是满足(ａ，m)=1得整数，则一次同余式aｘ≡１（modm)有唯一解ｘ≡a’(mｏdm)、定理3设m就是一个正整数,a就是满足（a，ｍ）|ｂ得整数,则一次同余式ax≡b（modｍ)得全部解为3.中国剩余定理定理1（中国剩余定理)设就是k个两两互素得正整数，则对任意得整数,同余式组一定有解，且解就是唯一得例1计算解一利用２、4定理1（Eulｅｒ定理）及模重复平方计算法直接计算、因为77=7·11,所以由２、4定理１（Ｅｕler定理),,又1000000=166６６·60+40,所以,设ｍ=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。二次同余式得定义定义１设m就是正整数,若同余式有解，则ａ叫做模ｍ得平方剩余（二次剩余）;否则，a叫做模m得平方非剩余（或二次非剩余)、模为奇素数得平方剩余与平方非剩余讨论模为素数ｐ得二次同余式定理１（欧拉判别条件)设p就是奇素数，（ａ,p)=1,则(ｉ）a就是模p得平方剩余得充分必要条件就是(ｉｉ）a就是模p得平方非剩余得充分必要条件就是并且当ａ就是模p得平方剩余时,同余式（１)恰有二解、定理２设ｐ就是奇素数,则模ｐ得简化剩余系中平方剩余与平方非剩余得个数各为（p—１)／2,且(p—1)/2个平方剩余与序列：中得一个数同余、且仅与一个数同余、例1利用定理判断3、勒让德符号定义1设p就是素数,定义勒让德符号如下:欧拉判别法则设ｐ就是奇素数，则对任意整数a,常用定理及结论设ｐ就是奇素数,则(1)(2)（3）（4)（５)(６)设（a，ｐ)=1，则(7）设p就是奇素数，如果整数ａ，ｂ满足a≡b(modp)，则(8）(９）互倒定律若p,ｑ就是互素奇素数,则例1,而所以第五章指数与原根一指数1．指数得定义定义1设m〉1就是整数，a就是与m互素得正整数,则使得成立得最小正整数e叫做a对模ｍ得指数,记作、2.指数得性质定理1设m>1就是整数,a就是与m互素得整数，则整数d使得得充分必要条件就是、定理1之推论设m〉1就是整数，ａ就是与ｍ互素得整数，则性质1设m>1就是整数,a就是与m互素得整数若b≡ａ(mｏdm)，则(ｉi)设使得则、性质2设m＞1就是整数，a就是与m互素得整数,则得充分必要条件就是性质3设m〉1就是整数，a就是与m互素得整数设ｄ≥0，为整数,则二原根原根得定义定义若（a,m)=1,如果a对模m得指数就是,即则ａ叫做模ｍ得原根2.原根得相关定理及性质定理1设m〉１就是整数,a就是与ｍ互素得整数、则模m两两不同余,特别地，当a就是模m得原根，即时,这个数组成模m得简化剩余系定理2设m＞1就是整数,ｇ就是模m得原根，设d≥0为整数，则就是模m得原根当