《保障与安全数论课件》由会员分享，可在线阅读，更多相关《保障与安全数论课件（30页珍藏版）》请在金锄头文库上搜索。
1、保障与安全数论,1,数论导引,1 素数和数的互素 除数(因子)的概念：设z为所有全体整数构成的集合，若 b0且 使得a=mb , 此时称b整除a.记为ba,还称b为a的除数(因子). 注:若a=mb+r且01被称为素数是指p的因子仅有1,-1,p,-p。 定义：若ax mod n =1，则称a与x对于模n互为逆元。 用Euclid算法求乘法逆元 若a和n互素，则a在模n下有逆元。,保障与安全数论,2,算术基本定理： 任何一个不等于0的正整数a都可以写成唯一的表达式 aP11P22Ptt，这里P1P2P3Pt是素数，其中i0 最大公约数： 若a,b,cz，如果ca，cb，称c是a和b的公约数。正
2、 整数d称为a和b的最大公约数，如果它满足 d是a和b的公约数。 对a和b的任何一个公约数c有cd。 注：1*. 等价的定义形式是： gcd（a,b）maxk ka，kb 2*若gcd（a,b）=1，称a与b是互素的。,保障与安全数论,3,模 算术 全体整数Z构成的集合对整数的加法和乘法的两种运算是封闭的且满足算术运算的所有定律，此时我们称整数集合z为整数环。整数环z对除法运算不封闭。 带余除法： az0，可找出两个唯一确定的整数q和r,使a=qm+r, 0=r m，q和r这两个数分别称为以m去除a所得到的商数和余数。 (若r=0则ma） 整数同余式和同余方程： 定义（同余）称整数a模正整数m
3、同余于整数b，并写 ab（mod m）是指mab, m称为模数。注：1*.ma-b等价于a=q1m+r,b=q2m+r即a和b分别 除以m有相同的余数。“同余”二字的来源就在于此。,保障与安全数论,4,2*.相对于某个固定模数m的同余关系，是整数间的一种等价关系。具有等价关系的三点基本性质： 对任意整数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，每一个算一类
4、，每一类都可以选一个代表元，一般选这一类中的最小的非负整数。于是称0,1,2,m-1为标准完全剩余系。Z模12的标准剩余系为：0,1,2,3,4,5,6,7,8,9,10,11,自反性,对称性,传递性,保障与安全数论,5,4*. 对于某个固定模m的同余式可以象普通的等式那样相加相减和相乘 （可交换的、可结合的、可分配的）而且，简化运算每个中间结果的模n运算，其作用与先进行全部运算，然后再简化模n运算是一样的。 (1)a(mod m)b(mod m) mod m =(ab)(mod m) (2)a(mod m)b(mod m) mod m =a b(mod m) (3) )(a b)(mod m
5、)+(ac)(mod m) mod m =(a (b+c)(mod m) 例1 152 mod 12 =(3*3) mod 12=9 例2 通过同余式演算证明5601是56的倍数，2231是47的倍数。 解： 注意53=12513(mod56) 于是有561691(mod56) 对同余式的两边同时升到10次幂， 即有56560-1。,保障与安全数论,6,注意26=64-30(mod47), 于是 223=(26)325=(26 26)26 25 900 (-30) (32) mod(47) (7)(-30) (32) (mod47) (-30) (224) (mod47) (-30) (36)
6、 (mod47) (-1080) (mod47) 1(mod47) 于是有 47223-1 求117 (mod13)， 112 =121 4 (mod13)， 114 42 3 (mod13)， 117 114 3 2 (mod13),保障与安全数论,7,定理：(消去率)对于abac（mod m）来说，若(a,m)1则bc(mod m) 5*.一次同余方程axb(mod m)这个方程有没有解，相当于问有没有那样一个整数x，使得对于某个整数y来说，有ax+my=b 定理：如记(a,m)=d,则同余方程axb(mod m)有解的充分必要条件是db。当这个条件满足时，恰有d个模m同余类中的整数是上述
7、方程的解。 证明：略。（从ax+my=b入手）,保障与安全数论,8,6*.整数环z模正整数m得到的剩余类集合可以记为zm(或z/(m)zm=0,1,m-1 在4中已说明zm对剩余类的加法，乘法是封闭的，可列出它们的加乘表。我们称zm为剩余类环（或同余类环） 7*.在整数环z中是没有零因子的，即两个非零整数的乘积一定不等于0，但是剩余环则不然。 例z12中：3*4=12=0 说明，zm中的元素可分为两类，一类是零因子，即若zm,0存在zm且0，有*=0，称，都为zm中的零因子。另一类是可逆元，即若zm，存在zm使*=1，此时,互为各自的逆元，记-1=；-1=,保障与安全数论,9,定理：剩余类环z
8、m中元素=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+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)
9、 rk-2=qkrk-1+rk,0=rkrk-1;(k),保障与安全数论,10,由于历次所得的余数 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的约数，只要按正序分析，自然可知。 为证定理的后一部分，将式(1)做移项有 r1=s1a+t1b（其中s1=1,t1= -q1）再将式(2)右端通过移项变为r2=s2a+t2b 这样一直下去，最后得d=
10、rk=s*a+t*b,s,tz,保障与安全数论,11,欧几里得（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。而推广的Euclid算法不仅可求两个正整数的最大公因子，而且当两个正整数互素时，还可求出其中一个数关于另一个数的乘法逆元。 Euclid算法是基于下面一个基本结论： 对任意非负整数a和正整数b，有gcd(a, b)=gcd(b,a mod b)。即a，b的公因子集合与b，a mod b的公因子集合相等，两个集合的最大值也相等。 例如： gcd(55, 22)=gcd(22, 55 mod 22) = gcd(22,11) =gcd(11, 0)=11。
11、 在求两个数的最大公因子时，可重复使用以上结论。 例如： gcd(18,12)=gcd(12,6)=gcd(6,0)=6, gcd(11,10)=gcd(10,1)=gcd(1,0)=1。,欧几里得算法,保障与安全数论,12,例子：求gcd(180，252)，并将他表示为180和252这两个数的一个带整系数的线性组合。 解：252=1*180+72(1) 180=2*72+36 (2) 72=2*36(3) 得gcd(180,252)=36，同时有 72=252-1*180 (1 ) 由(2)得36=180-2*72 (2 )将(1)代入(2 )，即得 36=180-2*(252-180) =
12、3*180-2*252 求gcd(1970,1066)=2,保障与安全数论,13,求gcd(1970, 1066)。 1970=11066+904,gcd(1066, 904) 1066=1904+162,gcd(904, 162) 904=5162+94,gcd(162, 94) 162=194+68,gcd(94, 68) 94=168+26,gcd(68, 26) 68=226+16,gcd(26, 16) 26=116+10,gcd(16, 10) 16=110+6,gcd(10, 6) 10=16+4,gcd(6, 4) 6=14+2,gcd(4, 2) 4=22+0,gcd(2,
13、0) 因此gcd(1970, 1066)=2。,保障与安全数论,14,计算逆元的方法有 1、用欧拉推广公式解：x=(ba (n)-1)modn 2、用欧几里德算法解： x=(b(a -1modn)modn 通常欧几里德算法在计算逆元方面较欧拉推广更快，特别是500位范围内的数。,保障与安全数论,15,Euclid算法就是用这种方法，因gcd(a, b)=gcd(|a|, |b|)，因此可假定算法的输入是两个正整数，设为d，f，并设f d。 Euclid（f, d） 1. Xf; Yd； 2. if Y=0 then return X=gcd(f,d)； 3. R=X mod Y； 4. X=Y
14、； 5. Y=R； 6. goto 2。,保障与安全数论,16,求乘法逆元 如果gcd(a, b)=1 ，则b在mod a下有乘法逆元（不妨设ba），即存在一x (xa)，使得bx1 mod a。推广的Euclid算法先求出gcd(a, b)，当gcd(a, b)=1时，则返回b的逆元。,保障与安全数论,17,扩展Euclidean 算法,设r0为a ， r1为b0，用辗转相除法，先用b去除a，得 r0 =q1 r1 +r2, 0r2r1 r1 =q2 r2 +r3, 0r3r2; 等等，这样一直进行下去，可得一系列关系式： rm-2=qm-1rm-1+rm, 0rmrm-1 rm-1=qmr
15、m 结论：假定gcd(r0 , r1)=1, 1 = gcd(r0 , r1)= sm r0+tm r1 那么r1-1mod r0 = tmmod r0,保障与安全数论,18,Extended Euclid(f, d) （设 f d） 1. (X1,X2,X3)(1,0,f);(Y1,Y2,Y3)(0,1,d); 2. if Y3=0 then return X3=gcd(f, d)；no inverse; 3. if Y3=1 then return Y3=gcd(f, d)；Y2=d-1 mod f; 4. Q=X3Y3 ； 5. (T1,T2,T3)(X1-QY1,X2-QY2,X3-Q
16、Y3); 6. (X1,X2,X3)(Y1,Y2,Y3); 7. (Y1,Y2,Y3)(T1,T2,T3); 8. goto 2。,保障与安全数论,19,算法中的变量有以下关系： fT1+dT2=T3;fX1+dX2=X3;fY1+dY2=Y3 在算法EUCLID (f, d)中，X等于前一轮循环中的Y，Y等于前一轮循环中的X mod Y。而在算法Extended Euclid(f, d)中，X3等于前一轮循环中的Y3，Y3等于前一轮循环中的X3-QY3，由于Q是Y3除X3的商，因此Y3是前一轮循环中的Y3除X3的余数，即X3 mod Y3，可见Extended Euclid(f, d)中的X3、Y3与Euclid(f, d)中的X、Y作用相同，因此可正确产生gcd(f, d)。 如果gcd(f, d)=1，则在最后一轮循环中Y3=0，X3=1，因此在前一轮循环中Y3=1。由Y3=1可得: fY1+dY2=Y3，fY1+dY2=1，dY2=1+(-Y1)f，dY21 mod f，所以Y2d-1 mod f。,保障与安全数论,20,例 用扩展Euclidean算法计算28-1mod 75
