资源描述：
《信息安全导论数学基础》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、信息安全导论数学基础一、模运算1、模p运算和普通的四则运算有很多类似的规律，如：规律公式结合率((a+b)modp+c)modp=(a+(b+c)modp)modp((a*b)modp*c)modp=(a*(b*c)modp)modp交换率(a+b)modp=(b+a)modp(a×b)modp=(b×a)modp分配率((a+b)modp×c)modp=((a×c)modp+(b×c)modp)modp2、模p相等：如果两个数a、b满足amodp=bmodp，则称他们模p相等，记做a≡bmodp可以证明，此时a、b满足a=kp+b，其中k是某个整数。3、对于模p相
2、等和模p乘法来说，有一个和四则运算中迥然不同得规则。在四则运算中，如果c是一个非0整数，则ac=bc可以得出a=b但是在模p运算中，这种关系不存在。例如：(3x3)mod9=0(6x3)mod9=0但是3mod9=36mod9=64、定理（消去律）：如果gcd(c,p)＝1，则ac≡bcmodp可以推出a≡bmodp。注释：gcd 最大公约数（greatestcommondivisor，简写为gcd；或highestcommonfactor，简写为hcf)，指某几个整数共有因子中最大的一个。最小公倍数（lcm）关系：gcd(a,b)×lcm(a,b)=ab。5、模P
3、乘法逆元：对于整数a、p，如果存在整数b，满足abmodp=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的完全余数集合。
4、1、对于素数p，φ(p)=p-1.对于两个素数p、q，他们的乘积n=pq满足φ(n)=(p-1)(q-1)2、欧拉定理：对于互质的整数a和n，有aφ(n)≡1modn。推论：对于互质的数a、n，满足aφ(n)+1≡amodn。3、费马定理：设a是不能被质数p整除的正整数，则有ap-1≡1modp推论：对于不能被质数p整除的正整数a，有ap≡amodp。三、指数及其原根定义：设n≥1，(a,n)=1,使式ad≡1(modn)成立的最小的正整数d称为对模的指数（习惯上也称为阶或周期），记作δn(a)。当δn(a)=φ(n)时，称a是模n的原根。性质1设n≥1，(a,n)
5、=1，对任意整数d，如果ad≡1(modn)则δn(a)
6、d（称作δn(a)整除d）性质2若b≡a(modn)，(a,n)=1,则δn(a)≡δn(b)性质3δn(a)
7、φ(n),性质4若(a,n)=1ai=aj(modn)则i=j(modδn(a))性质5设aa-1≡1(modn)则δn(a)=δn(a-1)性质6当（k,δn(a)）=1时，则δn(a)=δn(ak)。性质7若g为模n的原根，则模n的原根的个数为φ(φ(n))，并且{gi
8、(i,φ(n))=1,1≤i<φ(n)}即为所有原根的集合。性质8δn(ab)=δn(a)δn(b)的充要条件是(δn(a),
9、δn(b))=1。性质9若n
10、m，则δn(a)
11、δm(a)。注释：如果n，m是整数，n
12、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，那
13、么g是模n的原根的充要条件:gφ(n)/qj≠1(modn),j=1,2,…,s。对于每个随机选取的随机数a根据定理2可以检测是否为原根．由上节推论2知原根分布的平均概率为φ(φ(n))/n，这个概率表明用随机的方法可以在多项式时间内找到的一个原根．引理2与定理2提供了密码学中寻找原根的常用的概率方法。定理3如果模n存在原根，则任一原根g可以生成模n的既约剩余系，即{g0，g1，…,gφ(n)-1}构成模的既约剩余系。小结：在一个模的既约剩余系中，如果一个元素的指数恰好等于φ(n)，则这个元素即为模n的一个原根．在存在原根的既约剩余系中，每个元素均可以表示成原根
