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

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

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的因子或者約數(shù)，b是a的倍數(shù)，記為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的公倍數(shù)。特別地，把a和b的所有公倍數(shù)中最小的，稱為a和b的最小公倍數(shù)，記作lcm(a,b)。可以證明a和b的最大公因子必然存在，且唯一；a和b的最小公倍數(shù)一定存在，且唯一。例如：gcd(12，60)=12，lcm(15，20，30)=60

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

6=2×3，6有因數(shù)2和3，因此6是合數(shù)。從此定義可知，正整數(shù)集合可分為三類：素數(shù)、合數(shù)和1。定義2.1.5如果兩個整數(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ù)的個數(shù)，記作φ(m)。例如m=6，{1，2，3，4，5}中與m互素的數(shù)為{1，5}，則有：φ(m)=φ(6)=2定理2.1.1設正整數(shù)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（歐拉）定理若整數(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ù)基本定理）任何一個整數(shù)m（>1）

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

m=p1e1p2e2……pnen

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

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

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

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ù)基本定理可以求得兩個正整數(shù)的最大公因子，但當兩個正整數(shù)比較大時，求它們的標準分解式非常困難，因此求其最大公因子也變得非常困難，Eulid算法成為解決該問題的另一種簡便方法。定理2.1.4（帶余數(shù)除法）設a、b∈

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

a=qb+r0≤r<b

成立。定理2.1.5設a、b∈

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

ua+bv=gcd(a,b)9第九頁，共三十八頁，編輯于2023年，星期三定理2.1.6（Eulid算法）又稱輾轉(zhuǎn)除法，給定整數(shù)a和b且b>0，反復使用帶余數(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重復使用帶余數(shù)除法（即用每次的余數(shù)做除數(shù)去除上一次的除數(shù)）。每進行一次帶余數(shù)除法，余數(shù)會遞減，而b是有限的，因此經(jīng)過一定次數(shù)的帶余數(shù)除法，余數(shù)變?yōu)?。最后一個不為0的余數(shù)rn就是a和b的最大公因數(shù)。10第十頁，共三十八頁，編輯于2023年，星期三2.1數(shù)論基礎(chǔ) 例：求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是兩個整數(shù)，m是一個正整數(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ì) 設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、模運算①我們用a(modm)表示a被m除的余數(shù)，即r=a(modm)，于是有：

a(modm)=b(modm)，表示為a≡b(modm)②求余運算a(modm)是將a映射到集合{0,1，…，m-1}中，即用a(modm)代替a。求余運算稱為模運算。下面定義模m上的算術(shù)運算。Zm是一個集合{0，1，…，m-1}，其上有兩種運算+和×。在Zm上的+和×類似于實數(shù)域上的加法和乘法，但要將結(jié)果映射到集合{0,1，…，m-1}上。例：在Z16上做算術(shù)運算11×13（1）先在實數(shù)域上做運算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)的一個整數(shù)，即ax0≡b(modm)，則x0稱為該同余方程的解。事實上，滿足x≡x0(modm)的所有整數(shù)都滿足ax≡b(modm)，因此同余方程的解通常寫成x≡x0(modm)。16第十六頁，共三十八頁，編輯于2023年，星期三定理2.1.7（中國剩余定理）設m1,m2,…,mk是k個兩兩互素的正整數(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)------①M2’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)------①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依據(jù)定理2.1.5，存在兩個整數(shù)M3’和v，使得

gcd（42，5）=1=42M3’+5v兩邊同時對模5做求余運算，即可得：

42M3’1(mod5)（同式③）21第二十一頁，共三十八頁，編輯于2023年，星期三由以上分析可知，必須求出gcd（42，5）的線性表達式42M3’+5v，即可得到M3’。根據(jù)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)不難發(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是素數(shù)，則整數(shù)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信息論基礎(chǔ)

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

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

H(x)=-

其中p(x)表示隨機變量x的概率分布。 例如，隨機變量x取{0，1}兩個值（即隨機事件可發(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

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

H(xy)=-

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

H(x|y)=-

其中p(xy)表示隨機變量(x,y)的聯(lián)合概率分布，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)及聯(lián)合概率p(xy)，則互信息定義為：

I(x;y)=

如果隨機變量x和y統(tǒng)計獨立，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、算法復雜性計算復雜性表示解決問題的算法所需要的時間與空間資源的多少。通常算法所需的時間和空間往往取決于問題的輸入規(guī)模n。如問題的輸入規(guī)模為n，如果復雜性為O(nt)(t為常數(shù))，則稱該算法是多項式時間算法的；如果算法復雜性為O(tf(n))(為t>1的常數(shù))，則稱該算法是指數(shù)時間算法。2、問題的復雜性計算復雜性理論按照解決問題的算法對問題進行分類。能夠用多項式時間算法解決的問題稱之為易解的；不能在多項式時間內(nèi)解決的問題稱之為難解的。32第三十二頁，共三十八頁，編輯于2023年，星期三定義2.3.1P類問題：在多項式時間內(nèi)可以完成的問題；

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