第二章 预备知识21 数论基础数论是一门古老的数学分支。以前人们都认为它是完全纯粹 的数学，在现实生活中很难找到它的实际应用。自从1976年 公开密钥体制诞生以来，现代密码学就和数论有着千丝万缕 的联系。因此，我们先简单介绍一下有关的数论基本概念。1 引言我们约定：字母N表示全体自然数集合，Z表示全体整数集合 ，即N = 0,1,2,Z = ,-2,-1,0,1,2,定义2.1.1 如果存在一个整数kZ使得n = kd，则称d整除n，记 作dn ，其中d称作n的因数，n称作d的倍数。如果不存在这样 一个整数kZ使得n = kd，则称d不整除n，记作d + n 。定义2.1.2 整数p（ 1）,称为素数，如果除了1和其本身外，p没 有任何其他因数。不是素数的整数称为合数。例21 6 = 23 ，6是合数，26 ，2是6的因数，6是2的倍数。7 = 17，除了1和7之外，没有其他因数，因此7是素数。定理2.1.1 （带余数除法）设a，b是两个整数，其中b 0 。则存 在两个整数q，r使得a = bq + r 0 r b成立，其中q和r是唯一确定的。设a，b是两个整数。既是a的因数又是b的因数的数称为a，b的公因 数，a和b的所有公因数中最大者，称为a和b的最大公因数，记作 gcd ( a , b )。既是a的倍数又是b的倍数的数称为a和 b的公倍数，a 和b的所有公倍数中最小者称为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 = 其中，eiN，pi是素数且p1p2p n。 这个分解形式也称为m的标准分解形式。例22 6 =23， 20=225， 100 =2252有了算术基本定理后，就可以把任意整数分解为标准形式，从 而可以方便地求出两个整数的最大公因数和最小公倍数。设a， b是两个整整数，且有标准分解形式： ， ei ，fiN则 gcd (a，b) =lcd (a，b) =其中，min x ,y 表示x，y中最小者，max x ，y 表示x，y 中最大者。 2Euclid算法利用算术基本定理，原则上可以求得任何两个整数的最大公因数 ，但当两个整数比较大时求他们的标准分解式就非常困难，目前 还没有有效的算法，因此求他们的最大公因数也变得非常困难。 Euclid算法从另一方面解决了求两个整数的最大公因数的问题。 Euclid算法由称为辗转相除法，即带余数除法，有下列不等式：a = bq1 + r1 0 r1 bb = r1q2 + r2 0 r2 r1rn-2 = rn-1 q n+rn 0 rn rn-1rn-1 = rnqn+1 +rn+1 rn+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的 系数分别就是定理2.1.2中的u , v。故最后一个不为零的余数就是a、 b的最大公因数。 例23 求gcd 1694,917 1694=1917+777917=1777+140777=5140+77140=177+6377=163+1463=414+714=27+0 所以 gcd (1694，917) = 7进行回代 7=63-414=63-4（77-63）= -477+563=-477+5（140-77） =5140-977 =5140-9（777-5140） =-9777+50140 =-9777+50（917-777） =50917-59777 =50917-59（1694-917） -591694+109917 即 7= u1694+v917 其中 u =-59， v = 1093. 同余定义2.1.3 假设a 和b是两个整数，m是一个正整数，如果m b a ，则称a 和b对模m同余。记作 a b (mod m )。例24 3和1对模2同余，4和1对模3同余，即3 1（mod 2）， 41（mod 3）定理2.1.4 同余的性质设a，b，c和m是整数，则有：i. a a（mod m）ii. 若a b（mod m），则b a（mod m）. 若a b（mod m），b c（mod m），则a c（mod m） 假设a和b被m除，获得整数商和余数，这个余数在0和m-1之间，即 a = q1m +r1和b = q2m +r2 ，0r1m-1 ，0r2m-1 。不难看出 ，a b（mod m），当且仅当r1 = r2 。我们使用符号a（mod m） 来表示a 被m除时的余数，即上面的r1 ，这样a b（mod m），当 且仅当a（mod m ）b（mod m）。如果我们用a（mod m）来代 替a ，我们说a是被模m约简的。 现在我们能够定义模m的算术：Zm是一个集合0，1，。，m- 1，它有两种运算+和 。在Zm中的加法和乘法，除了将结果被模 m约减外，恰好象实数加法和乘法。例 25 在Z2种作加法0+00（mod 2 ）,0+11(mod 2 ) ,1+01(mod 2 ) , 1+10(mod 2 ) 一般地，在Z2种的加法称为模2加，有时也称为比特异或，用记号 表示。 0 0 =0 ， 0 1 = 1 ， 1 0 = 1 ， 1 1 = 0例25 在Z16作乘法1113 1113=143=816+15 所以， 1113(mod16)=15 定义2.1.4 Euler函数是定义在整数上的函数，它在正整数m的值等 于1，2， ，m-1中与m互素的数的个数，记作（m）。例26 m = 6 , 1,2,3,4,5中与6互素的数为1，5，共有 两个，所以，（m）= （6）=2 定理2.1.5 设正整数的标准分解形式为m = ， 则 （m）= m（1-1/p1）（1-1/p2）（1-1/pn）例27 m=6 ，其标准分解形式为 6 = 23 所以， （6）= 6（1-1/2）（1-1/3）=2定理2.1.6（Euler定理） 若a和m互素，则a(m) 1(mod m)设f(x)表示多项式：anxn + an-1xn-1 + +a0 ,其中an 0 ， aiN(i=1,2,n)。设n是一个正整数，则f(x)= 0(mod m)称作模m的同余式，n称作同余式的次数，n = 1称为一次同余式，n = 2称为二次同余式。若a是使f(a)0(mod m)成立的一个整数，则x a (mod m) 叫 做同余式的一个解。 定理2.1.7 （中国剩余定理） 设m1，m2，mk，是k个两两互素 的整数，m= m1m1mk，Mi =m/mi ，i=1,2,k 。则同余方程组x b1(mod m1) , x b2(mod m2) , x bk(mod mk) 有解 x =(M1M1b1+ M2M2b2+MkMkbk)(mod m)其中 MiMi 1(mod mi) ,i=1,2,k由此定理可以看出，Mi可以利用前面介绍的Euclid算法求出。4）二次剩余 设gcd(a,m)=1，若同余式x2a(mod m)有解，则a称作模m的二次剩 余，否则称作模m的非二次剩余。 例29 考虑下列同余式x21(mod 5)，x22(mod 5)，x23(mod 5)，x24(mod 5)不难发现：x=1, x=4满足x21(mod 5)x=2, x=3满足x24(mod 5) 不存在整数x满足x22(mod 5)，x23(mod 5)所以1，4是模5的二次剩余，而2，3是模5的非二次剩余。定理2.1.8 若gcd(a,p)=1，则a是模p的二次剩余的充要条件为ap-1/21(mod p) a是模p的非二次剩余的充要条件为 ap-1/2-1(mod p)定理2.1.9 两个模p的二次剩余的乘积或两个模p的非二次剩余的乘 积，还是模p的二次剩余，一个模p的二次剩余与另一个模p的非二 次剩余的乘积是非二次剩余。定义2.1.5 Legendre符号（）是一个对于给定素数p定义在一切整数 a上的函数，它的值规定如下：例210 ， ， 定理2.1.10 legendre符号的性质a ) b ) 如果a b(mod p )，则c) d) e) 设p，q均为奇素数，pq，则定义2.1.6 设m = ei0是一个奇正整数，u是与m互素的整数，则 Jacobi符号定义为（u/m）= 其中（）是Legendre符号。定理2.1.11 Jacobi符号的性质1）（u/m）=(u-m)/m)2) (uv/m) = (u/m)(v/m)3) (u/mn) =(u/n)(u/m)4) (-1/m) = 1 当且仅当m = 1(mod 4)5) (2/m) = 1 当且仅当m = +1，-1(mod 8)6) 设m，n都是奇数，且gcd(m,n) = 1则=（-1）(m-1)(n-1)/422信息论基础Shannon信息论是密码学的理论基础，本节介绍Shannon信息论的基 本概念，与密码学有关的概念将在后面介绍。1熵的概念熵是信息的测度或不确定性，它是作为概率分布的一个函数来计算 的。假设有一个随机变量x，它根据概率分布p(x)在一个有限集合上 取值。根据分布p(x)发生的事件来获得的信息是什么？等价地，如 果一个事件还没有发生，有关这个结果的不确定性是多少？这个量 称为x的熵并用H(x)表示。定义2.2.1 离散随机变量x的熵H(x)定义为H(x) = -P(x) Log2P(x)其中，P(x)表示随机变量x的概率分布。例211 设离散随机变量x取0，1两个值，其中 P(x=0)=P(x=1)=1/2，则H(x) = -1 P(x=0)Log2P(x=0) - P(x=1)Log2P(x=1) = -1/2(-1) 1/2(-1) = 1下面我们来定义联合熵和条件熵。 定义2.2.2 两个离散随机变量（x,y）的联合熵定义为H(xy) = -1P(