《信息安全专题讲座05.ppt》由会员分享，可在线阅读，更多相关《信息安全专题讲座05.ppt（21页珍藏版）》请在三一办公上搜索。
1、第五章数论导引,1 素数和数的互素 除数(因子)的概念：设z为有全体整数而构成的集合，若 b0且 使得a=mb,此时称b整除a.记为ba,还称b为a的除数(因子).注:若a=mb+r且01被称为素数是指p的因子仅有1,-1,p,-p。,算术基本定理：任何一个不等于0的正整数a都可以写成唯一的表达式aP11P22Ptt，这里P1P2P3Pt是素数，其中i0最大公约数：若a,b,cz，如果ca，cb，称c是a和b的公约数。正整数d称为a和b的最大公约数，如果它满足d是a和b的公约数。对a和b的任何一个公约数c有cd。注：1*.等价的定义形式是：gcd（a,b）maxk ka，kb 2*若gcd（a
2、,b）=1，称a与b是互素的。,模 算术 全体整数而构成的集合对整数的加法和乘法的两种运算是封闭的且满足算术运算的所有定律，此时我们称整数集合z为整数环。整数环z对除法运算不封闭。带余除法：az,0，可找出两个唯一确定的整数q和r,使a=qm+r,0=r m,q和r这两个数分别称为以m去除a所得到的商数和余数。(若r=0则ma）整数同余式和同余方程：定义（同余）称整数a模正整数m同余于整数b，并写ab（mod m）是指mab,m称为模数。注：1*.ma-ba=q1m+r,b=q2m+r即a和b分别 除以m有相同的余数。“同余”二字的来源就在于此。,2*.相对于某个固定模数m的同余关系，是整数间
3、的一种等价关系。具有等价关系的三点基本性质：自反性：对任意整数a有aa（modm）对称性：如果ab(modm)则ba（modm）传递性：如果ab(modm）bc（modm）则ac(modm)于是，全体整数集合z可按模m（m1）分成一些两两不交的等价类。3*.整数模m同余类共有m个，他们分别为mk+0,mk+1,mk+2,mk+(m-1);kz，每一个算一类，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称0,1,2,m-1为标准完全剩余系。Z模12的标准剩余系为：0,1,2,3,4,5,6,7,8,9,10,11,4*.对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘
4、：(1)a(mod m)b(mod m)=(ab)(mod m)(2)a(mod m)*b(mod m)=a*b(mod m)例子.通过同余式演算证明5601是56的倍数，2231是47的倍数。解：注意53=12513(mod56)于是有561691(mod56)对同余式的两边同时升到10次幂，即有56560-1。其次,注意26=64-30(mod47),于是,223=(26)325=(26 26)26 25 900*(-30)*(32)mod(47)(7)(-30)*(32)(mod47)1(mod47)于是有 47223-1定理：(消去率)对于abac（mod m）来说，若(a,m)1则b
5、c(mod m)5*.一次同余方程axb(mod m)这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b 定理：如记(a,m)=d,则同余方程axb(mod m)有解的充分必要条件是db。当这个条件满足时，恰有d个模m同余类中的整数是上述方程的解。证明：略。（从ax+my=b入手）,6*.整数环z模正整数m得到的剩余类集合可以记为zm(或z/(m)zm=0,1,m-1 在4中已说明zm对剩余类的加法，乘法是封闭的，可列出它们的加乘表。（见书214页）。我们称为zm为剩余类环（或同余类环）7*.在整数环z中是没有零因子的，即两个非零整数的乘积一定不等于0，但
6、是剩余环则不然。例z12中：3*4=12=0 说明，zm中的元素可分为两类，一类是零因子，即若zm,0存在zm且0，有*=0，称，都为zm中的零因子。另一类是可逆元，即若zm，存在zm使*=1，此时,互为各自的逆元，记-1=；-1=,定理：剩余类环zm中元素=a为zm的可逆元(a,m)=1要证明这个定理，只需证明下列引理：引理：任意两个整数a和b都有一个最大公约数，这样一个最大公约数d可以表示成a,b二数关于整系数的线性组合，即有s,tz，使dsatb。证明：不妨设b0，用辗转相除法，先用b去除a，得 a=q1b+r1,0=r1b;(1)如果r1=0，停止，否则再用r1去除b，得 b=q2r1
7、+r2,0=r2r1;(2)如果r2=0，停止，否则再用r2去除r1，得 r1=q3r2+r3;0=r3r2;(3)等等，这样一直进行下去，可得一系列关系式：rk-3=qk-1rk-2+rk-1,0=rk-1rk-2;(k-1)rk-2=qkrk-1+rk,0=rkrk-1;(k),由于历次所得的余数r1 r2 r3 r4 rk=0是严格递降的一串非负整数，故最后总会出现余数为0的情形：rk-1=qk+1rk(k+1)所以，进行有限步必停止，此时d=rk=(a,b)定成立，这是因为1*.可见rk为a和b的公约数，只要按倒序分析自然有此结论。2*.a和b的任何一个公约数c都是rk的约数，只要按正
8、序分析，自然可知。为证定理的后一部分，将式(1)做移项有 r1=s1a+t1b（其中s1=1,t1=-q1）再将式(2)右端通过移项变为r2=s2a+t2b这样一直下去，最后得d=rk=s*a+t*b,s,tz,例子：求(180，252)，并将他表示为180和252这两个数的一个带整系数的线性组合。解：252=1*180+72(1)180=2*72+36(2)72=2*36(3)得(180,252)=36，同时有72=252-1*180(1)由(2)得36=180-2*72(2)将(1)代入(2)，即得 36=180-2*(250-180)=3*180-2*252,3 Format定理和Eul
9、er定理,Format定理：如果p是素数并且a是正整数,pa，那么，ap-11(mod p)证明：z*pzp(,p)=1 易见，z*p=1,2,3,(p-1)且因为（a,p）1知 a z*p=a,2a,3a,(p-1)a=z*p，原因是a z*p内的元素两两不同。他们刚好为1，2，3，（p1）的一个排列。所以 a*2a*3a*(p-1)a1*2*3*(p-1)(modp)由（(p1)！，p）1，所以 ap-11(modp)注：易见对（a，p）1 有apa(modp),Euler 函数定义(Euler函数(n)：(n)是这样来定义的，当n1 时，(1)1；当n1时，它的值(n)等于比n小而与n互
10、素的正整数的个数。以n24为例，比24小而与24 互素的正整数为：1，5，7，11，13，17，19，23因此，我们有(24)8。易见，若p为素数，则(p)p1。注：1*.若p，q都为素数且pq，此时有(pq)(p)(q)=（p1）（q1）证明：考虑zpq剩余类的集合是0，1，2，（pq-1）集合中与pq不互素的元素子集为p,2p,(p-1)q和子集q,2q,(p-1)q以及0，于是若设npq，有(n)=pq-(q-1)+(p-1)+1=(p-1)(q-1)=(p)(q),例：(21)=(3*7)=(3)(7)=2*6=12.2*.设n=p1e1p2e2prer，其中p1,p2,pr为互异素数
11、，则(n)=p1e1-1p2e2-1prer-1(p1-1)(p2-2)(pr-1)=n(1-1/p1)(1-1/p2)(1-1/p3)(1-1/pr)3*.Euler公式证明：考虑1/n,2/n,n/n，然后化简成既约分数，分母为d的一类分数有(d)个，于是欧拉定理（Euler）：若整数a于整数n互素，则a(n)1(mod n)证明：设小于n而和n互素的个正整数为r1,r2,r3,r(n)(1),他们是模n两两互不同余的。对每一个定数i来说，由于a和ri都与n互素，所以(ari,n)=1，所以ari同余于（1）中的某个ri即ariri(mod n)，1=i=(n)并且当ij时有ari/arj
12、(mod n).于是,为 的置换.所以有由(ri,n)=1,所以 注：1*.np时，有ap-11(mod p)为Format定理！2*.易见a(n)+1a(mod n)3*.若n=pq，p与q为相异素数，取0mn，若（m,n）1，有m(n)+1m(mod n)，也即m(p-1)(q-1)+1m(mod n).,4*.对于3中，若(m，n)p，或q，书中P220P221给出了详细讨论。也同样有m(n)+1m(mod n)5*.由(m(n)k1k(mod n)知mk(n)1(modn)，进一步mk(n)+1m(mod n)mk(p-1)(q-1)+1m(mod n),4 中国剩余定理,例子：（孙子
13、算经）今有物不知其数。三三数之余二；五五数之余三；七七数之余二。问物几何？答曰：二十三。232*70+3*21+2*15(mod 105)（口诀：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。）问，70，21，15如何得到的？原问题为：求解同余方程组,注意：若x0为上述同余方程组的解，则x0=x0+105*k(kz)也为上述同余方程组的解。有意义的是，解题口诀提示我们先解下面三个特殊的同余方程组(1)(2)(3)的特殊解=?=?=?以方程（1）为对象，相当于解一个这样的同余方程 35y1(mod 3)，为什么呢？原因是，从（1）的模数及条件知，x应是35的倍数，于是可以假设x35y有,35y1(mod 3)相当于2y1(mod)3解出y=2（mod3）于是x35*2 70(mod105)类似地得到（2）、（3）方程的模105的解21、15。于是有得,中国剩余定理：设自然数m1,m2,mr两两互素，并记N=m1m2mr，则同余方程组在模N同余的意义下有唯一解。,证明：考虑方程组，(1=i=r)由于诸mi(1=i=r)两两互素，这个方程组作变量替换，令x=(N/mi)*y，方程组等价于解同余方程：(N/mi)y1(mod mi),若要得到特解yi,只要令xi=(N/mi)yi则方程组的解为x0=b1x1+b2x2+brxr(mod N)模N意义下唯一。,
