数学基础第二章网络

数学基础第二章网络1第一页，共三十八页，编辑于2023年，星期三2.1数论基础数论是一个用数学方法研究证书性质的古老的数学分支，是近代密码学的重要理论基础之一。2第二页，共三十八页，编辑于2023年，星期三2.1.1因子约定：字母N表示全体自然数集合，Z表示全体整数集合，即

N={0，1，2，∙∙∙∙∙∙}Z={∙∙∙∙∙∙，-2，-1，0，1，2，∙∙∙∙∙∙}定义2.1.1设a,b∈Z，a≠0，k∈Z，使得b=ka，则称a整除b，并称a是b的因子或者约数，b是a的倍数，记为a|b。定义2.1.2设a,b,c∈Z，a，b不全为0，如果c|a且c|b，则称c为a和b的公因子。特别地，把a和b的所有公因子中最大的，称为a和b的最大公因子（GreatestCommonDivisors），记为gcd(a,b)或者(a,b)。3第三页，共三十八页，编辑于2023年，星期三定义2.1.3设a,b,c∈Z，如果a|c且b|c，c≥1，则称c为a和b的公倍数。特别地，把a和b的所有公倍数中最小的，称为a和b的最小公倍数，记作lcm(a,b)。可以证明a和b的最大公因子必然存在，且唯一；a和b的最小公倍数一定存在，且唯一。例如：gcd(12，60)=12，lcm(15，20，30)=60

4第四页，共三十八页，编辑于2023年，星期三2.1.2素数定义2.1.4整数p（>1）是素数（PrimeNumber），当且仅当p只有因子1和p，否则p为合数。例如：7=1×7，7没有1和7以外的因数，因此7是素数；

6=2×3，6有因数2和3，因此6是合数。从此定义可知，正整数集合可分为三类：素数、合数和1。定义2.1.5如果两个整数a和b有gcd(a,b)=1，则称a与b互素。1与任何整数互素。

5第五页，共三十八页，编辑于2023年，星期三定义2.1.6Euler（欧拉）函数是定义在正整数上的函数，它在正整数m的值等于1，2，...，i，...，m-1中与m互素的数的个数，记作φ(m)。例如m=6，{1，2，3，4，5}中与m互素的数为{1，5}，则有：φ(m)=φ(6)=2定理2.1.1设正整数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。6第六页，共三十八页，编辑于2023年，星期三定理2.1.2Euler（欧拉）定理若整数a和m互素，则

aφ(m)≡1(modm)例如a=3，m=10

由定理2.1.1，10=21×51，因此

φ(m)=φ(10)=10×(1-1/2)(1-1/5)=4

代入定理2.1.2公式中有：

aφ(m)=34=81≡1(mod10)≡1(modm)定理2.1.3（算术基本定理）任何一个整数m（>1）

，都存在唯一的因数分解形式：

m=p1e1p2e2……pnen

其中ei∈N，pi均为素数且p1<p2<……<pn，又称为m的标准分解形式。例如：6=21×31×50，20=22×30×51，

100=22×30×527第七页，共三十八页，编辑于2023年，星期三用算术基本定理求最大公因/倍数

依据算术基本定理，任何正整数可以分解成标准分解形式，从而可方便地求出两个正整数的最大公因数和最小公倍数。设a、b是两个正整数，且有标准分解形式：

a=p1e1p2e2……pnenei∈N b=p1f1p2f2……pnfnfi∈N

则

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=608第八页，共三十八页，编辑于2023年，星期三2.1.3Eulid（欧几里德）算法

利用算术基本定理可以求得两个正整数的最大公因子，但当两个正整数比较大时，求它们的标准分解式非常困难，因此求其最大公因子也变得非常困难，Eulid算法成为解决该问题的另一种简便方法。定理2.1.4（带余数除法）设a、b∈

N，其中b>0，则存在唯一的整数q和r，使得：

a=qb+r0≤r<b

成立。定理2.1.5设a、b∈

N，则存在两个整数v、u，使得：

ua+bv=gcd(a,b)9第九页，共三十八页，编辑于2023年，星期三定理2.1.6（Eulid算法）又称辗转除法，给定整数a和b且b>0，反复使用带余数除法，得等式如下：

a=bq1+r10<r1<b b=r1q2+r20<r2<r1 r1=r2q3+r30<r3<r2

… rn-2=rn-1qn+rn0<rn<rn-1 rn-1=rnqn+1+rn+1rn+1=0

则有： gcd(a,b)=rn重复使用带余数除法（即用每次的余数做除数去除上一次的除数）。每进行一次带余数除法，余数会递减，而b是有限的，因此经过一定次数的带余数除法，余数变为0。最后一个不为0的余数rn就是a和b的最大公因数。10第十页，共三十八页，编辑于2023年，星期三2.1数论基础 例：求gcd(1970，1066)=？

【解】用欧几里德算法的计算过程如下：

1970＝1×1066+904 1066＝1×904+162 904＝5×162+94 162＝1×94+68 94＝1×68+26 68＝2×26+16 26＝1×16+10 16＝1×10+6 10＝1×6+4

6＝1×4+2 4＝2×2+0

因此gcd(1970，1066)=211第十一页，共三十八页，编辑于2023年，星期三进行回代：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×197012第十二页，共三十八页，编辑于2023年，星期三将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表达。13第十三页，共三十八页，编辑于2023年，星期三2.1.4同余与模运算

1、同余定义2.1.7设a、b是两个整数，m是一个正整数，如果m|b-a，即b-a=km，则称a与b对模m同余，记作a≡b(modm)。 （即a和b对m具有相同的余数。令a=k1m+r，b=k2m+r b-a=k1m+r-(k2m+r)=(k1-k2)m=km)定理2.1.7同余性质 设a、b、c是整数，m是正整数，则有：（1）自反性，即a≡a(modm)；（2）对称性，即若a≡b(modm)，则b≡a(modm)；（3）传递性，即若a≡b(modm)，且b≡c(modm)，则a≡c(modm)；14第十四页，共三十八页，编辑于2023年，星期三2、模运算①我们用a(modm)表示a被m除的余数，即r=a(modm)，于是有：

a(modm)=b(modm)，表示为a≡b(modm)②求余运算a(modm)是将a映射到集合{0,1，…，m-1}中，即用a(modm)代替a。求余运算称为模运算。下面定义模m上的算术运算。Zm是一个集合{0，1，…，m-1}，其上有两种运算+和×。在Zm上的+和×类似于实数域上的加法和乘法，但要将结果映射到集合{0,1，…，m-1}上。例：在Z16上做算术运算11×13（1）先在实数域上做运算11×13=143=8×16+15；（2）将结果143映射到集合{0,1，…，15}上，即用143(mod16)=15代替143。 因此在Z16上，11×13=143(mod16)=15。15第十五页，共三十八页，编辑于2023年，星期三2.1.4中国剩余定理定义2.1.8若a、b都是整数，且m不能整除a，则称ax≡b(modm)为模m的一次同余方程。若x0是满足ax≡b(modm)的一个整数，即ax0≡b(modm)，则x0称为该同余方程的解。事实上，满足x≡x0(modm)的所有整数都满足ax≡b(modm)，因此同余方程的解通常写成x≡x0(modm)。16第十六页，共三十八页，编辑于2023年，星期三定理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。17第十七页，共三十八页，编辑于2023年，星期三【例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

18第十八页，共三十八页，编辑于2023年，星期三且有：即：

M1’M11(modm1)15M1’1(mod2)------①M2’M21(modm2)10M2’1(mod3)------②M3’M31(modm3)6M3’1(mod5)-------③由①、②、③可得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)#19第十九页，共三十八页，编辑于2023年，星期三【例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=3020第二十页，共三十八页，编辑于2023年，星期三且有：即：

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。下面求解M3’=？，M4’=？首先分析如下：由于M3=M/m3，所以M3与m3互素，即42与5互素，于是

gcd（42，5）=1依据定理2.1.5，存在两个整数M3’和v，使得

gcd（42，5）=1=42M3’+5v两边同时对模5做求余运算，即可得：

42M3’1(mod5)（同式③）21第二十一页，共三十八页，编辑于2023年，星期三由以上分析可知，必须求出gcd（42，5）的线性表达式42M3’+5v，即可得到M3’。根据Eulid算法，此处a=42，b=542=5×8+25=2×2+1

因此gcd（42，5）=1进行回代：

1=5-2×2=5-2×(42-5×8)=5-242=5-2×42+16×5=17×5-2×42即线性表达式为:1=17×5-2×4222第二十二页，共三十八页，编辑于2023年，星期三两边同时对模5做求余运算，得:(-2)×421(mod5)(5-2)×421(mod5)3×421(mod5)与③对照，可知M3’=323第二十三页，共三十八页，编辑于2023年，星期三同理由30*M4‘≡1（MOD7）得： 30=4*7+2 7=3*2+1 2=2*1+0 于是1=7-3*2=7-3*（30-4*7）=13*7-3*30 有30*（-3）≡1（MOD7）， 即4*30≡1（MOD7）故与④对照，M4’=424第二十四页，共三十八页，编辑于2023年，星期三将M3’=3和M4’=4代入xM1’M1b1+M2’M2b2+……+Mk’Mkbk(modM)1×105×0+1×70×0+3×42×1+4×30×6(mod210)846(mod210)6(mod210)#25第二十五页，共三十八页，编辑于2023年，星期三2.1.6二次剩余考虑以下同余式

x21(mod5)，x22(mod5)，

x23(mod5)，x24(mod5)不难发现：x=1，x=4满足x21(mod5) x=2，x=3满足x24(mod5)不存在整数x，满足x22(mod5)和x23(mod5)于是我们说1，4是模5的二次剩余，而2，3是模5的二次非剩余。定义2.1.9如果gcd(a,m)=1，即a和m互素，且x2≡a(modm)有解，则称a为模m的二次剩余，否则称a为模m的二次非剩余。26第二十六页，共三十八页，编辑于2023年，星期三例如，m=7，模m的完全剩余集合为{1,2,3,4,5,6}。x2≡1(mod7)有解：x=1，x=6；x2≡2(mod7)有解：x=3，x=4；x2≡3(mod7)无解；x2≡4(mod7)有解：x=2，x=5；x2≡5(mod7)无解；x2≡6(mod7)无解；27第二十七页，共三十八页，编辑于2023年，星期三可见1、2和4是模7的二次剩余，3、5和6是模7的二次非剩余。二次剩余具有以下性质：（1）如果m是素数，则整数1、2、3、…、m-1中正好有（m-1）/2个是模m的二次剩余，其余的（m-1）/2个是模m的二次非剩余。（2）如果a是模m的二次剩余，那么a恰好有两个解，其中一个在0~（m-1）/2之间；另一个在（m-1）/2~（m-1）之间。28第二十八页，共三十八页，编辑于2023年，星期三2.2信息论基础

2.2.1熵的概念随机事件：指事件发生的结果是随机的、不确定的。随机变量：取值为某随机事件发生的任一可能结果。概率分布：反映随机变量取随机事件可能结果的分布情况。熵：反映随机变量的不确定性。 熵是信息的数学测度或不确定性，它是以概率分布的一个函数来进行计算的。假设x为一随机变量，它根据概率分布P(x)在一个有限集合上取值，我们用熵表示随机变量x的不确定性，记为H(x)。

“不确定性”与“信息量”有着密切关系。如某事件发生的结果只有一种可能，则说明该事件是确定的。若事件发生的结果有k种可能，则事件是不确定的，且随着k的增加，不确定性增大，所包含的信息量越多。即随机变量x的可能取值越多（k越大），随机变量的不确定性越大，所含信息量就越大。29第二十九页，共三十八页，编辑于2023年，星期三定义2.2.1离散随机变量x的熵H(x)定义为：

H(x)=-

其中p(x)表示随机变量x的概率分布。 例如，随机变量x取{0，1}两个值（即随机事件可发生两种结果），其中P(x=0)=P(x=1)=1/2，则H(x)=-P(x=0)log2P(x=0)-P(x=1)log2P(x=1)=1/2*(-1)-1/2*(-1)=1

当k=1（确定事件）时，H(x)=0；定义2.2.2两个离散随机变量(x,y)的联合熵H(x)定义为：

H(xy)=-

其中p(xy)表示随机变量(x,y)的联合概率分布。定义2.2.3两个离散随机变量(x,y)的条件熵H(x)定义为：

H(x|y)=-

其中p(xy)表示随机变量(x,y)的联合概率分布，p(x|y)表示随机变量(x,y)的条件概率分布。定理2.2.1离散随机变量x的熵H(x)定义为：

H(xy)=H(x)+H(y|x)30第三十页，共三十八页，编辑于2023年，星期三2.2.2互信息

互信息是一个事件包含另一个事件的信息的度量，或者是已知另外一事件（称作B）的情况下，事件（称作A）不确定性的减少。定义2.2.4两个离散随机变量x和y，它们具有概率分布p(x)和p(y)及联合概率p(xy)，则互信息定义为：

I(x;y)=

如果随机变量x和y统计独立，p(xy)=p(x)p(y)，则I(x;y)=0，即y不含x的任何信息。定理2.2.2互信息具有对称性，即

I(x;y)=H(x)-H(x|y) =H(y)-H(y|x)=I(y;x)31第三十一页，共三十八页，编辑于2023年，星期三2.3计算复杂性简介

计算复杂性理论给出了求解一个问题的计算是“容易”的还是“困难”的，它有助于确定一个密码算法的安全强度，即破译一个密码算法所花费的时间或者空间代价的大小。从理论上讨论什么样的问题可由计算机来完成，理论上可计算的问题实际上是否可行等，均属于计算复杂性理论研究范畴。计算机复杂性理论涉及算法的复杂性和问题的复杂性。1、算法复杂性计算复杂性表示解决问题的算法所需要的时间与空间资源的多少。通常算法所需的时间和空间往往取决于问题的输入规模n。如问题的输入规模为n，如果复杂性为O(nt)(t为常数)，则称该算法是多项式时间算法的；如果算法复杂性为O(tf(n))(为t>1的常数)，则称该算法是指数时间算法。2、问题的复杂性计算复杂性理论按照解决问题的算法对问题进行分类。能够用多项式时间算法解决的问题称之为易解的；不能在多项式时间内解决的问题称之为难解的。32第三十二页，共三十八页，编辑于2023年，星期三定义2.3.1P类问题：在多项式时间内可以完成的问题；

NP类问题：在多项式时间内可以验证的问题；在NP类问题中，有一类问题称为NP完全类问题(记为NPC)，所有NP类问题都可以转换为NP完全类问题。因此NP完全类问题只要有一个问题有多项式求解算法，则整个NP类问题都属于P类问题（即可在多项式时间内完成）。把P类问题称为易解问题，NP类问题称为难解问题。由于NP完全类问题(N