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

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|a，则bc|ac.(iii

2、)若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：且 为素数则 第二章 同余一 同余概念和基本性质、同余的定义定义： 如果用去除两个整数所得的余数相同，则 称整数关于模同余，记作 如果余数不同，则称关于模不同余，记作.定理1：整数关于模同余充分必要条件是 、性质定理2：同余关系是一种等价关系，即满足

3、(1)自反性： (2)对称性：若 (3)传递性：若 定理3：若 则： 定理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)能整除整

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

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

6、剩余系的充要条件是 定理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 设m是一个正整数，设f(x)为多项式其中ai

7、 是整数，则 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的整数，则一次同余式 ax b(mod m)

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

9、计算x(mod 77)等价于求解同余式组 因为Euler定理给出，以及=6+4，所以.令 ，分别求解同余式 ，得到 故x2112+87110023(mod 77)因此， 23(mod 77)例2：解同余式组 解： 原同余式组有解且同解于 两两互素 同余式组有惟一解 原同余式组的解为 第四章 二次同余式与平方剩余1二次同余式的定义定义1 设m是正整数，若同余式有解，则a叫做模m的平方剩余(二次剩余)；否则，a叫做模m的平方非剩余(或二次非剩余).2. 模为奇素数的平方剩余和平方非剩余讨论模为素数p的二次同余式 定理1（欧拉判别条件）设p是奇素数，(a, p)=1, 则( i ) a是模p的平方剩

10、余的充分必要条件是 (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是互素奇

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