1、信息安全数学基础第一阶段知识总结 第一章 整数的可除性 一 整除的概念和欧几里得除法 1 整除的概念 定义 1 设 a、 b 是两个整数，其中 b 0 如果存在一个整数 q 使得等式 a=bq 成立，就称 b 整除 a 或者 a 被 b 整除，记作 b|a ，并把b 叫作 a 的因数，把 a 叫作 b 的倍数 .这时， q 也是 a 的因数，我们常常将 q 写成 a b 或 否则，就称 b 不能整除 a 或者 a 不能被 b 整除，记作 a b. 2 整除的基本性质 (1)当 b 遍历整数 a 的所有因数时， -b 也遍历整数 a 的所有因 数 . (2)当 b 遍历整数 a 的所有因数时，
2、a/b 也遍历整数 a 的所有因数 . (3)设 b， c 都是非零整数， (i)若 b|a，则 |b|a|. (ii)若 b|a，则 bc|ac. (iii)若 b|a，则 11 都可以表示成素数的乘积，且在不考虑乘积顺序的情况下，该表达式是唯一的 .即 n= p1 p s , p1 ps , (1) 其中 pi 是素数，并且若 n = q1 q t , q1 qt , 其中 qj 是素数，则 s= t , pi = qj, 1 i s. 推论 1：设 是任一大于 1 的整数，且 为素数，且 则 是 的正因数的充分必要条件是 推论 2： 且 为素数 则 第二章 同余 一 同余概念和基本性质
3、、同余的定义 定义： 如果用 去除两个整数 所得的余数相同，则 称整数 关于模 同余，记作 如果余数不同，则称 关于模 不同余，记作 . 定理 1： 整数 关于模 同余充分必要条件是 、性质 定理 2： 同余关系是一种等价关系，即满足 (1)自反性： (2)对称性：若 (3)传递性：若 定理 3： 若 则： 定理 4： 若 且 则 定理 5： 若 且 则 定理 6： 若 ，则 定理 7： 若 且 则 定理 8： 若 则 定理 9 设整数 n 有十进制表示式： n = ak 10k + ak-1 10k-1 + + a 1 10 + a0 , 0 ai 、剩余类 1定义 1：设 是一个给定的正整
4、数 则 叫做模 的剩余类 定理 1： 设 是模 的剩余类， 则有 (1) 中每一个整数必属于这 个类中的一个 ,且仅属于一个 (2) 中 任意两个整数 属于同一类的充要条件是 、完全剩余系 1定义 2： 在模 的剩余类 中各取一个数 则 个整数 称为模 的一组完全剩余系 任意 个连续的整数一定构成模 的一组完全剩余系 2形成完全剩余系的充要条件 定理 2： 个整数 形成模 的完全剩余系的充要条件是： 3完全剩余系的性质 定理 3： 若 则当 遍历 模 的完全剩余系时，则 也 遍历 模 的完全剩余系 定理 4 设 m 是一个正整数， a 是满足 (a,m)=1 的整数，则存在整数 a 1 a 简
5、化剩余系 1、 简化 剩余类 、简化 剩余系概念 定义 3：若模 的某一剩余类里的数与 互素，则把它称为模 的一 个互素剩余类在与模 互素的全部剩余类中，各取出一整 数组成的系，叫做模 的一组 简化 剩余系 在完全剩余系中所有与模 互素的整数构成模 的 简化 剩余系 2 简化 剩余系的个数 定义 4：欧拉函数 是定义在正整数集上的函数， 的值等于 序列 与 互素的个数 为素数 定理 6： 个整数 构成模 的 简化 剩余系的充要条件是 定理 7： 若 遍历 模 的 简化 剩余系，则 也 遍历 模 的 简化 剩余系 定理 8设 m1 ， m2 是互素的两个正整数，如果 x1 , x2 分别遍历模
6、m1 和 m2 的简化剩余系，则 m2x1 + m1x2 遍历模 m1 m2 的简化剩余系 . 定理 9：若 ，则 npknpakaappnpnnpppnns|1|1)11()11()11()(101则有标准因数分解式为设正整数定理欧拉定理 费马小定理 威尔逊定理 1 欧拉定理 设 m 是大于 1 的整数，如果 a 是满足 (a , m)=1 的整数，则 )m m o d(1a )m( 2费马定理 设 p 是一个素数，则对任意整数 a ,我们有 ap a (mod p) 3（ wilson）设 p 是一个素数 .则 )p m o d(1)!1p( 模重复平方计算法 主要掌握运用该方法解题过程
7、第三章 同余式 1同余式的定义 定义 1 设 m 是一个正整数，设 f(x)为多项式 其中 ai 是整数，则 f(x) 0( mod m ) (1)叫作模 m 同余式 . 若 01nn axaxa)x(f na0 (mod m), 则 n 叫做 f(x)的次数，记作 degf .此时， (1)式又叫做模 m 的 n 次同余式 . 2同余式的解、解数及通解表达式 定理 1 设 m 是一个正整数， a 是满足 a m 的整数则一次同余式 ax b (mod m)有解的充分必要条件是 (a , m)|b ,而且， 当同余式有解时，其解数为 d =( a , m). 定理 2 设 m 是一个正整数，
8、a 是满足 (a,m)=1 的整数，则一次同余式 ax 1(mod m)有唯一解 x a(mod m). 定理 3 设 m 是一个正整数， a 是满足 (a,m)|b 的整数，则一次同余式 ax b(mod m) 的全部解为 .1)m,a(,1,0t)m m o d()m,a(mt)m,a(m m o d()m,a(a)m,a(bx13中国剩余定理 定理 1 (中国剩余定理 )设k1 m,m 是 k 个两两互素的正整数，则对任意的整数k1 b,b ，同余式组 )1()m m o d(bx)m m o d(bxkk11 一定有解，且解是唯一的 例 1 计算 ).77 m o d(2 1 0 0
9、0 0 0 0 解一 利用 2.4 定理 1(Euler 定理 )及模重复平方计算法直接计算 . 因为 77 7 11， ,60)11()7()77( 所以由 2.4 定理 1(Euler 定理 )， )77 m o d(12 60 ，又 1000000 16666 60 40，所以 )77 m o d(22)2(2 40401 6 6 6 6601 0 0 0 0 0 0 ，设 m=77,b=2,令 a=1. 将 40 写成二进制， 40 23 25 ，运用模重复平方法，我们依次计算如下： (1) )77( m od4,1,0 2100 bbaan 计算(2) n1 = 0, 计算 )77
10、m od(16bb,1aa 21201 (3) n2 = 0, 计算 )77 m od(25bb,1aa 22312 (4) n3 = 1, 计算 )77 m od(9bb,25baa 234323 (5) n4 = 0 , 计算 )77 m od(4bb,25aa 24534 (6) n6 = 1 , 计算 )77 23( m odbaa545 最后，计算出 )77 m o d(232 1 0 0 0 0 0 0 解二 令 1 0 0 0 0 0 02x ，因为 77=7 11，所以计算 x(mod 77) 等价于求解同余式组)11 m o d(bx)77 m o d(bx21 因为 Eul
11、er 定理给出 )7 m o d(122 6)7( ，以及 1000000=166666 6+4，所以 )7 m o d(22)2(2b 41 6 6 6 6 661 0 0 0 0 0 01 . 令 77mmm,11m,7m 2121 ， 7mM,11mM1221 分别求解同余式 )11 m o d(17M),7 m o d(111M 21 ，得到 8M,2M 21 故 x 2 11 2+8 7 1 100 23(mod 77) 因此， 21000000 23(mod 77) 例 2： 解同余式组 解： 原同余式组有解且同解于 两两互素 同余式组 有惟一解 原同余式组的解为 第四章 二次同余
12、式与平方剩余 1二次同余式的定义 定义 1 设 m 是正整数，若同余式 1)m,a(),m m o d(ax 2 有解，则 a 叫做模 m 的平方剩余 (二次剩余 )；否则， a 叫做模 m 的平方非剩余 (或二次非剩余 ). 2. 模为奇素数的平方剩余和平方非剩余 讨论模为素数 p 的二次同余式 1),(),( m o d2 papax 定理 1（欧拉判别条件）设 p 是奇素数， (a, p)=1, 则 ( i ) a 是模 p 的平方剩余的充分必要条件是 );( m o d12 1 pa p (ii) a 是模 p 的平方非剩余的充分必要条件是 );( m o d12 1 pa p 并且当
13、 a 是模 p 的平方剩余时，同 余式 (1)恰有二解 . 定理 2 设 p 是奇素数，则模 p 的简化剩余系中平方剩余与平方非剩余的个数各为 (p-1)/2,且 (p-1)/2 个平方剩余与序列： 222 )21(,2,1 p 中的一个数同余 .且仅与一个数同余 . 例 1 利用定理判断 3.勒让德符号 定义 1 设 p 是素数，定义勒让德符号如下： appapa|01,1)pa(若，的平方非剩余是模，若的平方剩余是模若欧拉判别法则 设 p 是奇素数，则对任意整数 a, )p m o d(apa 2 1p 常用定理及结论 设 p 是奇素数，则 (1) 1p1 (2) 2 1p)1(p1 (3
14、) 4) 3 (m o dp , 1-)4 m o d(1p,1p1若若 (4) ;pappa (5) ;pbpapab (6) 设 (a, p) =1, 则 1pa 2 (7) 设 p 是奇素数，如果整数 a, b 满足 a b(mod p),则 pbpa (8) 812p)1(p2 (9)互倒定律 若 p,q 是互素奇素数，则 qp)1(pq 2 1q2 1p 例 1 5355335325330 ，而 153553553)1(535132353353)1(5331)1(5322153215215321381532所以 15355335325330 第五章 指数与原根 一 指数 1指数的定义
15、 定义 1 设 m1 是整数 ， a 是与 m 互素的正整数，则使得)(m o d1 ma e 成立的最小正整数 e 叫做 a 对模 m 的指数，记作)(aord m . 2指数的性质 定理 1 设 m1 是整数， a 是与 m 互素的整数，则整数 d 使得)(m o d1 ma d 的充分必要条件是 daord m |)( . 定理 1 之推论 设 m1 是整数， a 是与 m 互素的整数 ,则)(|)( maord m 性质 1 设 m1 是整数， a 是与 m 互素的整数 (i) 若 b a(mod m),则 )b(o r d)a(o r dmm (ii)设 1a 使得 )m m o d
16、(1aa 1 则 )a(o r d)a(o rm1m . 性质 2 设 m1 是整数， a 是与 m 互素的整数，则 )(m o d maa kd 的充分必要条件是 )( m o d ao rdkdm性质 3 设 m1 是整数， a 是与 m 互素的整数设 d 0,为整数，则),()()(dao rdao rdao rdmmdm 二 原根 1 原根的定义 定义 若 (a,m)=1, 如果 a对模 m的指数是 )(m ，即 )()( aordmm则 a 叫做模 m 的原根 2原根的相关定理及性质 定理 1 设 m1 是整数 ， a 是与 m 互素的整数 .则 1)(10 ,1 ao rd maa
17、a 模 m 两两不同余，特别地，当 a 是模 m 的原根，即 )()( mao rdm 时，这 )( 个数组成模 m 的简化剩余系 定理 2 设 m1 是整数， g 是模 m 的原根，设 d 0 为整数，则 dg 是模 m 的原根当且仅当 1)m(,d( 3 原根存在的条件 定理 1 设 p 是奇素数，则模 p 的原根存在 . 定理 2 设 g 是模 p 的一个原根，则 g 或者 p+g 是模 p2 的原根 . 定理 3 设 p 是一个奇素数，则对任意正整数 a,模 pa 的原根存在 .更确切地说，如果 g 是模 p2 的一个原根， 则对任意正整数 a， g 是模 pa 的原根 . 定理 4 设 a 1,g 是模 pa 的一个原根，则 g 与 g+ pa 中的奇数是模2pa的一个原根 定理 5 模 m 的原根存在的充分必要条件是 aa 2p,p,4,2m ,其中 p是奇素数 . 定理 6 设 m1, 的所有不同素因数是 q1 , ,q k , 则 g 是模 m 的一个原根的充分必要条件是 iq/)m(g 1(mod m),i=1, ,k )m(
