信息安全导论数学基础一、模运算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是某个整数 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 最大公约数（greatest common divisor，简写为gcd；或highest common factor，简写为hcf)，指某几个整数共有因子中最大的一个 最小公倍数（lcm） 关系：gcd(a, b)×lcm(a, b) = ab5、模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的乘法逆元二、欧拉函数 欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数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，有ap ≡ a mod p三、指数及其原根 定义：设n≥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)=1ai=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可以检测是否为原根．由上节推论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,n)=1，则存在唯一的γ，0≤γ< n，使得a≡gγ(modn)我们把γ称为是a对模n的以g为底的指标（或离散对数），记为γn,g(a)或indexn,g(a)当模n与原根g很明确时，也可以简记为γg(a)、γ(a) 或indexg(a)、index(a)。