计算机网络安全技术第二章

《计算机网络安全技术第二章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章预备知识2．1数论基础数论是一门古老的数学分支。以前人们都认为它是完全纯粹的数学，在现实生活中很难找到它的实际应用。自从1976年公开密钥体制诞生以来，现代密码学就和数论有着千丝万缕的联系。因此，我们先简单介绍一下有关的数论基本概念。1．引言我们约定：字母N表示全体自然数集合，Z表示全体整数集合，即N={0,1,2,……}Z={……,-2,-1,0,1,2,……}定义2.1.1如果存在一个整数k∈Z使得n=kd，则称d整除n，记作d∣n，其中d称作n的因数，n称作d的倍数。如果不存在这样一个整数k∈Z使得n=kd，则称d不整除n，记作d+n。定义2

2、.1.2整数p（1）,称为素数，如果除了1和其本身外，p没有任何其他因数。不是素数的整数称为合数。例2．16=23，6是合数，26，2是6的因数，6是2的倍数。7=17，除了1和7之外，没有其他因数，因此7是素数。定理2.1.1（带余数除法）设a，b是两个整数，其中b0。则存在两个整数q，r使得a=bq+r0rb成立，其中q和r是唯一确定的。设a，b是两个整数。既是a的因数又是b的因数的数称为a，b的公因数，a和b的所有公因数中最大者，称为a和b的最大公因数，记作gcd(a,b)。既是a的倍数又是b的倍数的数称为a和b的公倍数，a和b的所有

3、公倍数中最小者称为a和b的最小公倍数，记作lcm(a,b)。显然a和b的最大公因数与最大公倍数满足下列等式：lcm(a,b)gcd(a,b)=ab如果对两个整数a,b有gcd(a,b)=1，则称a与b互素。定理2.1.2设a，bN，则存在两个整数u和v使得ua+vb=gcd(a，b)定理2.1.3（算术基本定理）任何一个正整数m都存在唯一的因数分解形式m=其中，eiN，pi是素数且p1p2pn。这个分解形式也称为m的标准分解形式。例2．26=23，20=225，100=2252有了算术基本定理后，就可以把任意整数分解为标准形式，从而可以

4、方便地求出两个整数的最大公因数和最小公倍数。设a，b是两个整整数，且有标准分解形式：a=，b=，ei，fiN则gcd(a，b)=lcd(a，b)=其中，min{x,y}表示x，y中最小者，max{x，y}表示x，y中最大者。2．Euclid算法利用算术基本定理，原则上可以求得任何两个整数的最大公因数，但当两个整数比较大时求他们的标准分解式就非常困难，目前还没有有效的算法，因此求他们的最大公因数也变得非常困难。Euclid算法从另一方面解决了求两个整数的最大公因数的问题。Euclid算法由称为辗转相除法，即带余数除法，有下列不等式：a=bq1+r10r

5、1bb=r1q2+r20r2r1rn-2=rn-1qn+rn0rnrn-1rn-1=rnqn+1+rn+1rn+1=0因为每进行一次带余数的除法，余数至少减1，而b是有限的。所以，最多进行b次带余数的除法，总可以得到一个余数是0的等式，即最后一个等式，而最后一个不为0的余数rn就是我们要求的最大公因数gcd(a，b)。从上面的Euclid算法中可以看出，将r1=a–bq1代入第二个等式中，，将r2=b–r1q2代入到第三个等式中，…，将rn-1=rn-3–rn-2qn-1代入倒数第二个等式中，就可得到rn关于a,b的一个表示式，其中a,b的系

6、数分别就是定理2.1.2中的u,v。故最后一个不为零的余数就是a、b的最大公因数。例2．3求gcd{1694,917}1694=1917+777917=1777+140777=5140+77140=177+6377=163+1463=414+714=27+0所以gcd(1694，917)=7进行回代7=63-414=63-4（77-63）=-477+563=-477+5（140-77）=5140-977=5140-9（777-5140）=-9777+50140=-9777+50（917-777）=50917-

7、59777=50917-59（1694-917）-591694+109917即7=u1694+v917其中u=-59，v=1093.同余定义2.1.3假设a和b是两个整数，m是一个正整数，如果mba，则称a和b对模m同余。记作a≡b(modm)。例2．43和1对模2同余，4和1对模3同余，即3≡1（mod2），4≡1（mod3）定理2.1.4同余的性质设a，b，c和m是整数，则有：i.a≡a（modm）ii.若a≡b（modm），则b≡a（modm）ⅲ.若a≡b（modm），b≡c（modm），则a≡c（modm）假设a和b被m除，获得

8、整数商和余数，这个余数在0和m-1之间，即a=q1m+r1和b=q2m+r2，0