信息安全导论数学基础

1、信息安全导论数学基础一、模运算1、模p运算和普通的四则运算有很多类似的规律，如： 规律 公式 结合率 (a+b) mod p + c)mod p = (a + (b+c) mod p) mod p (a*b) mod p * c)mod p = (a * (b*c) mod p) mod p 交换率 (a + b) mod p = (b+a) mod p (a × b) mod p = (b × a) mod p 分配率 (a +b)mod p × c) mod p = (a × c) mod p + (b × c) mod p) mod p

2、2、模p相等：如果两个数a、b满足a mod p = b mod p，则称他们模p相等，记做a b mod p可以证明，此时a、b满足 a = kp + b，其中k是某个整数。 3、对于模p相等和模p乘法来说，有一个和四则运算中迥然不同得规则。在四则运算中，如果c是一个非0整数，则ac = bc 可以得出 a =b但是在模p运算中，这种关系不存在。例如：(3 x 3) mod 9 = 0(6 x 3) mod 9 = 0但是 3 mod 9 = 36 mod 9 =64、定理（消去律）：如果gcd(c,p) 1 ，则 ac bc mod p 可以推出 a b mod p 。 注释： gcd最大

3、公约数（greatest common divisor，简写为gcd；或highest common factor，简写为hcf)，指某几个整数共有因子中最大的一个。 最小公倍数（lcm） 关系：gcd(a, b)×lcm(a, b) = ab。5、模P乘法逆元：对于整数a、p，如果存在整数b，满足ab mod p =1，则说，b是a的模p乘法逆元。定理：a存在模p的乘法逆元的充要条件是gcd(a,p) = 1。注释：当a与p互素时，a关于模p的乘法逆元有唯一解。如果不互素，则无解。如果p为素数，则从1到p-1的任意数都与p互素，即在1到p-1之间都恰好有一个关于模p的乘法逆元。二、

4、欧拉函数 欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数的个数，记做：(n)，其中(1)被定义为1，但是并没有任何实质的意义。定义小于n且和n互质的数构成的集合为Zn，称呼这个集合为n的完全余数集合。1、对于素数p，(p)= p -1.对于两个素数p、q，他们的乘积n = pq 满足(n) =(p-1)(q-1) 2、欧拉定理：对于互质的整数a和n，有a(n) 1 mod n。 推论：对于互质的数a、n，满足a(n)+1 a mod n 。3、费马定理：设a是不能被质数p整除的正整数，则有ap-1 1 mod p 推论：对于不能被质数p整除的正整数a

5、，有ap a mod p。三、指数及其原根 定义：设n1，(a,n)=1,使式ad1(mod n)成立的最小的正整数d称为对模的指数（习惯上也称为阶或周期），记作n(a)。当n(a)= (n) 时，称a是模n的原根。性质1 设n1，(a,n)=1，对任意整数d，如果ad1(mod n)则n(a)|d（称作n(a)整除d）性质2 若ba(mod n)，(a,n)=1,则n(a)n(b) 性质3 n(a)|(n),性质4 若(a,n)=1ai=aj (mod n)则i=j(mod n(a)性质5 设a a-11(mod n)则n(a)= n(a-1)性质6 当（k, n(a)）=1时，则 n(a)

6、= n(ak)。性质7 若g为模n的原根，则模n的原根的个数为(n)，并且gi|(i, (n)=1,1i<(n)即为所有原根的集合。性质8 n(ab)= n(a) n(b)的充要条件是(n(a),n(b)=1。性质9 若n|m，则n(a)| m (a)。注释：如果n，m是整数，n|m（称作n整除m）意味着存在某个整数k，有m=kn。性质10若(m1,m2)=1, 则m1m2 (a)=m1(a),m2(a)性质11对任意a,b，一定存在c，使n(c)= n(a),n(b)定理1 模n有原根的充要条件是n=1,2,4,p,2p,其中p是奇素数，1。引理1 设p是素数，则模p必有原根。引理2

7、设p是奇素数，那么对任意的1，模 p,2p均有原根。定理2 设n=1,2,4,p,2p（p是奇素数），(n)的所有不同的素因子为q1q2qs，那么g是模n的原根的充要条件:g(n)/ qj1(mod n),j=1,2,s。对于每个随机选取的随机数a根据定理2可以检测是否为原根由上节推论2知原根分布的平均概率为(n)/ n，这个概率表明用随机的方法可以在多项式时间内找到的一个原根引理2与定理2提供了密码学中寻找原根的常用的概率方法。定理3 如果模n存在原根，则任一原根g可以生成模n的既约剩余系，即g0，g1，,g(n)-1构成模的既约剩余系。小结：在一个模的既约剩余系中，如果一个元素的指数恰好等于(n)，则这个元素即为模n的一个原根在存在原根的既约剩余系中，每个元素均可以表示成原根的幂，反过来原根的幂所表示的所有不同的元素恰好构成既约剩余系，这就给出了一种构造模n的既约剩余系的很自然的一种方法但只有 n=1,2,4,p,2 p才有原根。三、指标、既约剩余系的构造 指标是初等数论中一个基本的概念，求指标问题即为密码学中经常提到的求离散对数问题在密码学中，在表示上习惯用指标的英文形式，但习惯上称为离散对数)(indexn,g(a)（Discrete logarithm）。 定义1 g为模n的原根，给定a, (a,