數(shù)學(xué)基礎(chǔ)第二章網(wǎng)絡(luò)

數(shù)學(xué)基礎(chǔ)第二章網(wǎng)絡(luò)1第一頁，共三十八頁，編輯于2023年，星期三2.1數(shù)論基礎(chǔ)數(shù)論是一個(gè)用數(shù)學(xué)方法研究證書性質(zhì)的古老的數(shù)學(xué)分支，是近代密碼學(xué)的重要理論基礎(chǔ)之一。2第二頁，共三十八頁，編輯于2023年，星期三2.1.1因子約定：字母N表示全體自然數(shù)集合，Z表示全體整數(shù)集合，即

N={0，1，2，??????}Z={??????，-2，-1，0，1，2，??????}定義2.1.1設(shè)a,b∈Z，a≠0，k∈Z，使得b=ka，則稱a整除b，并稱a是b的因子或者約數(shù)，b是a的倍數(shù)，記為a|b。定義2.1.2設(shè)a,b,c∈Z，a，b不全為0，如果c|a且c|b，則稱c為a和b的公因子。特別地，把a(bǔ)和b的所有公因子中最大的，稱為a和b的最大公因子（GreatestCommonDivisors），記為gcd(a,b)或者(a,b)。3第三頁，共三十八頁，編輯于2023年，星期三定義2.1.3設(shè)a,b,c∈Z，如果a|c且b|c，c≥1，則稱c為a和b的公倍數(shù)。特別地，把a(bǔ)和b的所有公倍數(shù)中最小的，稱為a和b的最小公倍數(shù)，記作lcm(a,b)?？梢宰C明a和b的最大公因子必然存在，且唯一；a和b的最小公倍數(shù)一定存在，且唯一。例如：gcd(12，60)=12，lcm(15，20，30)=60

4第四頁，共三十八頁，編輯于2023年，星期三2.1.2素?cái)?shù)定義2.1.4整數(shù)p（>1）是素?cái)?shù)（PrimeNumber），當(dāng)且僅當(dāng)p只有因子1和p，否則p為合數(shù)。例如：7=1×7，7沒有1和7以外的因數(shù)，因此7是素?cái)?shù)；

6=2×3，6有因數(shù)2和3，因此6是合數(shù)。從此定義可知，正整數(shù)集合可分為三類：素?cái)?shù)、合數(shù)和1。定義2.1.5如果兩個(gè)整數(shù)a和b有g(shù)cd(a,b)=1，則稱a與b互素。1與任何整數(shù)互素。

5第五頁，共三十八頁，編輯于2023年，星期三定義2.1.6Euler（歐拉）函數(shù)是定義在正整數(shù)上的函數(shù)，它在正整數(shù)m的值等于1，2，...，i，...，m-1中與m互素的數(shù)的個(gè)數(shù)，記作φ(m)。例如m=6，{1，2，3，4，5}中與m互素的數(shù)為{1，5}，則有：φ(m)=φ(6)=2定理2.1.1設(shè)正整數(shù)m的標(biāo)準(zhǔn)分解形式為：

m=p1e1p2e2……pnen

則

φ(m)=m(1-1/p1)(1-1/p2)…(1-1/pn)例如m=6，其標(biāo)準(zhǔn)分解形式為6=21×31

因此，φ(m)=φ(6)=6×(1-1/2)(1-1/3)=2。6第六頁，共三十八頁，編輯于2023年，星期三定理2.1.2Euler（歐拉）定理若整數(shù)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（算術(shù)基本定理）任何一個(gè)整數(shù)m（>1）

，都存在唯一的因數(shù)分解形式：

m=p1e1p2e2……pnen

其中ei∈N，pi均為素?cái)?shù)且p1<p2<……<pn，又稱為m的標(biāo)準(zhǔn)分解形式。例如：6=21×31×50，20=22×30×51，

100=22×30×527第七頁，共三十八頁，編輯于2023年，星期三用算術(shù)基本定理求最大公因/倍數(shù)

依據(jù)算術(shù)基本定理，任何正整數(shù)可以分解成標(biāo)準(zhǔn)分解形式，從而可方便地求出兩個(gè)正整數(shù)的最大公因數(shù)和最小公倍數(shù)。設(shè)a、b是兩個(gè)正整數(shù)，且有標(biāo)準(zhǔn)分解形式：

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（歐幾里德）算法

利用算術(shù)基本定理可以求得兩個(gè)正整數(shù)的最大公因子，但當(dāng)兩個(gè)正整數(shù)比較大時(shí)，求它們的標(biāo)準(zhǔn)分解式非常困難，因此求其最大公因子也變得非常困難，Eulid算法成為解決該問題的另一種簡便方法。定理2.1.4（帶余數(shù)除法）設(shè)a、b∈

N，其中b>0，則存在唯一的整數(shù)q和r，使得：

a=qb+r0≤r<b

成立。定理2.1.5設(shè)a、b∈

N，則存在兩個(gè)整數(shù)v、u，使得：

ua+bv=gcd(a,b)9第九頁，共三十八頁，編輯于2023年，星期三定理2.1.6（Eulid算法）又稱輾轉(zhuǎn)除法，給定整數(shù)a和b且b>0，反復(fù)使用帶余數(shù)除法，得等式如下：

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重復(fù)使用帶余數(shù)除法（即用每次的余數(shù)做除數(shù)去除上一次的除數(shù)）。每進(jìn)行一次帶余數(shù)除法，余數(shù)會遞減，而b是有限的，因此經(jīng)過一定次數(shù)的帶余數(shù)除法，余數(shù)變?yōu)?。最后一個(gè)不為0的余數(shù)rn就是a和b的最大公因數(shù)。10第十頁，共三十八頁，編輯于2023年，星期三2.1數(shù)論基礎(chǔ) 例：求gcd(1970，1066)=？

【解】用歐幾里德算法的計(jì)算過程如下：

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年，星期三進(jìn)行回代：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)相對應(yīng)：

a=1970，b=1066，

u=-204，v=377由此可見，gcd(a,b)可以以線性形式ua+bv表達(dá)。13第十三頁，共三十八頁，編輯于2023年，星期三2.1.4同余與模運(yùn)算

1、同余定義2.1.7設(shè)a、b是兩個(gè)整數(shù)，m是一個(gè)正整數(shù)，如果m|b-a，即b-a=km，則稱a與b對模m同余，記作a≡b(modm)。 （即a和b對m具有相同的余數(shù)。令a=k1m+r，b=k2m+r b-a=k1m+r-(k2m+r)=(k1-k2)m=km)定理2.1.7同余性質(zhì) 設(shè)a、b、c是整數(shù)，m是正整數(shù)，則有：（1）自反性，即a≡a(modm)；（2）對稱性，即若a≡b(modm)，則b≡a(modm)；（3）傳遞性，即若a≡b(modm)，且b≡c(modm)，則a≡c(modm)；14第十四頁，共三十八頁，編輯于2023年，星期三2、模運(yùn)算①我們用a(modm)表示a被m除的余數(shù)，即r=a(modm)，于是有：

a(modm)=b(modm)，表示為a≡b(modm)②求余運(yùn)算a(modm)是將a映射到集合{0,1，…，m-1}中，即用a(modm)代替a。求余運(yùn)算稱為模運(yùn)算。下面定義模m上的算術(shù)運(yùn)算。Zm是一個(gè)集合{0，1，…，m-1}，其上有兩種運(yùn)算+和×。在Zm上的+和×類似于實(shí)數(shù)域上的加法和乘法，但要將結(jié)果映射到集合{0,1，…，m-1}上。例：在Z16上做算術(shù)運(yùn)算11×13（1）先在實(shí)數(shù)域上做運(yùn)算11×13=143=8×16+15；（2）將結(jié)果143映射到集合{0,1，…，15}上，即用143(mod16)=15代替143。 因此在Z16上，11×13=143(mod16)=15。15第十五頁，共三十八頁，編輯于2023年，星期三2.1.4中國剩余定理定義2.1.8若a、b都是整數(shù)，且m不能整除a，則稱ax≡b(modm)為模m的一次同余方程。若x0是滿足ax≡b(modm)的一個(gè)整數(shù)，即ax0≡b(modm)，則x0稱為該同余方程的解。事實(shí)上，滿足x≡x0(modm)的所有整數(shù)都滿足ax≡b(modm)，因此同余方程的解通常寫成x≡x0(modm)。16第十六頁，共三十八頁，編輯于2023年，星期三定理2.1.7（中國剩余定理）設(shè)m1,m2,…,mk是k個(gè)兩兩互素的正整數(shù)，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)------①M(fèi)2’M21(modm2)10M2’1(mod3)------②M3’M31(modm3)6M3’1(mod5)-------③由①、②、③可得M1’=1，M2’=1，M3’=1，將以上參數(shù)代入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)------①M(fèi)2’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依據(jù)定理2.1.5，存在兩個(gè)整數(shù)M3’和v，使得

gcd（42，5）=1=42M3’+5v兩邊同時(shí)對模5做求余運(yùn)算，即可得：

42M3’1(mod5)（同式③）21第二十一頁，共三十八頁，編輯于2023年，星期三由以上分析可知，必須求出gcd（42，5）的線性表達(dá)式42M3’+5v，即可得到M3’。根據(jù)Eulid算法，此處a=42，b=542=5×8+25=2×2+1

因此gcd（42，5）=1進(jìn)行回代：

1=5-2×2=5-2×(42-5×8)=5-242=5-2×42+16×5=17×5-2×42即線性表達(dá)式為:1=17×5-2×4222第二十二頁，共三十八頁，編輯于2023年，星期三兩邊同時(shí)對模5做求余運(yùn)算，得:(-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)不難發(fā)現(xiàn)：x=1，x=4滿足x21(mod5) x=2，x=3滿足x24(mod5)不存在整數(shù)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的二次非剩余。二次剩余具有以下性質(zhì)：（1）如果m是素?cái)?shù)，則整數(shù)1、2、3、…、m-1中正好有（m-1）/2個(gè)是模m的二次剩余，其余的（m-1）/2個(gè)是模m的二次非剩余。（2）如果a是模m的二次剩余，那么a恰好有兩個(gè)解，其中一個(gè)在0~（m-1）/2之間；另一個(gè)在（m-1）/2~（m-1）之間。28第二十八頁，共三十八頁，編輯于2023年，星期三2.2信息論基礎(chǔ)

2.2.1熵的概念隨機(jī)事件：指事件發(fā)生的結(jié)果是隨機(jī)的、不確定的。隨機(jī)變量：取值為某隨機(jī)事件發(fā)生的任一可能結(jié)果。概率分布：反映隨機(jī)變量取隨機(jī)事件可能結(jié)果的分布情況。熵：反映隨機(jī)變量的不確定性。 熵是信息的數(shù)學(xué)測度或不確定性，它是以概率分布的一個(gè)函數(shù)來進(jìn)行計(jì)算的。假設(shè)x為一隨機(jī)變量，它根據(jù)概率分布P(x)在一個(gè)有限集合上取值，我們用熵表示隨機(jī)變量x的不確定性，記為H(x)。

“不確定性”與“信息量”有著密切關(guān)系。如某事件發(fā)生的結(jié)果只有一種可能，則說明該事件是確定的。若事件發(fā)生的結(jié)果有k種可能，則事件是不確定的，且隨著k的增加，不確定性增大，所包含的信息量越多。即隨機(jī)變量x的可能取值越多（k越大），隨機(jī)變量的不確定性越大，所含信息量就越大。29第二十九頁，共三十八頁，編輯于2023年，星期三定義2.2.1離散隨機(jī)變量x的熵H(x)定義為：

H(x)=-

其中p(x)表示隨機(jī)變量x的概率分布。 例如，隨機(jī)變量x取{0，1}兩個(gè)值（即隨機(jī)事件可發(fā)生兩種結(jié)果），其中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

當(dāng)k=1（確定事件）時(shí)，H(x)=0；定義2.2.2兩個(gè)離散隨機(jī)變量(x,y)的聯(lián)合熵H(x)定義為：

H(xy)=-

其中p(xy)表示隨機(jī)變量(x,y)的聯(lián)合概率分布。定義2.2.3兩個(gè)離散隨機(jī)變量(x,y)的條件熵H(x)定義為：

H(x|y)=-

其中p(xy)表示隨機(jī)變量(x,y)的聯(lián)合概率分布，p(x|y)表示隨機(jī)變量(x,y)的條件概率分布。定理2.2.1離散隨機(jī)變量x的熵H(x)定義為：

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

互信息是一個(gè)事件包含另一個(gè)事件的信息的度量，或者是已知另外一事件（稱作B）的情況下，事件（稱作A）不確定性的減少。定義2.2.4兩個(gè)離散隨機(jī)變量x和y，它們具有概率分布p(x)和p(y)及聯(lián)合概率p(xy)，則互信息定義為：

I(x;y)=

如果隨機(jī)變量x和y統(tǒng)計(jì)獨(dú)立，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計(jì)算復(fù)雜性簡介

計(jì)算復(fù)雜性理論給出了求解一個(gè)問題的計(jì)算是“容易”的還是“困難”的，它有助于確定一個(gè)密碼算法的安全強(qiáng)度，即破譯一個(gè)密碼算法所花費(fèi)的時(shí)間或者空間代價(jià)的大小。從理論上討論什么樣的問題可由計(jì)算機(jī)來完成，理論上可計(jì)算的問題實(shí)際上是否可行等，均屬于計(jì)算復(fù)雜性理論研究范疇。計(jì)算機(jī)復(fù)雜性理論涉及算法的復(fù)雜性和問題的復(fù)雜性。1、算法復(fù)雜性計(jì)算復(fù)雜性表示解決問題的算法所需要的時(shí)間與空間資源的多少。通常算法所需的時(shí)間和空間往往取決于問題的輸入規(guī)模n。如問題的輸入規(guī)模為n，如果復(fù)雜性為O(nt)(t為常數(shù))，則稱該算法是多項(xiàng)式時(shí)間算法的；如果算法復(fù)雜性為O(tf(n))(為t>1的常數(shù))，則稱該算法是指數(shù)時(shí)間算法。2、問題的復(fù)雜性計(jì)算復(fù)雜性理論按照解決問題的算法對問題進(jìn)行分類。能夠用多項(xiàng)式時(shí)間算法解決的問題稱之為易解的；不能在多項(xiàng)式時(shí)間內(nèi)解決的問題稱之為難解的。32第三十二頁，共三十八頁，編輯于2023年，星期三定義2.3.1P類問題：在多項(xiàng)式時(shí)間內(nèi)可以完成的問題；

NP類問題：在多項(xiàng)式時(shí)間內(nèi)可以驗(yàn)證的問題；在NP類問題中，有一類問題稱為NP完全類問題(記為NPC)，所有NP類問題都可以轉(zhuǎn)換為NP完全類問題。因此NP完全類問題只要有一個(gè)問題有多項(xiàng)式求解算法，則整個(gè)NP類問題都屬于P類問題（即可在多項(xiàng)式時(shí)間內(nèi)完成）。把P類問題稱為易解問題，NP類問題稱為難解問題。由于NP完全類問題(N