安全与保密课件

1第二章数学基础（3学时）一.基本要求与基本知识点（1）掌握数论的有关基本定义、Euclid算法、同余概念及二次剩余概念；（2）掌握熵和互信息的概念；（3）了解三个NP-完全问题。二.教学重点与难点（1）数论的有关基本定义和定理；（2）信息论的有关定义和定理。数论、信息论和算法复杂性理论是近代密码学的理论基础，本章给出简单介绍。22.1数论基础2.1.1引言约定：字母N表示全体自然数集合，Z表示全体整数集合，即N={0，1，2，∙∙∙∙∙∙}Z={∙∙∙∙∙∙，-2，-1，0，1，2，∙∙∙∙∙∙}定义2.1.1如果存在一个整数kZ，使得n=kd，则称d整除n，记作d|n，其中d称作n的因数（Divisors），n称作d的倍数。如果不存在这样一个整数kZ使得n=kd，则称d不整除n，记作d+n。（1）若a、b、c均为整数，若c|a且c|b，则称c是a和b的公因数。把a和b的所有公因数中最大的，称为a和b的最大公因数（GreatestCommonDivisors），记作gcd(a,b)。（2）若a、b、c均为整数，若a|c且b|c，则称c是a和b的公倍数。把a和b的所有公倍数中最小的，称为a和b的最小公倍数，记作lcm(a,b)。例如：gcd(12，60)=12，lcm(15，20，30)=6032.1数论基础定义2.1.2整数p(1)称为素数（PrimeNumber），如果除1和其本身除外，p没有任何其它因数。不是素数的整数称为合数。例如：7=1×7，7没有1和7以外的因数，因此7是素数；6=2×3，6有因数2和3，因此6是合数。从此定义可知，正整数集合可分为三类：素数、合数和1。定理2.1.1（算术基本定理）任何一个正整数m，都存在唯一的因数分解形式：m=p1e1p2e2……pnen其中eiN，pi是素数且p1p2……pn，又称为m的标准分解形式。例如：6=21×31×50，20=22×30×51，100=22×30×5242.1数论基础依据算术基本定理，任何整数可以分解成标准形式，从而可方便地求出两个整数的最大公因数和最小公倍数。设a、b是两个正整数，且有标准分解形式：a=p1e1p2e2……pneneiNb=p1f1p2f2……pnfnfiN则gcd(a,b)=，lcm(a,b)=其中min{x,y}表示x，y中最小者；max{x,y}表示x，y中最大者。例如：gcd(6，20)=2min{1,2}∙3min{1,0}∙5min{0,1}=21∙30∙50=2，lcm(6，20)=2max{1,2}∙3max{1,0}∙5max{0,1}=22∙31∙51=60},min{1fieiniip},max{1fieiniip52.1数论基础2.1.2Eulid（欧几里德）算法利用算术基本定理可以求得两个整数的最大公因数，但当两个整数比较大时，求它们的标准分解形式非常困难，因此求其最大公因数也变得非常困难，Eulid算法成为解决该问题的另一方法。定理2.1.2（带余数除法）设a、bN，其中b0，则存在两个整数q、r使得：a=bq+r0≤rb成立，其中q和r唯一确定。定理2.1.3设a、bN，则存在两个整数v、u，使得：ua+bv=gcd(a,b)定理2.1.4（Eulid算法）又称辗转除法，由定理2.1.2，得以下等式：a=bq1+r10r1bb=r1q2+r20r2r1r1=r2q3+r30r3r2…rn-2=rn-1qn+rn0rnrn-1rn-1=rnqn+1+rn+1rn+1=0则有：gcd(a,b)=rn62.1数论基础重复使用带余数除法（即每次的余数为除数去除上一次的除数）。每进行一次带余数除法，余数会递减，而b是有限的，因此经过一定次数的带余数除法，余数变为0。最后一个不为0的余数rn就是a和b的最大公因数。例：求gcd(1970，1066)=？【解】用欧几里德算法的计算过程如下：1970＝1×1066+9041066＝1×904+162904＝5×162+94162=1×94+6894＝1×68+2668＝2×26+1626＝1×16+1016＝1×10+610＝1×6+46=1×4+24＝2×2+0因此gcd(1970，1066)=272.1数论基础进行回代：2=6-1×4=6-1×(10-1×6)=6-10+1×6=2×6-10=2×(16-1×10)-10=2×16-2×10-10=2×16-3×10=2×16-3×(26-1×16)=2×16-3×26+3×16=5×16-3×26=5×(68-2×26)-3×26=5×68-10×26-3×26=5×68-13×26=5×68-13×(94-1×68)=5×68-13×94+13×68=18×68-13×94=18×(162-1×94)-13×94=18×162-18×94-13×94=18×162-31×94=18×162-31×(904-5×162)=18×162-31×904+155×162=173×162-31×904=173×(1066-1×904)-31×904=173×1066-173×904-31×904=173×1066-204×904=173×1066-204×(1970-1×1066)=173×1066-204×1970+204×1066=377×1066-204×1970故：2=377×1066-204×1970与定理2.1.3中ua+bv=gcd(a,b)相对应，a=1970，b=1066，u=-204，v=377由此可见，gcd(a,b)可以以线性形式ua+bv表达。82.1数论基础2.1.3同余定义2.1.3设a、b是两个整数，m是一个正整数，如果m|b-a，即b-a=km，则称a与b对模m同余（Congruence），记作ab(modm)。（即a和b对m具有相同的余数。令a=k1m+rb=k2m+rb-a=k1m+r-(k2m+r)=(k1-k2)m=km)定理2.1.5同余性质设a、b、c是整数，m是正整数，则有：（1）自反的，即aa(modm)；（2）对称的，即若ab(modm)，则ba(modm)；（3）传递的，即若ab(modm)，bc(modm)，则ac(modm)；92.1数论基础①我们用a(modm)表示a被m除的余数，即r=a(modm)，则有：a(modm)=b(modm)，表示为ab(modm)②如果用a(modm)代替a，就说a被模m约简。下面以约简的概念来定义模m的算术运算：Zm是一个集合{0，1，…，m-1}，其上有两种运算+和×。在Zm的+和×如同实数的加法和乘法，但要将结果被模m约简。例：在Z16上做算术运算11×13实数运算11×13=143=8×16+15，被模16约简后结果为15，因此在Z16上，11×13=15。定义2.1.4如果对两个整数a和b有gcd(a,b)=1，则称a与b互素。1与任何整数互素。定义2.1.5Euler（欧拉）函数是定义在正整数上的函数，它在正整数m的值等于1，2，...，i，...，m-1中与m互素的数的个数记作φ(m)。例如m=6，{1，2，3，4，5}中与m互素的数为{1，5}，则有：φ(m)=φ(6)=2102.1数论基础定理2.1.6设正整数m的标准分解形式为：m=p1e1p2e2……pnen则φ(m)=m(1-1/p1)(1-1/p2)…(1-1/pn)例如m=6，其标准分解形式为6=21×31因此，φ(m)=φ(6)=6×(1-1/2)(1-1/3)=2。定理2.1.7Euler（欧拉）定理若整数a和m互素，则aφ(m)1(modm)例如a=3，m=10由定理2.1.6，10=21×51，因此，φ(m)=φ(10)=10×(1-1/2)(1-1/5)=4代入定理2.1.7公式中有：aφ(m)=34=811(mod10)1(modm)112.1数论基础2.1.4中国剩余定理设f(x)=anxn+an-1xn-1+…+a1x+a0，an≠0，aiN(i=1,2,…,n)，若m是一个正整数，则f(x)0(modm)(1)称作为模m的同余式，n称为同余式的次数，n=1时称为一次同余式，n=2时称为二次同余式。若a是使f(a)0(modm)成立的一个整数，则a叫做同余式（1）的解。事实上，满足xa(modm)的所有整数都使同余式（1）成立，因此同余式（1）的解通常写成xa(modm)。122.1数论基础定理2.1.7（中国剩余定理）设m1,m2,…,mk是k个两两互素的正整数，m=m1m2…mk，Mi=m/mi，i=1,2,…k，则同余方程组：xb1(modm1)，xb2(modm2)，……，xbk(modmk)有解：XM1’M1b1+M2’M2b2+……+Mk’Mkbk(modm)其中Mi’Mi1(modmi)，i=1,2,……,k。中国剩余定理是数论中最有用的定理之一，定理说明了某一范围的整数可通过它对两两互素的整数（如mi）取模所得余数来重构。例如Z10（共10个数，0，1，…，9）中的每个数，可通过它们对2和5（10的素因子，即10=2x5）取模所得的两个余数来重构。假设已知十进制数x的余数为0和3，即x(mod2)=0且x(mod5)=3，则可得到x是Z10中的偶数，且被5除后余数是3，因此8是满足这一关系的唯一x。132.1数论基础【例1】求解x1(mod2)x2(mod3)x3(mod5)【解】由已知条件：b1=1，b2=2，b3=3，m1=2，m2=3，m3=5依中国剩余定理：m=m1m2m3=2×3×5=30M1=m/m1=30/2=15，M2=m/m2=30/3=10，M3=m/m3=30/5=6且有：即：M1’M11(modm1)15M1’1(mod2)------①M2’M21(modm2)10M2’1(mod3)------②M3’M31(modm3)6M3’1(mod5)-------③142.1数论基础由①、②、③可得M1’=1，M2’=1，M3’=1，将以上参数代入XM1’M1b1+M2’M2b2+……+Mk’Mkbk(modm)1×15×1+1×10×2+1×6×3(mod30)53(mod30)23(mod30)#152.1数论基础【例2】求解x0(mod2)x0(mod3)x1(mod5)x6(mod7)【解】由已知条件：b1=0，b2=0，b3=1，b4=6m1=2，m2=3，m3=5，m4=7依中国剩余定理：m=m1m2m3m4=2×3×5×7=210M1=m/m1=210/2=105，M2=m/m2=210/3=70，M3=m/m3=210/5=42，M4=m/m4=210/7=30且有：即：M1’M11(modm1)105M1’1(mod2)------①M2’M21(modm2)70M2’1(mod3)------②M3’M31(modm3)42M3’1(mod5)------③M4’M41(modm4)30M4’1(mod7)------④由①、②可得M1’=1，M2’=1。162.1数论基础下面求解M3’=？，M4’=？首先分析如下：由于M3=m/m3，所以M3与m3互素，即42与5互素，于是gcd（42，5）=1依据定理2.1.3，存在两个整数M3’和v，使得gcd（42，5）=1=42M3’+5v两边同时对模5做求余运算，即可得：42M3’1(mod5)（同式③）由以上分析可知，必须求出gcd（42，5）的线性表达式42M3’+5v，即可得到M3’。根据Eulid算法，此处a=42，b=542=5×8+25=2×2+1因此gcd（42，5）=1172.1数论基础进行回代：1=5-2×2=5-2×(42-5×8)=5-242=5-2×42+16×5=17×5-2×42即线性表达式为:1