信息安全导论数学基础.doc

信息安全导论数学基础 一、模运算 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、模p相等如果两个数a、b满足a mod p = b mod p，则称他们模p相等，记做 a ≡ b mod p 可以证明，此时a、b满足 a = kp + b，其中k是某个整数。 对于模p相等和模p乘法来说，有一个和四则运算中迥然不同得规则。在四则运算中，如果c是一个非0整数，则 ac = bc 可以得出 a =b 但是在模p运算中，这种关系不存在(3 x 3) mod 9 = 0 (6 x 3) mod 9 = 0 但是 3 mod 9 = 3 6 mod 9 =6 定理（消去律）：如果gcd(c,p) ＝ 1 ，则 ac ≡ bc mod p 可以推出 a ≡ b mod p gcd　最大公约数（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与互素时，a关于模的乘法逆元有唯一解。如果不互素，则无解。如果为素数，则从1到-1的任意数都与互素，即在1到-1之间都恰好有一个关于模的乘法逆元。欧拉函数 欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数的个数，记做：φ(n)，其中φ(1)被定义为1，但是并没有任何实质的意义。定义小于n且和n互质的数构成的集合为Zn，称呼这个集合为n的完全余数集合。于素数p，φ(p)= p -1.对于两个素数p、q，他们的乘积n = pq 满足φ(n) =(p-1)(q-1) 欧拉定理对于互质的整数a和n，有aφ(n) ≡ 1 mod n 推论：对于互质的数a、n，满足aφ(n)+1 ≡ a mod n 费马定理a是不能被质数p整除的正整数，则有ap-1 ≡ 1 mod p 推论：对于不能被质数p整除的正整数a，有ap ≡ a mod pn≥1，(a,n)=1,使式 ad≡1(mod n) 成立的最小的正整数d称为对模的指数（习惯上也称为阶或周期），记作δn(a)。当δn(a)= φ(n) 时，称a是模n的原根。 性质1 设n≥1，(a,n)=1，对任意整数d，如果 ad≡1(mod n) 则δn(a)|d（称作δn(a)整除d） 性质2 若b≡a(mod n)，(a,n)=1,则δn(a)≡δn(b) 性质3 δn(a)|φ(n), 性质4 若(a,n)=1 ai=aj (mod n) 则 i=j(mod δn(a)) 性质5 设 a a-1≡1(mod n) 则 δn(a)= δn(a-1) 性质6 当（k, δn(a)）=1时，则 δn(a)= δn(ak)。 性质7 若g为模n的原根，则模n的原根的个数为φ(φ(n))，并且 {gi|(i, φ(n))=1,1≤iφ(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 设p是奇素数，那么对任意的α≥1，模 pα,2pα均有原根。 定理2 设n=1,2,4,pα,2pα（p是奇素数），φ(n)的所有不同的素因子为q1q2…qs，那么g是模n的原根的充要条件: gφ(n)/ qj≠1(mod n),j=1,2,…,s。 对于每个随机选取的随机数a根据定理2可以检测是否为原根．由上