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

1、信息安全数学基础第一阶段知识综述第一章整数的可除性整数除法和欧几里得除法的概念1可分性的概念定义1让A和B是两个整数，其中b0如果有一个整数Q使方程a=bq成立，它被称为B可被A整除或A可被B整除，这被称为b|a，B被称为A的因子和B的倍数。这时，Q也是A的因子，我们经常把Q写成A/B或否则，就说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|a、bc|

2、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|ab(3)让A、B和C是三个整数。如果c|a和c|b等于任何整数S和T，则有c|sa tb。(4)如果整数a1，an，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和C是三个整数，c0。如果C | AB，(A，C)

3、=1，那么C | B .(8)设P为素数，如果p |ab，则p |a或P | B(9)让a1，an是n个整数，p是素数。如果p| a1 an，那么p必须除某个ak两个整数的表示掌握二进制、十进制和十六进制的相互转换。3.最大公因数和最小公倍数(一)最大的共同因素1.最大共同因素的概念定义：让它是一个整数。如果它是，它被称为一个因素。最大公因数被称为最大公因数。写为。如果是这样，它被称为互质。如果，它被称为成对素数。思考：1。它能从成对的相互元素中导出吗2.你能导出成对互质吗？2.最大的共同因素的存在(1)如果不是全部为零，则存在最大的公共因子(2)如果所有都为零，那么任何整数都是它的公因数。此

4、时，他们没有最大的共同因素。3.找出两个正整数的最大公因式。定理1:让任何三个不全为零的整数，然后欧几里得算法通过余数除法获得(1)因为余数至少减少1，并且在每次用余数除之后都是有限整数，所以余数为零的情况总是可以在有限次用余数除之后得到，即根据(1)，定理2:任何两个正整数都是(1)中不等于零的最后一个余数。定理3:任意两个正整数的任何公共因子都是一个因子。4.自然定理4:如果有任何两个正整数，就有一个整数，这使它为真定理5:让它是一个不全为零的整数。如果是这样如果是这样(iii)如果它是任意整数，则从上述定理中，我们可以很容易地得到以下共同结论：和5.找出两个以上正整数的最大公因数建立有以

5、下定理：定理6:如果它是正整数，那么只要证明是一个共同的因素。是最大的共同因素寻找榜样解决方案：6.找出两个正整数的最大公因数的线性组合(重点在于掌握)方法一使用通过曲折的划分找到最大公因数的逆过程；由方法2补充的方法第三种方法是列表法(2)最小公倍数1.最小公倍数的定义定义：它是一个整数。如果有整数，它就叫做公倍数。所有公倍数中最小的正整数称为最小公倍数。数一数。记录为。2.最小公倍数的性质。定理1:如果给定两个正整数，那么(I)的所有公倍数都是的倍数。定理2:如果正整数是公倍数，那么3.找出两个或多个整数的最小公倍数定理3:假设是正整数，如果然后只要证明是的公倍数，也就是说，(2)如果它是

6、任何普通倍数，那么示例1搜索解决方案：又算术四个基本定理1.素数和复合数的概念定义：一个大于1的整数，如果它的正因子只有1和它自己，我们就称它为素数，否则就称它为复合数。2.自然定理1:如果它是大于1的整数，它至少有一个质因数，当它是一个复合数时，如果它大于最小正因数1，那么定理2:如果所有质数都有n，那么让n是正整数。P n，那么n必须是质数。求素数的基本方法：艾的分散筛选法。定理3:让它是一个质数和一个任意整数(一)或(二)如果是这样，或3.素数的个数定理4:素数的数量是无限的。4.算术基本定理定理5中的任何整数n1都可以表示为素数的乘积，并且该表达式是唯一的，不考虑乘积的阶数。也就是说，

7、n=p1 ps，p1 ps，(1)其中是素数，如果n=Q1.Q1 Qt. Qt，其中qj是素数，那么s=t，pi=QJ，1 I S .推论1:让它是大于1的任何整数，并且是质数，并且是正因子，当且仅当推论2:还有是质数。然后第二章一致性同余的概念和基本性质1.同余的定义。定义：如果去掉两个整数得到的余数是相同的，那么这个整数就是模同余，如果余数是不同的，那么它就是模同余。定理1:关于模的整数同余的充要条件是二。大自然。定理2:同余关系是一种等价关系，即满足(1)反身性：(2)对称性：如果(3)及物性：如果定理3:如果然后：定理4:如果然后定理5:如果然后定理6:如果，那么定理7:如果然后定理8

8、:如果是这样定理9让整数n有一个十进制表达式：如果n=ak 10k ak-1 10k-1 a1 10 a0，0ai 10，则3 | n为3 | AKA0；9 |n是9 | ak a0的充要条件。定理10让整数n有一个1000位小数的表达式：n=ak 1000k a1 1000 a0，0ai 1000如果7(或11，或13)可被整数整除，那么7(或11，或13)|n是必要且充分的(A0 a2)(a1 a3)例1:求7除的余数。解决方案：除法的余数是4。例2:找出一位数。解决方案：的一位数是。两个完全剩余系统和互质剩余系统1.剩余课程。1.定义1:让它是一个给定的正整数。它被称为剩余模类。定理1:

9、让它成为模块的剩余类，那么(1)中的每个整数必须属于这个类中的一个，并且只属于一个。(2)如果任意两个整数属于同一类，则充要条件是第二，完全剩余制度1.定义2:一组完整的剩余模系，每个模系取一个数和一个整数。任何数量的连续整数必须构成一组完整的剩余模系。2.形成完全剩余系统的充要条件。定理2:一个整数形成一个模的完全剩余系统的充要条件是：3.完全剩余系统的性质。定理3:如果模块的完整剩余系统被遍历，那么它还遍历模块的完整剩余系统。定理4如果M是正整数，A是满足(A，m)=1的整数，那么有一个整数A1 a 简化剩余系统1.简化剩余类和剩余系统的概念。定义3:如果一个模的剩余类中的数和互质，它被称

10、为模之一互质剩余类。从所有与模块互质的剩余类中，取出一个整体由数组成的系统称为一组简化的剩余模系统。在完全剩余系统中，所有模为素数的整数构成一个简化的模剩余系统。2.简化剩余系统的数量。定义4:欧拉函数是定义在一组正整数上的函数，它的值等于序列和互质数。是质数定理6:简化剩余模系统的充要条件是定理7:如果我们遍历模块的简化剩余系统，我们也遍历模块的减少残留物系统定理8假设m1和m2是互质的两个正整数。如果X1和X2分别穿过模块m1和m2的简化残差系统，则m2x1 m1x2穿过模块m1和m2的简化残差系统。定理9:如果，那么三欧拉定理费马小定理威尔逊定理1.欧拉定理假设m是大于1的整数，如果a是

11、满足(a，m)=1的整数，那么2.费马定理假设P是一个素数，那么对于任何整数A，我们有ap a (mod p)3.让P是一个质数。然后四模式重复平方计算方法主要掌握使用这种方法解决问题的过程第三章同余公式1.同余公式的定义定义1让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是满足M的整数，那么它是第一同余Axb (mod m)有解当且仅当它是(a，m)|b，并且当同余式有解时，它的解数是

12、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)的所有解都是3.中国剩余定理定理1(中国剩余定理)是k个成对素数的正整数，所以对于任何整数，同余公式组必须有一个解决方案，这个解决方案是独一无二的示例1计算使用2.4的定理1(欧拉定理)和模重复平方计算方法直接计算解1。因为77=711，所以乘以2.4定理1(欧拉定理)，和1000000=1666660 40，所以，假设m=77，b=2，a=1。将40写成二进制，40=23 2

13、5，并使用模重复平坦法，我们依次计算如下：(1)(2) n1=0，计算(3) n2=0，计算(4) n3=1，计算(5) n4=0，计算(6) n6=1，计算得出最后，计算出求解二阶，因为77=711，所以计算x(模77)等效于求解同余方程，因为欧拉定理给出，1000000=1666666 4，所以。秩序，通过分别求解同余表达式，我们得到因此，x2112 87110023(mod 77)因此，21000000 23(mod 77)例2:解同余组解决方案：原始同余系统有一个解决方案，与成对互素同余系统有一个独特的解决方案。原同余系统的解是第四章是二次同余和平方余数1.二次同余公式的定义定义1如果

14、同余公式如果有解，那么A就叫做模M的平方剩余(二次剩余)；否则，A被称为模M的平方非剩余(或二次非剩余).2.模为奇素数的平方残差和平方非残差本文讨论了模为素数p的二次同余公式定理1(欧拉准则)如果P是一个奇素数并且(a，p)=1，那么(1)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)让(a，p)=1，然后(7)假设P是一个奇素数，如果整数A和B满足那么A b(mod p)(8)(9)倒数定律如果P和Q是互质奇素数，那么示例1，以及因此第五章索引和原始根一个指数1.指数的定义定义1如果m1