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

1、精选优质文档-倾情为你奉上信息安全数学基础第一阶段知识总结第一章 整数的可除性一 整除的概念和欧几里得除法1 整除的概念定义1 设a、b是两个整数，其中b0如果存在一个整数 q 使得等式 a=bq 成立，就称b整除a或者a被b整除，记作b|a ，并把b叫作a的因数，把a叫作b的倍数.这时，q也是a的因数，我们常常将q写成ab或否则，就称b不能整除a或者a不能被b整除，记作a b.2整除的基本性质(1)当b遍历整数a的所有因数时，-b也遍历整数a的所有因数.(2)当b遍历整数a的所有因数时，a/b也遍历整数a的所有因数.(3)设b，c都是非零整数， (i)若b|a，则|b|a|. (ii)若b|

2、a，则bc|ac.(iii)若b|a，则1<|b|a|.3整除的相关定理(1) 设a，b0，c0是三个整数.若c|b，b|a，则c|a.(2) 设a，b，c0是三个整数，若c|a，c|b，则c|a±b(3) 设a，b，c是三个整数.若c|a，c|b则对任意整数s，t，有c|sa+tb.(4) 若整数a1 , ,an都是整数c0的倍数，则对任意n个整数s1，sn，整数 是c的倍数(5) 设a，b都是非零整数.若a|b，b|a，则a=±b(6) 设a, b , c是三个整数，且b0，c 0，如果(a , c)=1,则 (ab , c)=(b , c)(7) 设a , b

3、, c是三个整数，且c0，如果cab , (a , c) = 1, 则c | b.(8) 设p 是素数，若p |ab , 则p |a或p|b(9) 设a1 , ,an是n个整数，p是素数，若p| a1 an ,则p一定整除某一个ak 二 整数的表示主要掌握二进制、十进制、十六进制等的相互转化.三 最大公因数和最小公倍数(一)最大公因数1最大公因数的概念定义：设是个整数，若使得 ，则称为的一个因数公因数中最大的一个称为的最大公因数记作.若 ,则称 互素若,则称两两互素思考：1由两两互素，能否导出 2由 能否导出两两互素？2最大公因数的存在性(1)若 不全为零，则最大公因数存在并且 (2)若全为零

4、，则任何整数都是它的公因数这时，它们没有最大公因数3求两个正整数的最大公因数定理1：设任意三个不全为零的整数，且 则辗转相除法 由带余除法 得 (1) 因为每进行一次带余除法，余数至少减少1，且是有限整数，故经过有限次带余除法后，总可以得到一个余数是零的情况，即 由(1)知， 定理2：任意两个正整数,则是(1)中最后一个不等于零的余数定理3：任意两个正整数的任意公因数都是的因数4性质定理4：任意两个正整数，则存在整数，使得成立定理5：设是不全为零的整数(i)若则 (ii)若则 (iii)若是任意整数，则 从上面定理我们很容易得到下面几个常用结论： 且 5求两个以上正整数的最大公因数设 则有下面

5、的定理：定理6：若 是个正整数，则只需证是的一个公因数 是的公因数中最大一个例 求 解： 6求两个正整数的最大公因数的线性组合（重点掌握） 方法一 运用辗转相除法求最大公因数的逆过程；方法二 补充的方法方法三 运用列表法求解(二) 最小公倍数1最小公倍数的定义定义： 是 个整数，如果对于整数，有 ,那么叫做的一个公倍数在 的一切公倍数中最小一个正整数，叫做最小公倍数记作 2最小公倍数的性质定理1：设是任给的两个正整数，则 (i)的所有公倍数都是的倍数 (ii) 定理2：设正整数是的一个公倍数，则3求两个以上整数的最小公倍数定理3：设是个正整数, 若 则 只需证：是 的一个公倍数，即,设是的任一

6、公倍数,则 例1 求 解： 又 四 素数 算术基本定理1素数、合数的概念定义：一个大于1的整数，如果它的正因数只有1和它的本身，我们就称它为素数，否则就称为合数2性质定理1：设是大于1的整数，则至少有一个素因数，并且当是合数时，若是它大于1的最小正因数，则定理2 设n是一个正整数，如果对所有地素数，都有p n,则n一定是素数. 求素数的基本方法：爱拉托斯散筛法。定理3：设是素数，是任意整数，则(i) 或 (ii) 若 则或3素数的个数定理4：素数的个数是无穷的4 算术基本定理定理 5 任一整数n>1都可以表示成素数的乘积，且在不考虑乘积顺序的情况下，该表达式是唯一的.即n= p1 ps

7、, p1 ps , (1)其中pi 是素数，并且若n = q1 qt , q1 qt , 其中qj 是素数，则 s= t , pi = qj, 1 i s. 推论1：设是任一大于1的整数，且 为素数，且 则是的正因数的充分必要条件是 推论2：且 为素数则 第二章 同余一 同余概念和基本性质<一>、同余的定义定义： 如果用去除两个整数所得的余数相同，则 称整数关于模同余，记作 如果余数不同，则称关于模不同余，记作.定理1：整数关于模同余充分必要条件是 <二>、性质定理2：同余关系是一种等价关系，即满足(1)自反性： (2)对称性：若 (3)传递性：若 定理3：若 则： 定

8、理4：若 且 则 定理5：若 且 则 定理6：若，则定理7：若 且 则 定理8：若 则定理9 设整数n有十进制表示式：n = ak 10k + ak-1 10k-1 + + a1 10 + a0 , 0ai <10则 3 | n的充分必要条件是 3 | ak + + a0 ;而9 |n 的充分必要条件是 9 | ak + + a0 .定理10 设整数n有1000进制表示式： n = ak 1000k + + a1 1000 + a0 , 0ai <1000则7(或 11，或13)|n的充分必要条件是7(或11，或13)能整除整数( a0 + a2 + ) ( a1 + a3 + )

9、 例1：求7除的余数解： 除的余数为4例2：求的个位数解： 的个位数为二 完全剩余系和互素剩余系<一>、剩余类1定义1：设是一个给定的正整数 则叫做模的剩余类定理1：设是模的剩余类，则有(1)中每一个整数必属于这个类中的一个,且仅属于一个(2)中任意两个整数属于同一类的充要条件是 <二>、完全剩余系1定义2：在模的剩余类中各取一个数 则个整数称为模的一组完全剩余系任意个连续的整数一定构成模的一组完全剩余系2形成完全剩余系的充要条件定理2：个整数形成模的完全剩余系的充要条件是： 3完全剩余系的性质定理3：若 则当遍历模的完全剩余系时，则 也遍历模的完全剩余系定理4 设m是

10、一个正整数，a是满足(a,m)=1的整数，则存在整数a1 a<m,使得aa1(mod m)定理5： 若 当分别遍历模的完全剩余系时,则也遍历模的完全剩余系例1：问是否构成模的完全剩余系？解： 是的一个排列 能构成模的一组完全剩余系<三> 简化剩余系1、简化剩余类 、简化剩余系概念定义3：若模的某一剩余类里的数与互素，则把它称为模的一 个互素剩余类在与模互素的全部剩余类中，各取出一整 数组成的系，叫做模的一组简化剩余系在完全剩余系中所有与模互素的整数构成模的简化剩余系2简化剩余系的个数定义4：欧拉函数是定义在正整数集上的函数，的值等于 序列与互素的个数为素数定理6：个整数构成模

11、的简化剩余系的充要条件是 定理7：若遍历模的简化剩余系，则也遍历模的简化剩余系定理8设 m1 ，m2 是互素的两个正整数，如果x1 , x2 分别遍历模 m1 和 m2 的简化剩余系，则m2x1 + m1x2 遍历模m1 m2 的简化剩余系.定理9：若 ，则 <三>欧拉定理 费马小定理 威尔逊定理1 欧拉定理 设m是大于1的整数，如果a是满足(a , m)=1的整数，则 2费马定理 设p是一个素数，则对任意整数a ,我们有 ap a (mod p)3（wilson）设p是一个素数.则 <四>模重复平方计算法主要掌握运用该方法解题过程第三章 同余式1同余式的定义定义1 设

12、m是一个正整数，设f(x)为多项式其中ai 是整数，则 f(x) 0( mod m ) (1)叫作模m同余式 . 若 0 (mod m), 则n叫做f(x)的次数，记作degf .此时，(1)式又叫做模m的n次同余式.2同余式的解、解数及通解表达式定理 1 设m是一个正整数，a是满足a m的整数则一次同余式 axb (mod m)有解的充分必要条件是(a , m)|b ,而且， 当同余式有解时，其解数为d =( a , m).定理2设m是一个正整数，a是满足(a,m)=1的整数，则一次同余式 ax 1(mod m)有唯一解xa(mod m).定理3 设m是一个正整数，a是满足(a,m)|b的整

13、数，则一次同余式 ax b(mod m) 的全部解为3中国剩余定理定理1 (中国剩余定理)设是k个两两互素的正整数，则对任意的整数，同余式组一定有解，且解是唯一的例1 计算 解一 利用 2.4定理 1(Euler定理 )及模重复平方计算法直接计算. 因为777·11，所以由2.4定理1(Euler定理)，又16666·6040，所以，设m=77,b=2,令a=1.将40写成二进制，4023 25 ，运用模重复平方法，我们依次计算如下：(1) (2) n1 = 0, 计算 (3) n2 = 0, 计算 (4) n3 = 1, 计算 (5) n4 = 0 , 计算 (6) n6

14、 = 1 , 计算 最后，计算出 解二 令，因为77=7·11，所以计算x(mod 77)等价于求解同余式组 因为Euler定理给出，以及=·6+4，所以.令 ，分别求解同余式 ，得到 故x2·11·2+8·7·110023(mod 77)因此， 23(mod 77)例2：解同余式组 解： 原同余式组有解且同解于 两两互素 同余式组有惟一解 原同余式组的解为 第四章 二次同余式与平方剩余1二次同余式的定义定义1 设m是正整数，若同余式有解，则a叫做模m的平方剩余(二次剩余)；否则，a叫做模m的平方非剩余(或二次非剩余).2. 模为奇素

15、数的平方剩余和平方非剩余讨论模为素数p的二次同余式 定理1（欧拉判别条件）设p是奇素数，(a, p)=1, 则( i ) a是模p的平方剩余的充分必要条件是 (ii) a是模p的平方非剩余的充分必要条件是并且当a是模p的平方剩余时，同余式(1)恰有二解.定理2 设p是奇素数，则模p的简化剩余系中平方剩余与平方非剩余的个数各为(p-1)/2,且(p-1)/2个平方剩余与序列：中的一个数同余.且仅与一个数同余.例1 利用定理判断3.勒让德符号定义1 设p是素数，定义勒让德符号如下：欧拉判别法则 设p是奇素数，则对任意整数a,常用定理及结论设p是奇素数，则(1) (2) (3) (4) (5) (6

16、) 设(a, p) =1, 则 (7) 设p是奇素数，如果整数a, b满足a b(mod p),则 (8)(9)互倒定律 若p,q是互素奇素数，则例1 ，而所以第五章 指数与原根一 指数1指数的定义定义1 设m>1是整数 ，a是与m互素的正整数，则使得成立的最小正整数e叫做a对模m的指数，记作.2指数的性质定理1 设m>1是整数，a是与m互素的整数，则整数d使得的充分必要条件是.定理1之推论 设m>1是整数，a是与m互素的整数,则性质1设m>1是整数，a是与m互素的整数(i) 若ba(mod m),则(ii)设使得则 .性质2 设m>1是整数，a是与m互素的整数，则 的充分必要条件是性质3 设m>1是整数，a是与m互素的整数设d0,为整数，则二 原根1 原根的定义定义 若(a,m)=1, 如果a对模m的指数是，即则a叫做模m的原根2原根的相关定理及性质定理1 设m>1是整数 ，a是与m互素的整数.则 模m两两不同余，特别地，当a是模m的原根，即时，这个数组成模m的简化剩余系定理2 设m>1是整数，g是模m的原根，设d0为整数，则是模m的原根当且仅当3 原根存在的条件定理