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

信息安全数学基础第一阶段知识总结第一章整数得可除性一 整除得概念与欧几里得除法1 整除得概念定义1 设a、b就是两个整数，其中b0如果存在一个整数 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就是三个整数、若cb,b|a,则|a、()设a，b，c就是三个整数,若|,|b,则ab(3） 设a，b,c就是三个整数、若ca，|b则对任意整数s，t,有c|a+tb、(） 若整数a , ,a都就是整数c0得倍数，则对任意n个整数s,，整数 就是c得倍数（5） 设a，b都就是非零整数、若a|b,|a,则a=b(6)设a, ，c就是三个整数,且b0,c 0,如果(a , c）=1,则(ab , )（ ，c）(7) 设 ， b , c就是三个整数,且0，如果cb，（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就是一个正整数，如果对所有地素数,都有p n，则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+ k1 0k1 + + a1 0 +a0 ， 0i 10则 3 |n得充分必要条件就是 3| ak + + a0 ;而n得充分必要条件就是 9 | ak + + a0 、定理10设整数n有000进制表示式: k + a1 100 + 0 ,0ai 100则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得整数,则存在整数a1 a，使得aa(mod ）定理5：若当分别遍历模得完全剩余系时,则也遍历模得完全剩余系.例1:问就是否构成模得完全剩余系?解： 就是得一个排列。 能构成模得一组完全剩余系三 简化剩余系1、简化剩余类 、简化剩余系概念.定义:若模得某一剩余类里得数与互素,则把它称为模得一 个互素剩余类。在与模互素得全部剩余类中，各取出一整 数组成得系,叫做模得一组简化剩余系。在完全剩余系中所有与模互素得整数构成模得简化剩余系.2.简化剩余系得个数.定义4:欧拉函数就是定义在正整数集上得函数,得值等于 序列与互素得个数。为素数定理:个整数构成模得简化剩余系得充要条件就是 定理7：若遍历模得简化剩余系,则也遍历模得 简化剩余系定理8设 m1 ,m2 就是互素得两个正整数,如果x , 分别遍历模 m1 与m2得简化剩余系,则m2x +m1x2遍历模m1 2 得简化剩余系、定理9：若，则 三欧拉定理 费马小定理 威尔逊定理1 欧拉定理设m就是大于1得整数，如果a就是满足(， m)=1得整数，则 2.费马定理 设p就是一个素数，则对任意整数a ,我们有 p (mod p）3(wilso）设p就是一个素数、则 1就是整数,a就是与m互素得整数，则整数d使得得充分必要条件就是、定理1之推论 设m1就是整数，就是与互素得整数，则性质1设m1就是整数,a就是与m互素得整数(i) 若b(md m)，则(i)设使得则 、性质2 设m1就是整数，a就是与m互素得整数,则 得充分必要条件就是性质3 设m1就是整数，a就是与m互素得整数设0，为整数,则二原根1 原根得定义定义若（a,m)=1, 如果a对模m得指数就是,即则叫做模得原根2.原根得相关定理及性质定理1设m就是整数 ,a就是与互素得整数、则 模m两两不同余,特别地，当a就是模m得原根，即时,这个数组成模m得简化剩余系定理2 设m1就是整数,就是模m得原根，设d0为整数，则就是模m得原根当且仅当3 原根存在得条件定理1 设就是奇素数,则模p得原根存在、定理2 设g就是模p得一个原根,则g或者p就是模p2 得原根、定理3设p就是一个奇素数，则对任意正整数，模a 得原根存在、更确切地说,如果g就是模 2得一个原根,则对任意正整数a，g就是模a 得原根、定理设a，就是模pa 得一个原根,则g与 pa 中得奇数就是模2pa得一个原根定理5模m得原根存在得充分必要条件就是，其中p就是奇素数、定理6设m1, 得所有不同素因数就是q1，q ,则g就是模得一个原根得充分必要条件就是 1(od m)，i=1,，k