信息安全数学基础第一阶段知识总结中学教育中考_中学教育-中考.pdf

《信息安全数学基础第一阶段知识总结中学教育中考_中学教育-中考.pdf》由会员分享，可在线阅读，更多相关《信息安全数学基础第一阶段知识总结中学教育中考_中学教育-中考.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 的所有

2、因数.(3)设 b，c 都是非零整数，(i)若 b|a，则|b|a|.(ii)若 b|a，则 bc|ac.(iii)若 b|a，则 11 都可以表示成素数的乘积，且在不考虑乘积顺序的情况下，该表达式是唯一的.即 n=p1 ps,p1 ps,(1)其中 pi 是素数，并且若 n=q1 qt,q1 qt,其中 qj 是素数，则 s=t,pi=qj,1 i s.推论 1：设 是任一大于 1 的整数，且 为素数，且 则 是 的正因数的充分必要条件是 推论 2：且 为素数 则 第二章 同余 一 同余概念和基本性质 、同余的定义 定义：如果用去除两个整数所得的余数相同，则 称整数其中如果存在一个整数使得等

3、式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公因数存在并且若全为零则任何整数关于模同余，记作 如

4、果余数不同，则称关于模不同余，记作.定理 1：整数关于模同余充分必要条件是 、性质 定理 2：同余关系是一种等价关系，即满足 (1)自反性：(2)对称性：若 (3)传递性：若 定理 3：若 则：定理 4：若 且 则 定理 5：若 且 则 定理 6：若，则 定理 7：若 且 则 定理 8：若 则 定理 9 设整数 n 有十进制表示式：n=ak 10k+ak-1 10k-1+a1 10+a0,0 ai 10 则 3|n的充分必要条件是 3|ak+a0;而 9|n 的充分必要条件是 9|ak+a0.定理 10 设整数 n 有 1000 进制表示式：n=ak 1000k+a1 1000+a0,0 ai

5、 1000 则 7(或 11，或 13)|n 的充分必要条件是 7(或 11，或 13)能整除整数(a0+a2+)(a1+a3+)例 1：求 7 除的余数 整数其中如果存在一个整数使得等式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念定义设是个整数若使得称为的一个因数公因

6、数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公因数存在并且若全为零则任何 解：除的余数为 4 例 2：求的个位数 解：的个位数为 二 完全剩余系和互素剩余系 、剩余类 1定义 1：设是一个给定的正整数 则叫做模的剩余类 定理 1：设是模的剩余类，则有(1)中每一个整数必属于这个类中的一个,且仅属于一个 (2)中任意两个整数属于同一类的充要条件是 、完全剩余系 1定义 2：在模的剩余类中各取一个数 则个整数称为模的一组完全剩余系 任意个连续的整数一定构成模的一组完全剩余系 2形成完全剩余系的充要条件 定理

7、2：个整数形成模的完全剩余系的充要条件是：整数其中如果存在一个整数使得等式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两

8、互素若不全为零则最大公因数存在并且若全为零则任何 3完全剩余系的性质 定理 3：若 则当 遍历模的完全剩余系时，则 也遍历模的完全剩余系 定理 4 设 m 是一个正整数，a 是满足(a,m)=1 的整数，则存在整数 a 1 a m,使得 aa 1(mod m)定理 5：若 当分别遍历模的完全剩余系时,则也遍历模的完全剩余系 例 1：问是否构成模的完全剩余系？解：是的一个排列 能构成模的一组完全剩余系 简化剩余系 1、简化剩余类、简化剩余系概念 定义 3：若模的某一剩余类里的数与互素，则把它称为模的一 个互素剩余类在与模互素的全部剩余类中，各取出一整 数组成的系，叫做模的一组简化剩余系 在完全剩

9、余系中所有与模互素的整数构成模的简化剩余系 2简化剩余系的个数 定义 4：欧拉函数是定义在正整数集上的函数，的值等于 序列与 互素的个数 为素数 定理 6：个整数构成模的简化剩余系的充要条件是 整数其中如果存在一个整数使得等式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念

10、定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公因数存在并且若全为零则任何 定理 7：若遍历模的简化剩余系，则也遍历模的 简化剩余系 定理8设 m1，m2 是互素的两个正整数，如果x1,x2 分别遍历模 m1 和 m2 的简化剩余系，则 m2x1+m1x2 遍历模 m1 m2 的简化剩余系.定理 9：若，则 npknpakaappnpnnpppnns|1|1)11()11()11()(101则有标准因数分解式为设正整数定理 欧拉定理 费马小定理 威尔逊定理 1 欧拉定理

11、 设 m 是大于 1 的整数，如果 a 是满足(a,m)=1 的整数，则 )m mo d(1a)m(2费马定理 设 p 是一个素数，则对任意整数 a,我们有 ap a(mod p)3（wilson）设 p 是一个素数.则)p mod(1)!1p(模重复平方计算法 主要掌握运用该方法解题过程 第三章 同余式 1同余式的定义 定义 1 设 m 是一个正整数，设 f(x)为多项式 其中 ai 是整数，则 f(x)0(mod m)(1)叫作模 m 同余式.若 01nnaxaxa)x(f整数其中如果存在一个整数使得等式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则

12、就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公因数存在并且若全为零则任何na 0(mod m),则 n 叫做 f(x)的次数，记作 degf.此时，(1)式又叫做模 m 的 n 次同余

13、式.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 的整数，则一次同余式 ax b(mod m)的全部解为.1)m,a(,1,0t)m mod()m,a(mt)m,a(m mod()m,a(a)m,a(bx1 3中国剩余定理 定理 1(中国剩余定理)

14、设k1m,m 是 k 个两两互素的正整数，则对任意的整数k1b,b，同余式组)1()m mod(bx)m mod(bxkk11 一定有解，且解是唯一的 例 1 计算).77 mod(21000000 解一 利用 2.4 定理 1(Euler 定理)及模重复平方计算法直接计算.因为 77711，,60)11()7()77(所以由2.4 整数其中如果存在一个整数使得等式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的

15、倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公因数存在并且若全为零则任何定理 1(Euler 定理)，)77 mod(1260，又 1000000166666040，所以)77 mod(22)2(2404016666601000000，设 m=77,b=2,令 a=1.将 40 写成二进制，4023 25，运用模重复平方法，我们

16、依次计算如下：(1)77(mod4,1,02100bbaan计算(2)n1=0,计算)77 mod(16bb,1aa21201(3)n2=0,计算)77 mod(25bb,1aa22312(4)n3=1,计算)77 mod(9bb,25baa234323(5)n4=0,计算)77 mod(4bb,25aa24534(6)n6=1,计算)77 23(modbaa545 最后，计算出)77 mod(2321000000 解二 令10000002x，因为 77=711，所以计算 x(mod 77)等价于求解同余式组)11 mod(bx)77 mod(bx21 因为 Euler 定理给出)7 mod(

17、1226)7(，以及 1000000=1666666+4，所以)7 mod(22)2(2b4166666610000001.令 77mmm,11m,7m2121，7mM,11mM1221 分别求解同余式)11 mod(17M),7 mod(111M21，得到 8M,2M21 故 x2112+87110023(mod 77)因此，21000000 23(mod 77)例 2：解同余式组 整数其中如果存在一个整数使得等式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个

18、整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公因数存在并且若全为零则任何 解：原同余式组有解且同解于 两两互素 同余式组有惟一解 原同余式组的解为 第四章 二次同余式与平方剩余 1二次同余式的定义 定义 1 设 m 是正整数，若同余式1)m,a(),m mod(ax2 有解，则

19、 a 叫做模 m 的平方剩余(二次剩余)；否则，a 叫做模 m 的平方非剩余(或二次非剩余).整数其中如果存在一个整数使得等式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两

20、互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公因数存在并且若全为零则任何 2.模为奇素数的平方剩余和平方非剩余 讨论模为素数 p 的二次同余式1),(),(mod2papax 定理 1（欧拉判别条件）设 p 是奇素数，(a,p)=1,则(i)a 是模 p 的平方剩余的充分必要条件是);(mod121pap (ii)a 是模 p 的平方非剩余的充分必要条件是);(mod121pap并且当a 是模 p 的平方剩余时，同 余式(1)恰有二解.定理 2 设 p 是奇素数，则模 p 的简化剩余系中平方剩余与平方非剩余的个数各为(p-1)/2,且(p-1)/2个平方剩余与序列：

21、222)21(,2,1p中的一个数同余.且仅与一个数同余.例 1 利用定理判断 3.勒让德符号 定义 1 设 p 是素数，定义勒让德符号如下：appapa|01,1)pa(若，的平方非剩余是模，若的平方剩余是模若 整数其中如果存在一个整数使得等式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则

22、一定整除某一个二整念定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公因数存在并且若全为零则任何欧拉判别法则 设 p 是奇素数，则对任意整数 a,)p mod(apa21p 常用定理及结论 设 p 是奇素数，则(1)1p1 (2)21p)1(p1 (3)4)3(modp ,1-)4 mod(1p,1p1若若 (4);pappa (5);pbpapab(6)设(a,p)=1,则 1pa2(7)设 p 是奇素数，如果整数 a,b 满足 a b(mod p),则 pbpa(8)

23、812p)1(p2 整数其中如果存在一个整数使得等式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公

24、因数存在并且若全为零则任何(9)互倒定律 若 p,q 是互素奇素数，则qp)1(pq21q21p 例 15355335325330，而 153553553)1(535132353353)1(5331)1(5322153215215321381532 所以15355335325330 第五章 指数与原根 一 指数 1指数的定义 定义 1 设 m1 是整数，a 是与 m 互素的正整数，则使得)(mod1mae成立的最小正整数 e 叫做 a 对模 m 的指数，记作)(aordm.2指数的性质 定理 1 设 m1 是整数，a 是与 m 互素的整数，则整数 d 使得整数其中如果存在一个整数使得等式成立就

25、称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公因数存在并且若全为零则任何)(mod1mad的充分必要条件

26、是daordm|)(.定理 1 之推论 设 m1 是整数，a 是与 m 互素的整数,则)(|)(maordm 性质 1 设 m1 是整数，a 是与 m 互素的整数(i)若 ba(mod m),则)b(ord)a(ordmm(ii)设1a使得)m mod(1aa1则)a(ord)a(ordm1m.性质 2 设 m1 是整数，a 是与 m 互素的整数，则)(mod maakd 的充分必要条件是)(modaordkdm 性质 3 设 m1 是整数，a 是与 m 互素的整数设 d0,为整数，则),()()(daordaordaordmmdm 二 原根 1 原根的定义 定义 若(a,m)=1,如果a对模

27、m的指数是)(m，即)()(ao r dmm则 a 叫做模 m 的原根 2原根的相关定理及性质 定理 1 设 m1 是整数，a 是与 m 互素的整数.则 1)(10,1aordmaaa模 m 两两不同余，特别地，当 a 是模 m 的原根，即)()(maordm时，这)(m个数组成模 m 的简化剩余系 定理 2 设 m1 是整数，g 是模 m 的原根，设 d0 为整数，则dg 是模 m 的原根当且仅当1)m(,d(3 原根存在的条件 定理 1 设 p 是奇素数，则模 p 的原根存在.整数其中如果存在一个整数使得等式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或

28、否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公因数存在并且若全为零则任何定理 2 设 g 是模 p 的一个原根，则 g 或者 p+g 是模 p2 的原根.定理 3 设 p 是一个奇

29、素数，则对任意正整数 a,模 pa 的原根存在.更确切地说，如果 g 是模 p2的一个原根，则对任意正整数 a，g 是模 pa 的原根.定理 4 设 a 1,g 是模 pa 的一个原根，则 g 与 g+pa 中的奇数是模2pa的一个原根 定理 5 模 m 的原根存在的充分必要条件是aa2p,p,4,2m,其中 p是奇素数.定理 6 设 m1,的所有不同素因数是 q1,qk,则 g 是模 m 的一个原根的充分必要条件是iq/)m(g 1(mod m),i=1,k )m(整数其中如果存在一个整数使得等式成立就称整除或者被整除记作并把叫作的因数把叫作的倍数这时也是的因数我们常常将写成或否则就称不能整除或者不能被整除记作整除的基本性质当遍历整数的所有因数时也遍历整数的所有因则设是三个整数若则设是三个整数若则对任意整数有若整数都是整数的倍数则对任意个整数整数是的倍数设都是非零整数若则设是三个整数且如果则设是三个整数且如果则设是素数若则或设是个整数是素数若则一定整除某一个二整念定义设是个整数若使得称为的一个因数公因数中最大的一个称为大公因数记作若互素则称则的最若则称思考由两两互素能否导出由能否导出最大公因数的存在性两两互素两两互素若不全为零则最大公因数存在并且若全为零则任何