(2)b隨機(jī)地向a提問(wèn)從s如何到達(dá)m1

1、隨機(jī)性在計(jì)算機(jī)領(lǐng)域中的作用,,隨機(jī)性的作用,“Randomization is a big idea in computer science.”---C. E. Leiserson @ MIT,隨機(jī)性的作用,賓夕法尼亞大學(xué)的André DeHon在“Big Ideas in Computer Science in Computer Science and Engineering”中總結(jié)了所有計(jì)算機(jī)學(xué)科中有代表性的重要思想，其

2、中多次提到了“隨機(jī)性”。,1. 隨機(jī)化的快速排序算法,,確定性的快速排序算法,確定性的快速排序算法的效率依賴于pivot值的選取。只要pivot值的選取方式固定，都存在一些規(guī)模為n的輸入，使得快速排序算法效率為Θ(n2)。例如，如果每次選取pivot值為待排序數(shù)組的最后一個(gè)值，則快速排序算法對(duì)于已經(jīng)排序好的數(shù)組效率最低。也就是說(shuō)，確定性的快速排序算法希望輸入數(shù)據(jù)沒(méi)有任何規(guī)律，是完全隨機(jī)的。,隨機(jī)化的快速排序算法,每次在輸入數(shù)

3、據(jù)中隨機(jī)地選取pivot值。不存在任何輸入使得隨機(jī)化的快速排序算法在該輸入下復(fù)雜度一定為Θ(n2)。隨機(jī)化的快速排序算法不依賴于外部輸入數(shù)據(jù)的隨機(jī)性。,隨機(jī)算法的作用之一：降低對(duì)輸入數(shù)據(jù)隨機(jī)性的依賴,,,確定性的快速排序算法,依賴于輸入數(shù)據(jù)的“隨機(jī)性”,隨機(jī)性的快速排序算法：帶有一種內(nèi)置的隨機(jī)性(built-inrandomness),不依賴輸入數(shù)據(jù)的“隨機(jī)性”,,,2. 計(jì)算“平均成績(jī)”問(wèn)題,,計(jì)算“平均成

4、績(jī)”問(wèn)題,n個(gè)學(xué)生P1,P2,…,Pn參加了一次考試，學(xué)生Pi的成績(jī)?yōu)镃i(1≤i≤n)。現(xiàn)在這n個(gè)學(xué)生要計(jì)算他們的平均成績(jī)，并且保證：(1) 任何一個(gè)學(xué)生都不泄露自己的成績(jī)。(2) 即使有k個(gè)學(xué)生之間相互共享信息，這k個(gè)學(xué)生最多也只能知道其余n-k個(gè)學(xué)生的平均成績(jī)。是否存在一種可行的方案？,協(xié)議(protocol),我們通過(guò)設(shè)計(jì)一個(gè)“協(xié)議”來(lái)解決這個(gè)問(wèn)題。簡(jiǎn)單地說(shuō)，“協(xié)議”是兩個(gè)(或兩個(gè)以上)人為完成某項(xiàng)任務(wù)而進(jìn)行的一

5、系列操作步驟。最簡(jiǎn)單的協(xié)議是“切蛋糕”協(xié)議。參與者：兩個(gè)人A和B。任務(wù)：公平地分一塊蛋糕。操作步驟：(1)A把蛋糕切成2塊。 (2)B選走其中一塊蛋糕。 (3)A取走剩下的那塊蛋糕。,計(jì)算“平均成績(jī)”問(wèn)題,參與者： n個(gè)學(xué)生P1,P2,…,Pn任務(wù)：計(jì)算平均成績(jī)(滿足前面提到的兩個(gè)條件)步驟：？,協(xié)議1,思想：假設(shè)考試包含n道題目。每個(gè)同學(xué)Pi負(fù)責(zé)統(tǒng)計(jì)所有同學(xué)第i道題目的得分。最后把所有同學(xué)的統(tǒng)計(jì)

6、結(jié)果加起來(lái)，得到總成績(jī)。,協(xié)議1,(1) 每個(gè)學(xué)生Pi把自己的成績(jī)分成n份Ci=Ci1+Ci2+…+Cin（其中Cij代表第i個(gè)同學(xué)第j道題的分?jǐn)?shù)），學(xué)生Pi把Cij告訴給學(xué)生Pj。(2) 每個(gè)學(xué)生Pj計(jì)算并公布Dj=C1j+C2j+…+Cnj (所有學(xué)生第j道題的得分)。(3) 計(jì)算D1+D2+…+Dn，得到總成績(jī)。,協(xié)議1的優(yōu)點(diǎn),一方面，為了計(jì)算總成績(jī)，每個(gè)學(xué)生必須把自己的成績(jī)以某種方式發(fā)布出去，實(shí)現(xiàn)“信息共享”。另一方面，

7、任何學(xué)生都不能直接把自己的成績(jī)告訴給任何人。每個(gè)學(xué)生Pi把自己的成績(jī)分成n份，把其中n-1份分別告訴其他n-1個(gè)同學(xué)。這樣每個(gè)學(xué)生從Pi那得到的只不過(guò)是關(guān)于學(xué)生Pi成績(jī)的“部分信息”。,協(xié)議1的缺點(diǎn),考試未必恰好包含n個(gè)考試題目。假設(shè)k個(gè)同學(xué)共享信息，可以大概估計(jì)其他同學(xué)的考試分?jǐn)?shù)。,協(xié)議2,(1) 每個(gè)學(xué)生Pi把自己的成績(jī)分成n份Ci=Ci1+Ci2+…+Cin(對(duì)任意j, Cij為0和Ci之間的隨機(jī)數(shù))，學(xué)生Pi把Cij告訴給

8、學(xué)生Pj。(2) 每個(gè)學(xué)生Pi計(jì)算并公布Di=C1i+C2i+…+Cni(3) 計(jì)算D1+D2+…+Dn，得到總成績(jī)。,協(xié)議2（例子）,假設(shè)n=30，學(xué)生P1成績(jī)是90，學(xué)生P2成績(jī)是30。則相應(yīng)的矩陣可能為：,協(xié)議2的缺點(diǎn),假設(shè)k個(gè)同學(xué)共享信息，可以大概估計(jì)出：某兩個(gè)學(xué)生Pi和Pj的分?jǐn)?shù)哪個(gè)更高。原因：隨機(jī)變量Cij為0和Ci之間的隨機(jī)數(shù)，因此可以從Cij中得到關(guān)于Ci的統(tǒng)計(jì)信息。,協(xié)議3,思想：選取一個(gè)數(shù)M，使得Ci

9、j為0和M之間的隨機(jī)數(shù)。這樣的好處是：無(wú)需擔(dān)心可以從Cij中得到M的任何統(tǒng)計(jì)信息。,協(xié)議3,(1) 選取M=101*n，每個(gè)學(xué)生Pi產(chǎn)生n-1個(gè)1到M之間的隨機(jī)數(shù)Cij(i ≠j, 1≤j≤n)，計(jì)算Cii，使得Ci=Ci1+Ci2+…+Cin(mod M)，學(xué)生Pi把Cij告訴給學(xué)生Pj。(2) 每個(gè)學(xué)生Pi計(jì)算并公布Di=C1i+C2i+…+Cni(mod M)。(3) 計(jì)算D1+D2+…+Dn (mod M)，得到總

10、成績(jī)。,協(xié)議3（例子）,假設(shè)n=30，選取M=101*30=3030。學(xué)生P1成績(jī)是90，學(xué)生P2成績(jī)是30。相應(yīng)的矩陣可能為：其中矩陣第一行所有值相加等于3120=90(mod 3030)其中矩陣第一行所有值相加等于6090=30(mod 3030),協(xié)議3,分析：協(xié)議3滿足：(1)任何一個(gè)學(xué)生都不泄露自己的成績(jī)。(2)即使有k個(gè)學(xué)生之間相互共享信息，這k個(gè)學(xué)生最多也只能知道其余n-k個(gè)學(xué)生的平均成績(jī)。這

11、是因?yàn)椋好總€(gè)學(xué)生Pi從其他學(xué)生那里得到的無(wú)非是一些0到M(公開(kāi)的)之間的隨機(jī)數(shù)。,隨機(jī)性在協(xié)議3中起的作用,基本思想：把學(xué)生Pi的成績(jī)Ci分成n份Ci=Ci1+Ci2+…+Cin（其中n-1個(gè)數(shù)都是隨機(jī)數(shù)），借助這些隨機(jī)數(shù)的“掩護(hù)”，Ci中包含的信息才不會(huì)被泄露。,3. 驗(yàn)證一個(gè)數(shù)是否為質(zhì)數(shù),,RSA算法,(1)生成兩個(gè)大質(zhì)數(shù)p, q………要想保證RSA的安全性，p和q的數(shù)量級(jí)應(yīng)為21000。,生成質(zhì)數(shù)的算法,generate

12、Prime(m, n)//生成一個(gè)m到n范圍內(nèi)的質(zhì)數(shù)isPrime = false;while(!isPrime)k = rand(m,n);//生成一個(gè)m到n范圍內(nèi)的隨機(jī)數(shù)isPrime = primilityTesting(k);//驗(yàn)證n是否為質(zhì)數(shù)return k;如果要生成一個(gè)21000數(shù)量級(jí)的質(zhì)數(shù)，對(duì)primilityTesting算法效率有很高的要求。,“驗(yàn)證質(zhì)數(shù)”的一個(gè)簡(jiǎn)單算法,p

13、rimilityTesting(n){for i = 2 to n – 1if (n % i == 0)return false;return true;}算法復(fù)雜度為O(n)，也就是說(shuō)要驗(yàn)證一個(gè)21000數(shù)量級(jí)的數(shù)是否為質(zhì)數(shù)，需要O(21000)的時(shí)間。,驗(yàn)證質(zhì)數(shù)的算法,Miller-Rabin Test是驗(yàn)證一個(gè)數(shù)是否為質(zhì)數(shù)的最常用的方法，也是最著名的隨機(jī)算法。我們這里主要介紹該算法的框

14、架結(jié)構(gòu)和整體思想。,Miller-Rabin Test的思想,假定要驗(yàn)證n是否為質(zhì)數(shù)，該算法驗(yàn)證n為質(zhì)數(shù)的某個(gè)必要條件（存在高效率的算法）。根據(jù)驗(yàn)證的結(jié)果判斷n是否為質(zhì)數(shù)。這個(gè)必要條件就是“費(fèi)馬小定理”(Fermat’s Little Theorem),費(fèi)馬小定理,如果一個(gè)數(shù)p是質(zhì)數(shù)，那么對(duì)于任意的a∈{1,2,…,p-1}, ap-1 = 1 (mod p)。例如，從{1,2,…,p-1}中隨機(jī)地選取a=2：7是質(zhì)數(shù)

15、? 2(7-1) = 64 = 1 (mod 7)2(6-1) = 32 = 2 ≠1 (mod 6) ? 6不是質(zhì)數(shù)。,Miller-Rabin Test的思想,如果一個(gè)數(shù)p是質(zhì)數(shù)，那么對(duì)于任意的a∈{1,2,…,p-1}, ap-1 = 1 (mod p)。例如，從{1,2,…,p-1}中隨機(jī)地選取a=2：2(7-1) = 1 (mod 7) ? 7是質(zhì)數(shù)。2(6-1)≠1 (mod 6) ? 6不是質(zhì)數(shù)。,Mi

16、ller-Rabin Test的思想,如果一個(gè)數(shù)p是質(zhì)數(shù)，那么對(duì)于任意的a∈{1,2,…,p-1}, ap-1 = 1 (mod p)。從{1,2,…,p-1}中隨機(jī)地選取a：a(n-1) = 1 (mod n) ? n是質(zhì)數(shù)。(理由不充分)a(n-1)≠1 (mod n) ? n不是質(zhì)數(shù)。(一定成立),Miller-Rabin Test的思想,從{1,2,…,p-1}中隨機(jī)地選取a：a(n-1) = 1 (mod

17、n) ? n是質(zhì)數(shù)。(理由不充分)a(n-1)≠1 (mod n) ? n不是質(zhì)數(shù)。(一定成立)如果算法返回“n不是質(zhì)數(shù)”，則n一定不是質(zhì)數(shù)。如果算法返回“n是質(zhì)數(shù)”，則算法有可能“出錯(cuò)”。事實(shí)上，可以證明，“出錯(cuò)”的概率小于1/2。,Miller-Rabin Test算法,將以下“實(shí)驗(yàn)”重復(fù)進(jìn)行k次：從{1,2,…,p-1}中隨機(jī)地選取a：a(n-1) = 1 (mod n) ? n是質(zhì)數(shù)。(理由不充分)a

18、(n-1)≠1 (mod n) ? n不是質(zhì)數(shù)。(一定成立)(Miller-Rabin Test算法在此基礎(chǔ)上還作了進(jìn)一步的改進(jìn)。)如果算法返回“n不是質(zhì)數(shù)”，則n一定不是質(zhì)數(shù)。如果算法返回“n是質(zhì)數(shù)”，則算法有可能“出錯(cuò)”。事實(shí)上，可以證明，“出錯(cuò)”的概率小于(1/2)k。,隨機(jī)算法中一種常用的技巧,在隨機(jī)算法的精確度和時(shí)間復(fù)雜度之間可以進(jìn)行交換(trade-off)：代價(jià)：算法時(shí)間復(fù)雜度以線性的速度上升。收益：算法“失

19、敗”的概率以指數(shù)級(jí)的速度下降。,4. 零知識(shí)證明（zero-knowledge proof）,,什么是零知識(shí)證明？,A向B證明c，證明結(jié)束后B不知道關(guān)于c的任何信息。J.-J. Quisquater et al., "How to Explain Zero-Knowledge Protocols to Your Children," Proc. Advances in Cryptology, pp. 628-63

20、1, 1989.我們舉另外一個(gè)例子。,一個(gè)直觀的例子,有一個(gè)迷宮，A知道這個(gè)迷宮從入口s到出口t的n條路徑。假設(shè)A想讓B相信從s到t至少有一條路徑，同時(shí)A又不希望向B泄露從s到t的路徑。該采用什么樣的方法？,s,t,,,解決辦法,(1) A選取從s到t的任意一條路徑及路徑上的一個(gè)中間點(diǎn)m1。以m1為界，將路徑一分為二：s,…,m1和m1,…,t。A把m1的位置告訴給B。,s,t,,m1,,,解決辦法,(2) B隨機(jī)地向A提問(wèn)：“從s

21、如何到達(dá)m1？”或“從m1如何到達(dá)t？”,s,t,,m1,,,解決辦法,(3) A回答B(yǎng)的問(wèn)題，B驗(yàn)證A的答案是否正確。如果正確，則B相信A知道從s到t的路徑。,s,t,,m1,,,分析,從B的角度，假設(shè)A只知道s,…,m1和m1,…,t其中的一條路徑。A能正確回答B(yǎng)的問(wèn)題的概率為1/2。,s,t,,m1,,,解決辦法&分析,如果把前面的協(xié)議看成一次“隨機(jī)實(shí)驗(yàn)”，該實(shí)驗(yàn)失敗的概率為1/2。如果A和B重復(fù)進(jìn)行該實(shí)驗(yàn)k次，失敗的概

22、率為(1/2)k。當(dāng)k足夠大時(shí)， (1/2)k足夠小，k次實(shí)驗(yàn)全部失敗的概率可以忽略不計(jì)。,s,t,,m1,,,,,m2,,,,,。。。 。。。,mk,解決辦法&分析,A每次向B提供的信息都是“部分信息”，B不足以從這些部分信息中“拼湊出”從s到t的路徑。,s,t,,m1,,,,,m2,,,,,。。。 。。。,mk,隨機(jī)性所起的作用,我們注意到：(2) B隨機(jī)地向A提問(wèn)：“從s如何到達(dá)m1？”或“從m1如何到達(dá)t？”假如

23、A預(yù)先知道B提的問(wèn)題是：“從s如何到達(dá)m1？”，則A有辦法欺騙B。同樣道理，假如A預(yù)先知道B提的問(wèn)題是： “從m1如何到達(dá)t？” ，A同樣有辦法欺騙B。,總結(jié),“驗(yàn)證身份(authentication)”問(wèn)題,一組用戶A, B, C,…每個(gè)用戶都有一個(gè)私有信息。假如A想向B表明身份：(1) A向B證明他(她)知道xA。(2) A不希望泄露xA。,數(shù)論基礎(chǔ),為了解決“驗(yàn)證身份”問(wèn)題，我們?cè)赯n*上考慮問(wèn)題:Zn* = {

24、i | 1≤ i ≤n-1, gcd(i, n) = 1}，其中n為兩個(gè)不相同質(zhì)數(shù)的乘積。假設(shè)n = 3×7 = 21，Zn* ={1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}Zn*在乘法操作下，形成一個(gè)代數(shù)系統(tǒng)“群(group)”.,游戲時(shí)間！,,Zn*中的乘法操作,對(duì)任意的a, b∈Zn*，a*b = a*b (mod n)。例如，在Z21*中，2*4 = 8 (

25、mod 21)4*16 = 1 (mod 21)在Zn*中乘法操作是簡(jiǎn)單的(regular multiplication & division)。,Zn*中的除法操作,對(duì)任意的b∈Zn*，存在唯一的c ∈Zn*，使得b*c = 1 (mod n)我們把c叫做b的倒數(shù)，記為b-1。在Zn*中，已知一個(gè)數(shù)b，計(jì)算b-1是簡(jiǎn)單的(the extended Euclidean algorithm)。,Zn*中的除法操作,對(duì)

26、任意的a, b∈Zn*a/b = a*b-1 (mod n)例如，在Z21*中，5/8 = 5*(8-1) = 5*8 = 19 (mod 21)在Zn*中除法操作是簡(jiǎn)單的(the extended Euclidean algorithm & regular multiplication and division)。,在Zn*中求平方,對(duì)任意的a∈Zn*，a2 = a*a (mod n)例如，在Z21*中，52

27、= 4(mod 21)在Zn*中“求平方”操作是簡(jiǎn)單的(regular multiplication & division)。,在Zn*中開(kāi)平方,對(duì)任意的a, b∈Zn*，如果a2 = b (mod n)那么，a叫做b的一個(gè)平方根。對(duì)于較大的n，在不知道n的質(zhì)因數(shù)分解的情況下，在Zn*中“開(kāi)方”操作是極其復(fù)雜的。,總結(jié),在Zn*(n為兩個(gè)不同質(zhì)數(shù)的乘積)中：,“驗(yàn)證身份(authentication)”問(wèn)題,一組用戶A

28、, B, C,…每個(gè)用戶都有一個(gè)私有信息。假如A想向B表明身份：(1) A向B證明他(她)知道xA。(2) A不希望泄露xA。,“驗(yàn)證身份(authentication)”問(wèn)題,選取n為兩個(gè)不同大質(zhì)數(shù)p和q的乘積。每個(gè)用戶都知道n，但并不知道p或者q。每個(gè)用戶i從Zn*中隨機(jī)地選取一個(gè)數(shù)xi，計(jì)算Xi = xi2 (mod n)，并把(i, Xi)公開(kāi)。,“驗(yàn)證身份(authentication)”問(wèn)題,假設(shè)A想向B表明身份

29、，最簡(jiǎn)單的辦法：(1) A把xA告訴給B。(2) B驗(yàn)證xA2 = XA (mod n)是否成立。但這樣做之后，B知道xA，B可以偽裝成A和其他用戶通信。我們需要用到“零知識(shí)證明”。,“零知識(shí)證明”的思想,A首先生成一個(gè)隨機(jī)數(shù)y，并計(jì)算Y = y2(mod n)。A把關(guān)于xA的信息“拆分”成兩部分，“y”和“y*xA”。(1) 把兩部分信息和在一起，可以得到xA。(2) y對(duì)xA起“掩護(hù)”作用。,s,t,,Y,,,y

30、,y*xA,類比,解決辦法,(1) A隨機(jī)地生成一個(gè)數(shù)y∈Zn*，計(jì)算Y = y2(mod n)。A把Y告訴給B。,s,t,,Y,,,y,y*xA,解決辦法,(2) B隨機(jī)地向A提問(wèn)：“y等于多少？”或“y*xA等于多少？”,s,t,,Y,,,y,y*xA,解決辦法,(3) A回答B(yǎng)的問(wèn)題，B驗(yàn)證A的答案。3.1 問(wèn)題: “y等于多少?” ? 驗(yàn)證: y2 = Y (mod n)?3.2 問(wèn)題: “y*xA等于多少?” ? 驗(yàn)證

31、: (y*xA)2= Y*XA (mod n)?,s,t,,Y,,,y,y*xA,分析,從B的角度，假設(shè)A只知道“y”或“y*xA” 。A能正確回答B(yǎng)的問(wèn)題的概率為1/2。,s,t,,,,Y,y,y*xA,解決辦法&分析,如果把前面的協(xié)議看成一次“隨機(jī)實(shí)驗(yàn)”，該實(shí)驗(yàn)失敗的概率為1/2。如果A和B重復(fù)進(jìn)行該實(shí)驗(yàn)k次，失敗的概率為(1/2)k。當(dāng)k足夠大時(shí)， (1/2)k足夠小，k次實(shí)驗(yàn)全部失敗的概率可以忽略不計(jì)。,s,t,,Y1

32、,,,,,Y2,,,,,。。。 。。。,Yk,解決辦法&分析,A每次向B提供的信息或者是“y”或者是“y*xA”，B不足以從這些隨機(jī)信息中得到關(guān)于xA的任何信息。,s,t,,Y1,,,,,Y2,,,,,。。。 。。。,Yk,隨機(jī)性所起的作用,我們注意到：(2) B隨機(jī)地向A提問(wèn)：“y等于多少？”或“y*xA等于多少？”假如A預(yù)先知道B提的問(wèn)題是： “y等于多少？” ，則A有辦法欺騙B。同樣道理，假如A預(yù)先知道B提的問(wèn)

33、題是： “y*xA等于多少？” ，A同樣有辦法欺騙B。,5. 隨機(jī)性方法在數(shù)據(jù)通信中的應(yīng)用,,問(wèn)題,已知：A和B各有一個(gè)文本文件，并且A和B之間通過(guò)一條可靠（但昂貴）的通訊線路連接。目標(biāo)：A和B需要比較他們的文本文件是否相同。要求：在A與B之間通訊的數(shù)據(jù)量盡量少。方法：？,問(wèn)題,,This is my document …,This is my document …,1001011101 …,1001011101 …,A,B

34、,,,,,,?,問(wèn)題,已知：A和B各有一個(gè)二進(jìn)制序列（二進(jìn)制數(shù)），并且A和B之間通過(guò)一條可靠（但昂貴）的通訊線路連接。目標(biāo)：A和B需要比較他們的二進(jìn)制序列（二進(jìn)制數(shù)）是否相同。要求：在A與B之間通訊的數(shù)據(jù)量盡量少。方法：？,方法1,(確定性的方法)A和B事先約定好，A只向B傳輸二進(jìn)制序列的某些位（比如，奇數(shù)位）。B接收到A傳來(lái)的數(shù)據(jù)后，依序跟自己序列的相應(yīng)位（奇數(shù)位）位比較。,方法1的缺點(diǎn),有時(shí)候，方法1能檢測(cè)出A與

35、B數(shù)據(jù)的不一致。,有時(shí)候，方法1不能檢測(cè)出A與B數(shù)據(jù)的不一致。,A: 1011010,B: 1011110,A: 1011010,A: 1111010,,,,,方法1的缺點(diǎn),條件：假設(shè)A與B的二進(jìn)制序列長(zhǎng)度為n，選取傳輸位的方法為確定性的方法且傳輸位的總位數(shù)小于n。結(jié)論：則總存在某些情況，使得A與B之間數(shù)據(jù)的不一致性永遠(yuǎn)無(wú)法得到檢測(cè)（檢測(cè)出數(shù)據(jù)不一致性的概率為0）。,方法2,(隨機(jī)性的方法)A隨機(jī)地向B傳輸二進(jìn)制序列的某些位。

36、B接收到A傳來(lái)的數(shù)據(jù)后，依序跟自己序列的對(duì)應(yīng)位比較。,方法2的缺點(diǎn),對(duì)于A傳送的每一個(gè)比特位，都需要附加相應(yīng)的信息，來(lái)表示該比特位對(duì)應(yīng)A數(shù)據(jù)的哪一位。該方法能成功地檢測(cè)A與B數(shù)據(jù)不一致的概率較低。假設(shè)只傳輸100個(gè)比特位，成功驗(yàn)證兩個(gè)長(zhǎng)度為100000的比特序列是否一致的概率小于0.1%。,方法2的缺點(diǎn),假設(shè)A與B的二進(jìn)制序列長(zhǎng)度為n，且其中只有一個(gè)比特位不一致。如果A隨機(jī)地向B傳送k比特的數(shù)據(jù)，則用方法2能成功地檢測(cè)出這

37、種不一致性的概率為： / = k/n 。,方法3,思想：采用傳輸數(shù)據(jù)指紋（fingerprint）的方法。A向B傳送A數(shù)據(jù)的指紋，B核對(duì)該指紋是否與自己數(shù)據(jù)的指紋一致。一個(gè)數(shù)據(jù)的數(shù)據(jù)指紋中包含原數(shù)據(jù)的特征信息。,,我們前面已經(jīng)提到了，A和B的數(shù)據(jù)都可以看成是二進(jìn)制序列（二進(jìn)制數(shù)）。最簡(jiǎn)單的生成數(shù)據(jù)指紋的方法：對(duì)于一個(gè)二進(jìn)制數(shù)n，其指紋為“n (mod p)”其中p為一個(gè)質(zhì)數(shù)。,數(shù)據(jù)指紋的例子,為了直觀

38、起見(jiàn)，我們用十進(jìn)制數(shù)來(lái)解釋數(shù)據(jù)指紋，二進(jìn)制數(shù)的指紋類似。假設(shè)，n = 8928，選取p = 23：8929 (mod 23) = 4意味著8929在“mod 23”操作下的數(shù)據(jù)指紋為4。,方法2.9999,假定A和B的數(shù)據(jù)分別為xA和xB（位數(shù)為n）A隨機(jī)選取一個(gè)質(zhì)數(shù)p（位數(shù)最多為m），A向B發(fā)送xA (mod p)。B接收到指紋后，核對(duì)xA (mod p) = xB (mod p)是否成立。,方法3,假定A和B的數(shù)據(jù)分別

39、為xA和xB（位數(shù)為n）A隨機(jī)選取一個(gè)質(zhì)數(shù)p（位數(shù)最多為m），A向B發(fā)送xA (mod p)和p。B接收到指紋后，核對(duì)xA (mod p) = xB (mod p)是否成立。,方法3 --- 例子,,,A:8928,mod 23,4,B:8928,mod 23,4,(4, 23),,,,,,,=?,,,,,A: 8928,mod 23,4,B:8944,mod 23,20,(4, 23),,,,,,,=?,,,,,方法3 ---

40、例子,,如果B的數(shù)據(jù)為8928+23*k, 用方法3都會(huì)“出錯(cuò)”。下面我們來(lái)分析一下方法3出錯(cuò)的概率。,A:8928,mod 23,4,B:8951,mod 23,4,(4, 23),,,,,,,=?,,,,,方法3 --- 分析,為了區(qū)分xA和xB (xA≠xB) ，我們隨機(jī)地選取一個(gè)質(zhì)數(shù)p，進(jìn)行“mod p”操作：如果p | |xA-xB|， 則xA ≠ xB (mod p)。即：p能將xA和xB區(qū)分開(kāi)來(lái)。如果p | |x

41、A-xB|， 則xA = xB (mod p)。即：p不能將xA和xB區(qū)分開(kāi)來(lái)。,,方法3 --- 分析,Fact #1: 小于等于n的數(shù)中大約有n / ln(n)個(gè)質(zhì)數(shù)。Fact #2: 如果x ≤ 2n，則x最多有n個(gè)不同的質(zhì)因數(shù)。P[failure]= (|xA-xB|的質(zhì)因數(shù)的個(gè)數(shù)) / (1到2m之間的質(zhì)數(shù)的個(gè)數(shù))< n / (2m / ln(2m))例如，n=100000，m=32：P[fail

42、ure] ≈ 10-3假設(shè)只傳輸64個(gè)比特位，成功驗(yàn)證兩個(gè)長(zhǎng)度為100000的比特序列是否一致的概率大概是99.9%。我們還可以通過(guò)“重復(fù)進(jìn)行隨機(jī)試驗(yàn)”的方法提高成功的概率。,6. 隨機(jī)性方法在圖論中的應(yīng)用,,圖,定義圖G = (V, E)，其中V為頂點(diǎn)的集合，E為邊的集合。例如，,,,,,,,,,,,,,,,連通圖,在圖G = (V, E)中，p1, p2, …, pn叫做從v到v’的路徑，當(dāng)且僅當(dāng)p1=v, pn=v’，(p

43、i, pi+1) ∈E（1 ≤ i ≤ n-1）。圖G = (V, E)被稱為是連通圖，當(dāng)且僅當(dāng)對(duì)任意的v, v’∈V，都存在從v到v’的路徑。,連通度,已知一個(gè)連通圖G = (V, E)，如果至少需要從G中去掉c條邊才能使G變?yōu)榉沁B通圖，則c稱為G的連通度(connectivity)。,研究連通度的意義,假設(shè)我們用圖來(lái)表示一個(gè)局域網(wǎng)：頂點(diǎn)表示局域網(wǎng)中的計(jì)算機(jī)，邊表示計(jì)算機(jī)之間的物理連接。則，連通度在一定程度上表示該局域網(wǎng)的可靠程度

44、。假設(shè)我們用圖來(lái)表示一個(gè)交通網(wǎng)絡(luò)：頂點(diǎn)表示城市，邊表示城市之間的公路。則，連通度在一定程度上表示該交通網(wǎng)絡(luò)的抗阻塞能力。,計(jì)算連通度的算法,計(jì)算圖連通度的確定性算法是基于網(wǎng)絡(luò)流(network flow)的方法。該算法復(fù)雜，而且效率低。目前，計(jì)算圖連通度常用算法是一種隨機(jī)算法。和確定性的算法相比，該方法不僅簡(jiǎn)單，而且效率較高。,計(jì)算連通度的隨機(jī)性算法,connectivity(G)//G=(V, E)while(|V|≠2

45、)choose an edge (x, y) at random in G;//在G中隨機(jī)選擇一條邊(x, y)contract (x, y);//聚合邊(x, y)return |E|;,分析,給定一個(gè)圖G = (V, E)，重復(fù)執(zhí)行connectivity(G) kn2次之后，算法“出錯(cuò)”的概率小于(1/e)k (其中n為圖G的頂點(diǎn)數(shù)，e為自然對(duì)數(shù)的底)。Nick Harvey: “The Bes