第2章信息論與數(shù)學基礎(chǔ)

統(tǒng)計機器學習與數(shù)據(jù)挖掘技術(shù)與方法研討班講義第2章信息論與數(shù)學基礎(chǔ)

統(tǒng)計機器學習與數(shù)據(jù)挖掘技術(shù)與方法研1信息論Shannon與20世紀40年代提出信息是個很抽象的概念。我們常常說信息很多，或者信息較少，但卻很難說清楚信息到底有多少。比如一本五十萬字的中文書到底有多少信息量。直到1948年，香農(nóng)提出了“信息熵”的概念，才解決了對信息的量化問題。信息論Shannon與20世紀40年代提出2信息量與不確定性

一條信息的信息量大小和它的不確定性有直接的關(guān)系。比如說，要搞清楚一件非常不確定的事，或是我們一無所知的事情，就需要了解大量的信息。相反，如果我們對某件事已經(jīng)有了較多的了解，則不需要太多的信息就能把它搞清楚。從這個角度可認為，信息量的度量就等于不確定性的多少。例子：冠軍隊預測信息量與不確定性3熵（Entropy）的定義：設隨機變量X，取值空間Ω，Ω為有限集合。X的分布密度為p(x)，p(x)=P(X=x)x∈X，則該隨機變量的取值不確定程度，即其熵為：當使用log2時，熵的單位為比特反映一個信源發(fā)出不同信號，具有的平均信息量。熵（Entropy）的定義：4chp2-信息論與數(shù)學基礎(chǔ)課件5chp2-信息論與數(shù)學基礎(chǔ)課件6chp2-信息論與數(shù)學基礎(chǔ)課件7熵率（語言信息率）

：：

r=H(M)/N語言絕對信息率：R=log2L語言多余度：D=R-r熵率（語言信息率）：：8密碼體制的安全性密碼體制的安全性9唯一解距離唯一解距離是指，當進行強力攻擊時，可能接觸唯一有意義的明文所需要的最少密文量。一般而言，唯一解距越長，密碼體制越好。唯一解距離唯一解距離是指，當進行強力攻擊時，可能接觸唯一有意10混亂和散布混亂用于掩蓋明文和密文之間的關(guān)系，如凱撒移位密碼。散布是通過將明文多余度分散到密文中使之分散開來的方法，如置換密碼?；靵y和散布混亂用于掩蓋明文和密文之間的關(guān)系，如凱撒移位密碼。11復雜性理論1、算法的復雜性一個密碼體制的強度是通過破譯它所需的計算能力來確定的，所需的計算能力越大，表明密碼體制的安全強度越大。一個算法的計算復雜性由兩個角度來度量：T（時間復雜性）、S（空間復雜性）。通常，一個算法的計算復雜性的數(shù)量級用“O”表示復雜性理論1、算法的復雜性12表2.1當n=106不同算法族運行時間與n的關(guān)系復雜度所需運算所需時間（106運算/s）常數(shù)線性二次方三次方指數(shù)O(1)O(n)O(n2)O(n3)O(2n)110610121018103010301us1s11.6d32000年宇宙年齡的10301006倍表2.1當n=106不同算法族運行時間與n的關(guān)系復雜度所132、問題的復雜性復雜性理論也將各種問題，按照解決問題時所需最少的時間及最小的空間將之歸納為不同類別的復雜度。

能夠用多項式時間算法解決（輸入與n成多項式關(guān)系）的問題稱之為易處理的。

不能在多項式時間內(nèi)解決的問題稱之為難處理的，難處理的問題有時也稱之為難解問題。復雜度與輸入值成指數(shù)關(guān)系的問題屬于難解問題。

2、問題的復雜性復雜性理論也將各種問題，按照14

依照求解問題所需的時間，復雜性理論也將各種問題區(qū)分成下面各類：（1）P問題：代表那些能夠在多項式時間內(nèi)可解的問題

易處理的，在確定性圖靈機上多項式時間內(nèi)可計算（2）NP問題：多項式時間內(nèi)可驗證的問題

在不確定性Turingmachine上多項式時間內(nèi)可計算,不確定性Turingmachine能進行猜測,即不確定性Turingmachine如能猜出一個解的話,則確定性Turingmachine在多項式時間內(nèi)可校驗解的正確性.依照求解問題所需的時間，復雜性理論也將各種15（3）NP－完全問題：是NP問題中的一些特殊問題，NP中的所有問題都可以轉(zhuǎn)換成NP完全問題。換句話說，只要NP完全問題解決了，其他問題都可以解決。NP完全問題是NP問題中最困難的問題。（3）NP－完全問題：是NP問題中的一些特殊問題，NP中的所163、NP－完全問題

（一）旅行商問題：一名旅行商必須旅行到n個不同的城市，而他只有一箱汽油（即有一個他能旅行的最遠距離）。有方法使他僅用一箱汽油而旅行到每個城市恰好一次嗎？（這是一般的漢密爾頓問題）

（二）三方匹配問題：有一屋子的人，包括n個男人，n個女人和n個牧師（祖父，猶太教士等等）。正常的婚禮將包括一個男人、一個女人和一個愿主持儀式的牧師。有了這樣一張可能的三人一組的表，是否可能安排n個婚禮，使每一個人要么和一個人結(jié)婚，要么主持一個婚禮？3、NP－完全問題17（三）整數(shù)分解問題（四）背包問題（五）離散對數(shù)問題（三）整數(shù)分解問題18數(shù)論數(shù)論是研究數(shù)性質(zhì)的一個數(shù)學分支，他同時也是密碼學的基礎(chǔ)學科之一。全體整數(shù)所組成的集合通常用Z表示，即：Z={…,-3,-2,-1,0,1,2,3,…}數(shù)論數(shù)論是研究數(shù)性質(zhì)的一個數(shù)學分支，他同時也是密碼學的基礎(chǔ)學19chp2-信息論與數(shù)學基礎(chǔ)課件20chp2-信息論與數(shù)學基礎(chǔ)課件21chp2-信息論與數(shù)學基礎(chǔ)課件22chp2-信息論與數(shù)學基礎(chǔ)課件23chp2-信息論與數(shù)學基礎(chǔ)課件24chp2-信息論與數(shù)學基礎(chǔ)課件25歐幾里德（Euclid）算法

歐幾里德（Euclid）算法

歐幾里德（Euclid）算法歐幾里德（Euclid）算法26

首先我們介紹整數(shù)的帶余除法，它是整個數(shù)論的基礎(chǔ)性定理之一。

首先我們介紹整數(shù)的帶余除法，它是整個數(shù)論的基礎(chǔ)27對于兩個整數(shù)a和b，可以對其進行分解來計算它們的最大公因數(shù)，但對于大整數(shù)而言，目前還沒有足夠有效的辦法進行。實際中常用的用來計算兩個數(shù)的最大公因數(shù)的算法稱為歐幾里德算法。它的理論依據(jù)正是前面所述的帶余除法。

對于兩個整數(shù)a和b，可以對其進行分解來計算它們的最大28chp2-信息論與數(shù)學基礎(chǔ)課件29chp2-信息論與數(shù)學基礎(chǔ)課件30chp2-信息論與數(shù)學基礎(chǔ)課件31

例1求(726,393),并求整數(shù)p和q使得(726,393)=726p+393q

例1求(726,393),并求整數(shù)p和q使得32chp2-信息論與數(shù)學基礎(chǔ)課件33自反性對稱性傳遞性除了上述結(jié)論外，以下性質(zhì)也是經(jīng)常用到的自反性除了上述結(jié)論外，以下性質(zhì)也是經(jīng)常用到的34chp2-信息論與數(shù)學基礎(chǔ)課件35chp2-信息論與數(shù)學基礎(chǔ)課件36習題求51mod13,和111mod13.求51mod17.習題求51mod13,和111mo37chp2-信息論與數(shù)學基礎(chǔ)課件38chp2-信息論與數(shù)學基礎(chǔ)課件39例子：

例求21mod11.例子：例求21mod11.40九、中國剩余定理

九、中國剩余定理41例利用中國剩余定理求解下列聯(lián)立的線性同余式

例利用中國剩余定理求解下列聯(lián)立的線性同余式42習題1.

求(937,576),并求整數(shù)p和q使得(937,576)=937p+576q2.求51mod17.3.

利用中國剩余定理求解聯(lián)立的線性同余式:習題1.求(937,576),并求整數(shù)p和q使得243chp2-信息論與數(shù)學基礎(chǔ)課件44例子

設有下列同余式:

x21,x22,x23,x24mod5求解?例子設有下列同余式:45因子分解（NPC:整數(shù)分解問題）

在數(shù)論中，因子分解是一個古老而又困難的問題?，F(xiàn)代的算法并不能測試出一個數(shù)所有可能的素因子。盡管如此，人們在這方面還是取得了不少的進展。

因子分解（NPC:整數(shù)分解問題）

46目前，比較好的因子分解算法有：二次篩選法數(shù)域篩法橢圓曲線法連式分解法試除法

（一）因子分解法目前，比較好的因子分解算法有：（一）因子分解法47（二）模N的平方根如果n是兩個素數(shù)的乘積，那么計算模n的平方根的能力在計算上等價于對n進行因子分解的能力。換句話說，某人知道n的素因子，那么就能容易計算出一個數(shù)模n的平方根；這個計算已被證明與計算n的素因子一樣困難。（二）模N的平方根48素數(shù)生成元

兩個大的素數(shù)相乘，據(jù)推測它是一個單向函數(shù)，因為這兩個數(shù)數(shù)相乘得到一個數(shù)是容易的，但分解這個大數(shù)且恢復原來的兩個大素數(shù)卻是困難的。這樣，就有辦法利用這個單向函數(shù)設計一個陷門單向函數(shù)。素數(shù)生成元49chp2-信息論與數(shù)學基礎(chǔ)課件50

單向函數(shù)是求逆困難的函數(shù)，而Diffie和Hellman引入的概念陷門單向函數(shù)(TrapdoorOne-wayFunction)，是在不知道陷門信息下求逆困難的函數(shù)，當陷門信息知道后，求逆是易于實現(xiàn)的。但如何給陷門單向函數(shù)下定義則難以解決，因為：

(1)陷門函數(shù)其實就不是單向函數(shù)，因為單向函數(shù)在任何條件下求逆都是困難的；

(2)陷門可能不止一個，通過實驗，一個個陷門就可容易地找到逆。如果陷門信息的保密性不強，則求逆不難。單向函數(shù)是求逆困難的函數(shù)，而Diffie和H51測試一個整數(shù)是否素數(shù)也是一個經(jīng)常遇到的事，但它與因子分解相比要容易得多。公鑰密碼體制需要素數(shù)，而產(chǎn)生這些素數(shù)由多種方法。

首先，我們將解決一些顯爾易見的問題：（1）如果每個人都需要一個不同的素數(shù)，是否可以用光素數(shù)？（2）是否會有兩個人偶然地選擇了同樣素數(shù)的情況呢？

測試一個整數(shù)是否素數(shù)也是一個經(jīng)常遇到的52（一）Solovage-Strassen方法（不講）

（二）Rabin－Miller方法

這個算法是由Rabin發(fā)明的。事實上，這也是在NIST（國家標準和技術(shù)研究所）的DSS建議中推薦算法的一個簡化版。

首先選擇一個待測試的隨機數(shù)p。計算b，b是2整除p-1的次數(shù)（即2b是能整除p-1的2的最大冪）。然后計算m，使得n=1+2bm。

(1)

選擇一個隨機數(shù)a，使得a小于p。

(2)

設j=0且z=ammodp。

(3)

如果z=0或z=p-1，那么p通過測試，可能是素數(shù)。

(4)

如果j>0且z=1，那么p不是素數(shù)。

(5)

設j=j+1。如果j<b且z=p-1，設z=z2modp，然后回到步驟（4）。

(6)

如果j=b且z=p-1，那么p不是素數(shù)。

（一）Solovage-Strassen方法（不講）

（二）53（三）Lehmann方法另一種更簡單的測試是由Lehmann獨自研究出的。下面是迭代次數(shù)設置為100的這個算法：(1)

選擇一個待測的隨機數(shù)n。(2)

確信n不能被任何小素數(shù)整除。測試2、3、5、7和11將顯著地提高這個算法的速度。(3)

選擇100個1到n-1之間的隨機數(shù)a1,a2,…,a100。(4)

對所有的ai=

a1,,a2,…,a100，計算ai(n-1)/2：如果對所有的i，ai(n-1)/2=1(modn)，那n可能是合數(shù)。如果對任一個i，ai(n-1)/2=1或-1(modn)，那么n是合數(shù)。如果對所有i，ai(n-1)/2=1或-1(modn)，(但并非所有i均等于1)，那么n是素數(shù)。（三）Lehmann方法54（四）強素數(shù)

p-1和q-1的最大公因子應該較小。

p-1和q-1都應有大的素因子，分別記為p和q。

p-1和q-1都應有大的