1、随机性在计算机领域中的作用,随机性的作用,“Randomization is a big idea in computer science.”-C. E. Leiserson MIT,随机性的作用,宾夕法尼亚大学的Andr DeHon在“Big Ideas in Computer Science in Computer Science and Engineering”中总结了所有计算机学科中有代表性的重要思想，其中多次提到了“随机性”。,1. 随机化的快速排序算法,确定性的快速排序算法,确定性的快速排序算法的效率依赖于pivot值的选取。只要pivot值的选取方式固定，都存在一些规模为n的输入
2、，使得快速排序算法效率为(n2)。例如，如果每次选取pivot值为待排序数组的最后一个值，则快速排序算法对于已经排序好的数组效率最低。也就是说，确定性的快速排序算法希望输入数据没有任何规律，是完全随机的。,随机化的快速排序算法,每次在输入数据中随机地选取pivot值。不存在任何输入使得随机化的快速排序算法在该输入下复杂度一定为(n2)。随机化的快速排序算法不依赖于外部输入数据的随机性。,随机算法的作用之一：降低对输入数据随机性的依赖,确定性的快速排序算法,依赖于输入数据的“随机性”,随机性的快速排序算法：带有一种内置的随机性(built-inrandomness),不依赖输入数据的“随机性”,
3、2. 计算“平均成绩”问题,计算“平均成绩”问题,n个学生P1,P2,Pn参加了一次考试，学生Pi的成绩为Ci(1in)。现在这n个学生要计算他们的平均成绩，并且保证：(1) 任何一个学生都不泄露自己的成绩。(2) 即使有k个学生之间相互共享信息，这k个学生最多也只能知道其余n-k个学生的平均成绩。是否存在一种可行的方案？,协议(protocol),我们通过设计一个“协议”来解决这个问题。简单地说，“协议”是两个(或两个以上)人为完成某项任务而进行的一系列操作步骤。最简单的协议是“切蛋糕”协议。参与者：两个人A和B。任务：公平地分一块蛋糕。操作步骤：(1)A把蛋糕切成2块。 (2)B选走其中一
4、块蛋糕。 (3)A取走剩下的那块蛋糕。,计算“平均成绩”问题,参与者： n个学生P1,P2,Pn任务：计算平均成绩(满足前面提到的两个条件)步骤：？,协议1,思想：假设考试包含n道题目。每个同学Pi负责统计所有同学第i道题目的得分。最后把所有同学的统计结果加起来，得到总成绩。,协议1,(1) 每个学生Pi把自己的成绩分成n份Ci=Ci1+Ci2+Cin（其中Cij代表第i个同学第j道题的分数），学生Pi把Cij告诉给学生Pj。(2) 每个学生Pj计算并公布Dj=C1j+C2j+Cnj (所有学生第j道题的得分)。(3) 计算D1+D2+Dn，得到总成绩。,协议1的优点,一方面，为了计算总成绩，
5、每个学生必须把自己的成绩以某种方式发布出去，实现“信息共享”。另一方面，任何学生都不能直接把自己的成绩告诉给任何人。每个学生Pi把自己的成绩分成n份，把其中n-1份分别告诉其他n-1个同学。这样每个学生从Pi那得到的只不过是关于学生Pi成绩的“部分信息”。,协议1的缺点,考试未必恰好包含n个考试题目。假设k个同学共享信息，可以大概估计其他同学的考试分数。,协议2,(1) 每个学生Pi把自己的成绩分成n份Ci=Ci1+Ci2+Cin(对任意j, Cij为0和Ci之间的随机数)，学生Pi把Cij告诉给学生Pj。(2) 每个学生Pi计算并公布Di=C1i+C2i+Cni(3) 计算D1+D2+Dn，
6、得到总成绩。,协议2（例子）,假设n=30，学生P1成绩是90，学生P2成绩是30。则相应的矩阵可能为：,协议2的缺点,假设k个同学共享信息，可以大概估计出：某两个学生Pi和Pj的分数哪个更高。原因：随机变量Cij为0和Ci之间的随机数，因此可以从Cij中得到关于Ci的统计信息。,协议3,思想：选取一个数M，使得Cij为0和M之间的随机数。这样的好处是：无需担心可以从Cij中得到M的任何统计信息。,协议3,(1) 选取M=101*n，每个学生Pi产生n-1个1到M之间的随机数Cij(i j, 1jn)，计算Cii，使得Ci=Ci1+Ci2+Cin(mod M)，学生Pi把Cij告诉给学生Pj。
7、(2) 每个学生Pi计算并公布Di=C1i+C2i+Cni(mod M)。(3) 计算D1+D2+Dn (mod M)，得到总成绩。,协议3（例子）,假设n=30，选取M=101*30=3030。学生P1成绩是90，学生P2成绩是30。相应的矩阵可能为：其中矩阵第一行所有值相加等于3120=90(mod 3030)其中矩阵第一行所有值相加等于6090=30(mod 3030),协议3,分析：协议3满足：(1)任何一个学生都不泄露自己的成绩。(2)即使有k个学生之间相互共享信息，这k个学生最多也只能知道其余n-k个学生的平均成绩。这是因为：每个学生Pi从其他学生那里得到的无非是一些0到M(公开的
8、)之间的随机数。,随机性在协议3中起的作用,基本思想：把学生Pi的成绩Ci分成n份Ci=Ci1+Ci2+Cin（其中n-1个数都是随机数），借助这些随机数的“掩护”，Ci中包含的信息才不会被泄露。,3. 验证一个数是否为质数,RSA算法,(1)生成两个大质数p, q要想保证RSA的安全性，p和q的数量级应为21000。,生成质数的算法,generatePrime(m, n)/生成一个m到n范围内的质数isPrime = false;while(!isPrime)k = rand(m,n);/生成一个m到n范围内的随机数isPrime = primilityTesting(k);/验证n是否为质
9、数return k;如果要生成一个21000数量级的质数，对primilityTesting算法效率有很高的要求。,“验证质数”的一个简单算法,primilityTesting(n)for i = 2 to n 1if (n % i = 0)return false;return true;算法复杂度为O(n)，也就是说要验证一个21000数量级的数是否为质数，需要O(21000)的时间。,验证质数的算法,Miller-Rabin Test是验证一个数是否为质数的最常用的方法，也是最著名的随机算法。我们这里主要介绍该算法的框架结构和整体思想。,Miller-Rabin Test的思想,假定要验
10、证n是否为质数，该算法验证n为质数的某个必要条件（存在高效率的算法）。根据验证的结果判断n是否为质数。这个必要条件就是“费马小定理”(Fermats Little Theorem),费马小定理,如果一个数p是质数，那么对于任意的a1,2,p-1, ap-1 = 1 (mod p)。例如，从1,2,p-1中随机地选取a=2：7是质数 2(7-1) = 64 = 1 (mod 7)2(6-1) = 32 = 2 1 (mod 6) 6不是质数。,Miller-Rabin Test的思想,如果一个数p是质数，那么对于任意的a1,2,p-1, ap-1 = 1 (mod p)。例如，从1,2,p-1中
11、随机地选取a=2：2(7-1) = 1 (mod 7) 7是质数。2(6-1)1 (mod 6) 6不是质数。,Miller-Rabin Test的思想,如果一个数p是质数，那么对于任意的a1,2,p-1, ap-1 = 1 (mod p)。从1,2,p-1中随机地选取a：a(n-1) = 1 (mod n) n是质数。(理由不充分)a(n-1)1 (mod n) n不是质数。(一定成立),Miller-Rabin Test的思想,从1,2,p-1中随机地选取a：a(n-1) = 1 (mod n) n是质数。(理由不充分)a(n-1)1 (mod n) n不是质数。(一定成立)如果算法返回“
12、n不是质数”，则n一定不是质数。如果算法返回“n是质数”，则算法有可能“出错”。事实上，可以证明，“出错”的概率小于1/2。,Miller-Rabin Test算法,将以下“实验”重复进行k次：从1,2,p-1中随机地选取a：a(n-1) = 1 (mod n) n是质数。(理由不充分)a(n-1)1 (mod n) n不是质数。(一定成立)(Miller-Rabin Test算法在此基础上还作了进一步的改进。)如果算法返回“n不是质数”，则n一定不是质数。如果算法返回“n是质数”，则算法有可能“出错”。事实上，可以证明，“出错”的概率小于(1/2)k。,随机算法中一种常用的技巧,在随机算法的
13、精确度和时间复杂度之间可以进行交换(trade-off)：代价：算法时间复杂度以线性的速度上升。收益：算法“失败”的概率以指数级的速度下降。,4. 零知识证明（zero-knowledge proof）,什么是零知识证明？,A向B证明c，证明结束后B不知道关于c的任何信息。J.-J. Quisquater et al., How to Explain Zero-Knowledge Protocols to Your Children, Proc. Advances in Cryptology, pp. 628-631, 1989.我们举另外一个例子。,一个直观的例子,有一个迷宫，A知道这个迷宫
14、从入口s到出口t的n条路径。假设A想让B相信从s到t至少有一条路径，同时A又不希望向B泄露从s到t的路径。该采用什么样的方法？,s,t,解决办法,(1) A选取从s到t的任意一条路径及路径上的一个中间点m1。以m1为界，将路径一分为二：s,m1和m1,t。A把m1的位置告诉给B。,s,t,m1,解决办法,(2) B随机地向A提问：“从s如何到达m1？”或“从m1如何到达t？”,s,t,m1,解决办法,(3) A回答B的问题，B验证A的答案是否正确。如果正确，则B相信A知道从s到t的路径。,s,t,m1,分析,从B的角度，假设A只知道s,m1和m1,t其中的一条路径。A能正确回答B的问题的概率为
15、1/2。,s,t,m1,解决办法&分析,如果把前面的协议看成一次“随机实验”，该实验失败的概率为1/2。如果A和B重复进行该实验k次，失败的概率为(1/2)k。当k足够大时， (1/2)k足够小，k次实验全部失败的概率可以忽略不计。,s,t,m1,m2,。 。,mk,解决办法&分析,A每次向B提供的信息都是“部分信息”，B不足以从这些部分信息中“拼凑出”从s到t的路径。,s,t,m1,m2,。 。,mk,随机性所起的作用,我们注意到：(2) B随机地向A提问：“从s如何到达m1？”或“从m1如何到达t？”假如A预先知道B提的问题是：“从s如何到达m1？”，则A有办法欺骗B。同样道理，假如A预先
16、知道B提的问题是： “从m1如何到达t？” ，A同样有办法欺骗B。,总结,“验证身份(authentication)”问题,一组用户A, B, C,每个用户都有一个私有信息。假如A想向B表明身份：(1) A向B证明他(她)知道xA。(2) A不希望泄露xA。,数论基础,为了解决“验证身份”问题，我们在Zn*上考虑问题:Zn* = i | 1 i n-1, gcd(i, n) = 1，其中n为两个不相同质数的乘积。假设n = 37 = 21，Zn* =1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20Zn*在乘法操作下，形成一个代数系统“群(group)”.,游戏
17、时间！,Zn*中的乘法操作,对任意的a, bZn*，a*b = a*b (mod n)。例如，在Z21*中，2*4 = 8 (mod 21)4*16 = 1 (mod 21)在Zn*中乘法操作是简单的(regular multiplication & division)。,Zn*中的除法操作,对任意的bZn*，存在唯一的c Zn*，使得b*c = 1 (mod n)我们把c叫做b的倒数，记为b-1。在Zn*中，已知一个数b，计算b-1是简单的(the extended Euclidean algorithm)。,Zn*中的除法操作,对任意的a, bZn*a/b = a*b-1 (mod n)例
18、如，在Z21*中，5/8 = 5*(8-1) = 5*8 = 19 (mod 21)在Zn*中除法操作是简单的(the extended Euclidean algorithm & regular multiplication and division)。,在Zn*中求平方,对任意的aZn*，a2 = a*a (mod n)例如，在Z21*中，52 = 4(mod 21)在Zn*中“求平方”操作是简单的(regular multiplication & division)。,在Zn*中开平方,对任意的a, bZn*，如果a2 = b (mod n)那么，a叫做b的一个平方根。对于较大的n，在不
19、知道n的质因数分解的情况下，在Zn*中“开方”操作是极其复杂的。,总结,在Zn*(n为两个不同质数的乘积)中：,“验证身份(authentication)”问题,一组用户A, B, C,每个用户都有一个私有信息。假如A想向B表明身份：(1) A向B证明他(她)知道xA。(2) A不希望泄露xA。,“验证身份(authentication)”问题,选取n为两个不同大质数p和q的乘积。每个用户都知道n，但并不知道p或者q。每个用户i从Zn*中随机地选取一个数xi，计算Xi = xi2 (mod n)，并把(i, Xi)公开。,“验证身份(authentication)”问题,假设A想向B表明身份，
20、最简单的办法：(1) A把xA告诉给B。(2) B验证xA2 = XA (mod n)是否成立。但这样做之后，B知道xA，B可以伪装成A和其他用户通信。我们需要用到“零知识证明”。,“零知识证明”的思想,A首先生成一个随机数y，并计算Y = y2(mod n)。A把关于xA的信息“拆分”成两部分，“y”和“y*xA”。(1) 把两部分信息和在一起，可以得到xA。(2) y对xA起“掩护”作用。,s,t,Y,y,y*xA,类比,解决办法,(1) A随机地生成一个数yZn*，计算Y = y2(mod n)。A把Y告诉给B。,s,t,Y,y,y*xA,解决办法,(2) B随机地向A提问：“y等于多少
21、？”或“y*xA等于多少？”,s,t,Y,y,y*xA,解决办法,(3) A回答B的问题，B验证A的答案。3.1 问题: “y等于多少?” 验证: y2 = Y (mod n)?3.2 问题: “y*xA等于多少?” 验证: (y*xA)2= Y*XA (mod n)?,s,t,Y,y,y*xA,分析,从B的角度，假设A只知道“y”或“y*xA” 。A能正确回答B的问题的概率为1/2。,s,t,Y,y,y*xA,解决办法&分析,如果把前面的协议看成一次“随机实验”，该实验失败的概率为1/2。如果A和B重复进行该实验k次，失败的概率为(1/2)k。当k足够大时， (1/2)k足够小，k次实验全部
22、失败的概率可以忽略不计。,s,t,Y1,Y2,。 。,Yk,解决办法&分析,A每次向B提供的信息或者是“y”或者是“y*xA”，B不足以从这些随机信息中得到关于xA的任何信息。,s,t,Y1,Y2,。 。,Yk,随机性所起的作用,我们注意到：(2) B随机地向A提问：“y等于多少？”或“y*xA等于多少？”假如A预先知道B提的问题是： “y等于多少？” ，则A有办法欺骗B。同样道理，假如A预先知道B提的问题是： “y*xA等于多少？” ，A同样有办法欺骗B。,5. 随机性方法在数据通信中的应用,问题,已知：A和B各有一个文本文件，并且A和B之间通过一条可靠（但昂贵）的通讯线路连接。目标：A和B
23、需要比较他们的文本文件是否相同。要求：在A与B之间通讯的数据量尽量少。方法：？,问题,This is my document ,This is my document ,1001011101 ,1001011101 ,A,B,?,问题,已知：A和B各有一个二进制序列（二进制数），并且A和B之间通过一条可靠（但昂贵）的通讯线路连接。目标：A和B需要比较他们的二进制序列（二进制数）是否相同。要求：在A与B之间通讯的数据量尽量少。方法：？,方法1,(确定性的方法)A和B事先约定好，A只向B传输二进制序列的某些位（比如，奇数位）。B接收到A传来的数据后，依序跟自己序列的相应位（奇数位）位比较。,方法1
24、的缺点,有时候，方法1能检测出A与B数据的不一致。,有时候，方法1不能检测出A与B数据的不一致。,A: 1011010,B: 1011110,A: 1011010,A: 1111010,方法1的缺点,条件：假设A与B的二进制序列长度为n，选取传输位的方法为确定性的方法且传输位的总位数小于n。结论：则总存在某些情况，使得A与B之间数据的不一致性永远无法得到检测（检测出数据不一致性的概率为0）。,方法2,(随机性的方法)A随机地向B传输二进制序列的某些位。B接收到A传来的数据后，依序跟自己序列的对应位比较。,方法2的缺点,对于A传送的每一个比特位，都需要附加相应的信息，来表示该比特位对应A数据的哪
25、一位。该方法能成功地检测A与B数据不一致的概率较低。假设只传输100个比特位，成功验证两个长度为100000的比特序列是否一致的概率小于0.1%。,方法2的缺点,假设A与B的二进制序列长度为n，且其中只有一个比特位不一致。如果A随机地向B传送k比特的数据，则用方法2能成功地检测出这种不一致性的概率为： / = k/n 。,方法3,思想：采用传输数据指纹（fingerprint）的方法。A向B传送A数据的指纹，B核对该指纹是否与自己数据的指纹一致。一个数据的数据指纹中包含原数据的特征信息。,我们前面已经提到了，A和B的数据都可以看成是二进制序列（二进制数）。最简单的生成数据指纹的方法：对于一个二
26、进制数n，其指纹为“n (mod p)”其中p为一个质数。,数据指纹的例子,为了直观起见，我们用十进制数来解释数据指纹，二进制数的指纹类似。假设，n = 8928，选取p = 23：8929 (mod 23) = 4意味着8929在“mod 23”操作下的数据指纹为4。,方法2.9999,假定A和B的数据分别为xA和xB（位数为n）A随机选取一个质数p（位数最多为m），A向B发送xA (mod p)。B接收到指纹后，核对xA (mod p) = xB (mod p)是否成立。,方法3,假定A和B的数据分别为xA和xB（位数为n）A随机选取一个质数p（位数最多为m），A向B发送xA (mod p
27、)和p。B接收到指纹后，核对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 - 例子,如果B的数据为8928+23*k, 用方法3都会“出错”。下面我们来分析一下方法3出错的概率。,A:8928,mod 23,4,B:8951,mod 23,4,(4, 23),=?,方法3 - 分析,为了区分xA和xB (xAxB) ，我们随机地选取一个质数p，进行“mod p”操作：如果p | |x
28、A-xB|， 则xA xB (mod p)。即：p能将xA和xB区分开来。如果p | |xA-xB|， 则xA = xB (mod p)。即：p不能将xA和xB区分开来。,方法3 - 分析,Fact #1: 小于等于n的数中大约有n / ln(n)个质数。Fact #2: 如果x 2n，则x最多有n个不同的质因数。Pfailure= (|xA-xB|的质因数的个数) / (1到2m之间的质数的个数) n / (2m / ln(2m)例如，n=100000，m=32：Pfailure 10-3假设只传输64个比特位，成功验证两个长度为100000的比特序列是否一致的概率大概是99.9%。我们还可
29、以通过“重复进行随机试验”的方法提高成功的概率。,6. 随机性方法在图论中的应用,图,定义图G = (V, E)，其中V为顶点的集合，E为边的集合。例如，,连通图,在图G = (V, E)中，p1, p2, , pn叫做从v到v的路径，当且仅当p1=v, pn=v，(pi, pi+1) E（1 i n-1）。图G = (V, E)被称为是连通图，当且仅当对任意的v, vV，都存在从v到v的路径。,连通度,已知一个连通图G = (V, E)，如果至少需要从G中去掉c条边才能使G变为非连通图，则c称为G的连通度(connectivity)。,研究连通度的意义,假设我们用图来表示一个局域网：顶点表示
30、局域网中的计算机，边表示计算机之间的物理连接。则，连通度在一定程度上表示该局域网的可靠程度。假设我们用图来表示一个交通网络：顶点表示城市，边表示城市之间的公路。则，连通度在一定程度上表示该交通网络的抗阻塞能力。,计算连通度的算法,计算图连通度的确定性算法是基于网络流(network flow)的方法。该算法复杂，而且效率低。目前，计算图连通度常用算法是一种随机算法。和确定性的算法相比，该方法不仅简单，而且效率较高。,计算连通度的随机性算法,connectivity(G)/G=(V, E)while(|V|2)choose an edge (x, y) at random in G;/在G中随机选择一条边(x, y)contract (x, y);/聚合边(x, y)return |E|;,分析,给定一个图G = (V, E)，重复执行connectivity(G) kn2次之后，算法“出错”的概率小于(1/e)k (其中n为图G的顶点数，e为自然对数的底)。Nick Harvey: “The Best Algorithms are Randomized Algorithms” University of Waterloo, 2010.,总结,基于随机性的方法是计算机领域中常用的解决问题的方法。我们列举了随机性在以下几个方面的应用：设计协议、数论、密码学、数据通信、图论。,
