1、8.1 确定性多项式时间 8.2 非确定多项式时间 8.3 概率多项式时间 8.4 多项式时间不可区分性 习题 8.1 确定性多项式时间确定性多项式时间8.1.1 算法效率分析算法效率分析所谓算法(Algorithm)即是在有限步骤内求解某一问题所使用的一组定义明确的规则。前面章节中已经介绍了许多算法，但未对其做详细的效率分析。本节主要给出衡量算法效率的方法，它是后续几节的基础。定义定义8.1.1 复杂度(Complexity)一般而言，分析某算法的效率存在如下两个指标：(1)时间复杂度(Time Complexity)，该算法完全运行所需运算时间的多少。(2)空间复杂度(Space Comp
2、lexity)，该算法完全运行所需存储空间的大小。在理论和实际中，由于使用者更关心问题解决的快慢，因此时间复杂度更为重要。随着技术的发展，存储设备的价格不断下降，对空间复杂度的关注也越来越小。衡量时间复杂度的最“精确”也最原始的办法是在某台计算机上执行算法，经过测量后得到关于它的评价。但这种时间复杂度的测试与具体机器有关，不同的计算机有不同的性能和结构，测量值自然不同。即便在同一台计算机上，算法的每次执行时间也会有一些偏差。为此，对时间复杂度的渐进分析是必要的，通常采用阶(Order)的概念来描述时间复杂度。例例8.1 插入排序效率分析/这段程序对int型数组a进行插入排序，数组长度为n。fo
3、r(int i=0;i=0)&(tempaj);j-)aj+1=aj;aj+1=temp;显然每一次循环的程序步数最少是4，最多是2i+4。整个程序在最好情况下需要执行4n次，在最坏情况下需要执行次。计算出其上下界可了解该算法的执行时间。假定该算法有5次插入操作，并且假设这几次实际的程序步数分别为4，4，6，10，8。那么，该操作序列的实际程序步数为4+4+6+10+8=32。该指标和上下界有一定的差距，而复杂的算法时间复杂度变化可能相当大。为描述输入数据导致的时间复杂度差异，可用平均时间复杂度来描述，设算法需要执行i步出现的概率为pi，则平均时间复杂度为。120(24)3niinn1*nii
4、pi与此对应，渐近时间复杂度存在最好情况、最坏情况和平均情况三种度量指标。最坏情况下的渐进时间复杂度分析由Hopcroft和Tarjan最先应用于实际问题，其目的是为算法分析给出一个不依赖于具体硬件的定量方法。定义定义8.1.2 渐进记号(Asymptotic Notation)假定f()、g()均为非负函数，定义域均为N。问题的输入规模为n，为描述渐进复杂度中的阶，定义如下记号：O：当且仅当c，n0，n(nn0f(n)cg(n)，称f(n)=O(g(n)。：当且仅当c，n0，n(nn0f(n)cg(n)，称f(n)=(g(n)。：当且仅当f(n)=O(g(n)与f(n)=(g(n)，称f(n
5、)=(g(n)。通常分析的是时间的渐进复杂度，需要估计出t(n)=O(tasymptotic(n)。O记号经常被采用(Paul Bachmann于1894年引入)，因为它指出了算法时间的上界，也较好估算。更为精确的大多时候较难计算，较少采用。此外，O记号仅表示函数的上界，它不意味着最坏情况，各种情况下均有此记号。一般而言，各种阶的增长速度不同，输入规模增大时，增长速度慢的阶可认为是快速算法。常用的阶按照增长速度递增排序为O(c)，O(logn)，O(n)，O(n logn)，O(n2)，O(2n)，O(n!)，O(nn)其中，O(c)一般写为O(1)，它是理论上的最佳算法；O(n)称为线性算法
6、，它是实际中常见的最好算法；而O(nn)是最差算法，相当于穷举搜索。定义定义8.1.3 有效算法(Efficient Algorithm)多项式算法是有效算法，即时间复杂度为O(nk)(kN)的算法是有效算法。例例8.2 素性测试(Primality Test)最坏情况下的时间复杂度。/最原始的素性测试程序bool PrimeQ(int x)int i=2;bool isPrime=true;/假定该数为素数 if(x=1)isPrime=false;else while(ix)&isPrime)if(x%i=0)isPrime=false;+i;return isPrime;/返回值为该数是
7、否是素数在最坏情况下，程序运行cx次，但它不是线性算法，其原因是该问题的输入规模不随x的增长而线性增长。事实上，在计算机中采用二进制表示整数，当x为大整数时，以长度为logx的二进制序列表示之。若记n=logx，则该程序的时间复杂度为O(2n)，因此该算法是指数算法，并非有效算法。8.1.2 问题的难度问题的难度对于某个问题而言，需要对其难度进行描述。一个自然的想法是：该问题若存在有效算法解决，则可认为它是较“简单”的问题，反之则可认为它是较“困难”的问题。例例8.3 排序问题的难度。元素的排序问题可用堆排序(HeapSort)解决，最坏情况下的时间复杂度为O(n logn)。注意到O(n l
8、ogn)也是O(n2)，可知堆排序算法是有效算法，进而可认为排序问题是较“简单”的问题。事实上，基于比较方法的排序算法时间下界是(n logn)，堆排序也是解决排序问题的最好算法之一。为引入更一般的定义，需要介绍图灵机(Turing Machine，TM)的概念，引入它的主要目的是形式化给出“计算”(Computation)的模型。当然，计算模型不只TM一种，演算、递归函数等都是计算模型，它们相互等价。计算理论领域对此有一个普遍被接受的论题，即著名的Church-Turing论题。Church-Turing论题：直观上可计算的函数类就是TM(以及任意与TM等价的计算模型)可计算的函数类。讨论计
9、算模型时，首先要对计算进行抽象。A.M.Turing仔细研究了人类进行计算的过程，他把人类的计算抽象成计算者、笔、纸三个基本要素。Turing认为只要存在这三个要素，即可模拟计算的全过程。假定存在某个旁观者，他不认识计算者所采用的符号，以他所看到的过程为模拟。旁观者认为计算者一直在进行两种类型的操作：在纸上书写某些符号和把笔移动到纸上某位置。计算者采用的符号类型是有限的，他每次书写的符号可由纸上的现有符号和他自身的状态决定。事实上，旁观者观察到的过程即是抽象化的计算过程。为方便以后的讨论，Turing进一步把纸简化成一条无限长的纸带，该纸带由无限方格组成。计算者每次只能移动纸带或者改变某方格内
10、的符号，并且他每一时刻只能处于某一特定状态，状态的变化就是计算者行为的抽象。上面给出的这种简单的TM是确定性的，即确定型图灵机(Deterministic Turing Machine，DTM)，如图8-1所示。DTM在给定输入数据后，其后它每一步的动作即可完全确定。每一时刻的DTM可用格局(Configuration)来描述，它包括纸带的内容、读写头的位置和控制器的状态。图8-1 确定型图灵机定义定义8.1.4 确定型图灵机 一台DTM由如下要素组成：(1)符号表：由有限个符号组成，包括标识空白的特殊字符*。(2)可双向移动的无限长纸带：该纸带由无限个方格组成，方格上的符号均属于，除了有限个
11、方格外，其他方格上的符号均为*。(3)读写头：可在任一时刻对某个确定的方格进行操作。此读写头可向左()或向右()移动。(4)控制器：它携带状态集，包括特定的起始状态0和停机状态集。DTM的计算可由转移函数(Transition Function)决定：:，若控制器当前状态为n且读写头指向方格内容为n，转移函数(n，n)可完成如下工作：(1)若n，则计算停止(也称停机)，否则确定控制器的下一步状态n+1；(2)修改读写头指向方格内容，将其改为n+1；(3)确定读写头移动的方向，要么向左()，要么向右()。确定型图灵机模型易于理解：输入固定的程序和数据(此处隐含了冯诺依曼结构中不区分程序和数据的思
12、想)，然后DTM按照输入完全确定性地运行。不过DTM的构造相当复杂，在实际中往往采用更接近现实计算机的模型如RASP、RAM等，它们均与DTM等效，此处不再赘述。一般而言，DTM如果停机，运行结果只能是两种：接受或不接受，于是停机状态集可划分为接受状态集与不接受状态集。接受格局(Accepting Configuration)意味着DTM停机时，控制器状态属于。称DTM不接受该输入就是控制器状态属于。于是DTM可等价于一台能回答问题的机器,接受输入数据计算后仅可回答Yes或No。DTM是否停机属于可计算性(Computability)领域所研究的问题，可参阅相关书籍。表面上，DTM只能以停机来
13、表示接受输入的程序和数据，它如何能和日常使用的计算机等价呢，这需要引入判定问题(Decision Problem)。所谓判定问题，是指问题的答案仅有Yes或No。若该问题存在有效算法当且仅当其对应的判定问题存在有效算法，最优化问题均可转化为对应的判定问题。TYFNYN例例8.4 最短路径问题的判定问题。仅考虑路径长度均为非负整数的情况。定义判定问题为“是否存在长度小于等于L的路径？”容易计算出路径长度的上界M，于是可对L从0开始递增直到M，给出一系列判定问题。解决每个判定问题，直到找到某个回答为Yes的L，该值即为所求最短路径。利用此判定问题可解决最短路径问题。对于一般的问题，可先将该问题转换
14、成判定问题，然后利用DTM回答的答案解决之。密码学中大量涉及的是离散优化问题，它们均可以转换成相应的判定问题，本章中的问题大部分为判定问题。一个粗略的结论是：DTM的计算能力与日常使用的计算机等效。DTM的输入称为语言(Language)，了解DTM的定义后，可给出较“简单”问题的定义。定义定义8.1.5 P 确定型图灵机上的具有有效算法的判定问题之集合。从另一个角度看，DTM是有效算法的模型表示：任何确定性有效算法均可由DTM实现，且可以在多项式时间内运行。这就是多项式时间Church-Turing论题(The Polynomial-time Church-Turing Thesis)。通过
15、对DTM的讨论，可知DTM代表了计算的能力，于是问题的难度即可定义为：若某问题存在有效算法，则称之为易解(Tractable)的；如果它不存在多项式算法，则称它是难解的(Intractable)。该定义等价于：L是易解的当且仅当LP。这就是著名的Cook-Karp论题。例例8.5 素性测试问题属于P。2002年6月印度理工学院(Indian Institute of Technology，Kanpur)的Manindra Agrawal、Neeraj Kayal和Nitin Saxena发表了题为“PRIMES is in P”的论文，随后经过修改，在2004年的Annals of Mathe
16、matics上发表了修正后的“PRIMES is in P”。他们提出了一个确定性多项式算法，现在被命名为AKS算法或Agrawal-Kayal-Saxena算法。AKS算法短小精悍，极漂亮地解决了素性测试问题。8.2 非确定多项式时间非确定多项式时间如果所有的问题都存在有效算法，那么密码即无存在的价值，因为破译密码可以通过有效算法轻易解决。事实上，大多数问题目前还未发现有效算法。这些“未解决”问题中有一个巨大的问题子集，它们拥有共同的特点，即对于这些问题的正确答案能在多项式时间内验证。一个最简单的例子就是判定某数是否是合数，如果有人声称找到了其约数，可以在多项式时间内验证之。计算机科学和密码
17、学中可找到许多类似的问题，它们的集合称之为NP。当然也有大量问题是超出NP的。输出全排列是典型的例子，该问题属于PSPACE(Polynomial Space)。容易验证P是NP的子集，但P是否是NP的真子集呢？此问题被称为“P=NP?”问题，它是计算复杂性领域乃至于整个理论计算机科学的焦点问题。(注意：了解P的定义后，常有人认为NP是Non-Polynomial的缩写。事实上，这里的N是“非确定性”(Non-deterministic)的缩写。如果NP是Non-Polynomial，有关“P=NP?”的讨论也将不复存在。)例例8.6 可满足性问题(Boolean Satisfiability
18、)。给定某布尔表达式，是否存在某一组对其变量的真假赋值，使得该布尔表达式为真。此问题可在多项式内验证，所以它是NP问题。例如S=(p1p2)p3)，需判断p1、p2、p3在何种赋值下可使S为真。当p1、p2、p3分别为1、0、1情况下，可使S为真，易知该验证算法为有效算法。目前给出的解决可满足性问题的算法均为指数算法，其上界为O(2n)。这些算法的基本思路均为回溯(BackTracking)。可满足性问题最简单的蛮力算法如图8-2所示。图 8-2 可满足性问题的蛮力算法该算法从根结点开始进行搜索，分别给p1、p2、p3赋值为0或1，搜索每个可能的结点(可剪去某些不可能的子树)，最终得到是否可满
19、足。为介绍NP，下面简要描述关于非确定型图灵机(Non-deterministic Turing Machine，NTM)的概念，这里并不给出其精确定义，仅给出它的两种直观的解释。解释解释1 NTM在进行计算的时候，会自动选择最优路径进行计算。在上面的可满足性问题中，可假定NTM拥有一个具有预测能力的神奇硬币，根据它抛掷后的结果进行选择：正面提示下一步该选择1，而反面则选择0。这样在NTM进行计算的时候，它会提示给p1、p2、p3赋值1、0、1。这样可利用此解答来验证出其可满足性。解释解释2 NTM进行计算时，碰到需要选择的分支，则对自身进行复制，每个分支分配一个副本进行计算，这样也只需要多项
20、式时间即可判定其可满足性。显然NTM的计算能力极强，远远超出目前计算机的能力。它不可能对应通常意义上的算法，更不可能在目前的实际计算中实现。定义定义8.2.1 NP 非确定型图灵机上的存在有效算法的判定问题之集合。从此定义可看出NP问题的本质不是多项式时间内可验证，而是在NTM上可找到有效算法。这意味着如果有相当“智能”的信息引导，有望对其获得突破，即能在DTM上找到有效算法，这是多数组合优化问题均不可回避的难点。如果不用NTM进行描述，还可以仅从判定问题的角度来认识NP。这样，P问题是指能够在多项式时间求解的判定问题，而NP问题则是指那些其“肯定解”(回答为是)能够在给定的正确信息下在多项式
21、时间内验证的判定问题。前面的可满足性问题目前仅能找到指数级的算法，很自然的问题就是它存在有效算法，目前的回答是不确定。除此之外，还有一大批NP问题，目前既找不到有效算法，又不能确定它不存在有效算法。这类问题具有非常特殊的性质，即如果其中一个存在有效算法，那么此类问题均存在有效算法，这类问题统称为NP完全(NP-Complete，NPC)问题。Cook于1971年给出了第一个NPC问题，即可满足性问题。此后，大量NPC问题被发现，对它们的研究集中在寻找有效算法上，如果在其中一个问题上取得突破，那么NPC问题全部存在有效算法，并可确定P=NP。不过，大多数学者认为NPC问题不存在有效算法，也即假定
22、NPC问题是难解的。图8-3给出了在此假设下NP中各类问题的关系。图 8-3 NP中各类问题的关系密码学家根据NPC问题是难解的假设，设计了相当多的加密体制。这些体制主要利用单向函数(One Way Function)的思想，原理是该类函数正向计算存在有效算法，对其反向计算是难解问题。基于单向函数思想的典型例子有ElGamal加密体制(基于离散对数问题)、Rabin加密体制(基于Rabin函数)等，前面的章节中已有详细的介绍。一般而言，基于NPC问题设计的加密体制比较安全。值得注意的是，某些基于NPC问题设计的加密体制不甚安全，已经被攻破。例例8.7 MerkleHellman加密体制(Cry
23、ptosystem)。它是最早提出的公钥密码体制，其本质是背包加密算法。该方法基于子集和问题(Subset Sum Problem)，所谓子集和问题是：对于一个由正整数组成的集合和某个给定的数Sum，是否存在该集合的某个子集，其元素之和恰好等于Sum。子集和问题是NPC问题，从表面上看该体制很安全。1982年Shamir利用LenstraLenstraLovsz(L3)格基约简(Lattice Basis Reduction)算法破解了Merkle-Hellman 加密体制。不过Merkle-Hellman加密体制的加密和解密速度很快，尽管它已被破解，但依然有其价值。需要指出，此问题的解决不等
24、于NPC问题存在有效算法。此外，有些加密算法所采用的NP问题虽然未被肯定是NPC问题，但在实践上得到了良好的应用。RSA算法即是一个典型的例子，目前对其尚无有效算法破解。8.3 概率多项式时间概率多项式时间NPC问题目前虽然尚无有效算法，但该类问题在实际中经常出现，于是提出了两类算法来部分的解决：概率算法(Probabilistic Algorithm，也称随机算法Randomized Algorithm)与近似算法(Approximation Algorithm)。密码学中经常用到概率算法，如何判定其优劣，这是本节所讨论的问题。NTM从本质上可认为是从不犯错的机器，它总能找到正确的路径。而人
25、在预测中总会犯一定的错误，不同的人犯错误的可能性不同。一般来说，经验丰富的人犯的错误少，没有经验的人犯的错误多，这种现象可用他们犯错误的概率定量描述。定义定义8.3.1 概率图灵机(Probabilistic Turing Machine，PTM)是一台总停机的NTM，它的每个当前格局至多有两个后续格局，从当前格局等可能的到达其中之一。PTM停机的状态有三种：接受、不接受和未知。如果PTM停机在未知状态，则称该计算无效。如果PTM是多项式界限且没有未知状态，则称该机为PP机(Probabilistic Polynomial-time Machine)，它能接受的语言类称为PP。PP机满足两类概
26、率的界限：(1)输入I属于语言L时，PTM识别该输入属于语言L的概率，这是一种正确概率：PrPTM recognizes IL|ILC(2)输入I不属于语言L时，PTM识别该输入属于语言L的概率，这是一种错误概率：PrPTM recognizes IL|ILE理想情况下，C应当较大，E应当较小。为此规定两类界限分别满足112C102E如果改变界限为，则PTM为BPP机(Bounded Probabilistic Polynomial-time Machine)，所接受的语言类为BPP。为了提高PTM的准确性，可将同一输入多次交于PTM执行。对其重复执行n次，若识别次数达到以上，则认为该输入可识
27、别。采用重复执行的方案后，可证明Prmajor of PTMs recognize IL|IL1Prmajor of PTMs recognize IL|I L0210121EC和12n这两个极限表明，如果运行次数足够多，便能得到接近于正确的结果。值得注意的是，运行次数越多，PrPTM recognizes IL|IL越高，PrPTM recognizes IL|IL越低，此种算法的性能可用于解决实际问题。此外，可证明两类界限若为1/2，两类概率则不能达到上面的极限。事实上，概率为1/2相当于随机猜测，没有任何经验知识支持，当然不能成功。据此可给出一般意义下有效算法的定义。定义定义8.3.2
28、广义的有效算法 在DTM或PP机下的多项式算法是有效算法。如果能找到这种意义下的有效算法用于密码破解，那么这种攻击也是相当有效的。由于概率算法的特殊性，决定了衡量它的指标不仅是效率，还必须从正确率的角度考察。这些指标均可从其运作机理考察。由于该方案仅讨论接受的次数，易知PrPTM recognizes IL|IL越大，所需要重复运行的次数越少，这意味着该算法速度快。而PrPTM recognizes IL|IL越小，表明被PTM接受的计算中犯错的几率越小，这意味着该算法的正确率高。依此可对概率算法做如下分类。定义定义8.3.3 Monte Carlo算法 满足下列特点的概率算法：PrPTM r
29、ecognizes IL|IL=1PrPTM recognizes IL|ILE这种算法的速度最快，但会犯一定的错误。它对应复杂性类PP(Monte Carlo)。例例8.8 素性测试的一个随机算法。bool PrimeQ(int x)int i=0;int L=logx/log 2;int temp;bool isPrime=true;/假定该数为素数 bool tag=false;if(x=1)isPrime=false;else while(i1|(temp%x)!=1&temp%x)!=x-1)isPrime=false;+i;if(!tag)isPrime=false;return
30、isPrime;/返回值为该数是否是素数可证明该算法属于Monte Carlo算法。从此程序中也可看出，Monte Carlo算法测试的范围广，验证手段较简单，因此速度快但易犯错误。定义定义8.3.4 Las Vegas算法 满足下列特点的概率算法：PrPTM recognizes IL|ILCPrPTM recognizes IL|IL=0这种算法几乎完全正确，但速度较慢。它对应复杂性类PP(Las Vegas)。例例8.9 素性测试的另一个随机算法。int PrimeQ(int x，int q，int k)/数组q存放着所有x-1的素因子，长度为k int i=0;int L=logx;i
31、nt temp;int isPrime=1;/假定该数为素数 bool Decision=true;任取(1,x)内的随机数r;if(x=1)isPrime=false;else while(ik)Decision)if(pow(x-1)，qi%x)!=1)Decision=false;+i;if(!Decision)isPrime=2;/返回值为不确定 else if(pow(r，x-1)%x)!=1)isPrime=0;/该数为合数 return isPrime;/返回值为该数是否是素数或不确定可证明该算法属于Las Vegas算法。从此程序中也可看出，Las Vegas算法测试的范围较窄
32、，验证手段较多，因而正确率高但速度稍慢。定义定义8.3.5 Zero-sided-error算法 满足下列特点的概率算法：PrPTM recognizes IL|IL=1PrPTM recognizes IL|I L=0Zero-sided-error算法较为特殊，它的速度最快，也几乎完全正确。Zero-sided-error算法对应复杂性类ZPP，从定义上可知ZPP是PP(Monte Carlo)与PP(Las Vegas)的交集。这些复杂性类之间满足如下关系：PPBPPVegas)pp(LasCarlo)PP(MonteZPPP8.4 多项式时间不可区分性多项式时间不可区分性某些加密体制虽
33、然暂时不存在有效算法破解，但这并不意味着它们是安全的。如果某人截获密文后伪造之再予以发送，这种破坏力也是相当大的。对付这种攻击，需要有效的辨认方法。更重要的是，在零知识证明和交互证明中，辨认或者验证是必需的。为此，本节简要介绍多项式时间不可区分性。给定样本空间S，所含样本数为|S|，对其进行编码，长度最多为l=log|S|。若有两个随机序列集合A=a1，a2，a3，和B=b1，b2，b3，则需要判断语言来自哪个随机序列集合。一个自然的判断方法是要求对方给出一串序列R，辨认者对其进行辨认进而做出判断。为保证算法的有效性，序列长度不得超过某个多项式P(l)，辨认算法也必须是有效算法。给出两类条件概
34、率的定义：当序列R来自集合A时，辨认者判断该序列来自A的概率记为PrA|RA，辨认者判断该序列来自B的概率记为PrB|RA；当序列R来自集合B时，辨认者判断该序列来自A的概率记为PrA|RB，辨认者判断该序列来自B的概率记为PrB|RB。若PrA|RA和PrB|RA相差较大，可认为当序列R来自集合A时，辨认者的判断基本正确。若PrA|RB和PrB|RB相差较大，可认为当序列R来自集合B时，辨认者的判断基本正确。根据这两类条件概率的差异，可给出判断标准为diff=min|PrA|RA-PrB|R A|，|PrA|R B-PrB|R B|显然diff与输入规模l有关，若对相当大的M，可认为辨认者可
35、做出有效的判断，这种多项式时间内完成的辨认称之为有效辨认。在实际中，只需要求对相当大的M，diff不至于可以忽略即可。0diffinfMl定义定义8.4.1 多项式时间不可区分性(Polynomial-time Indistinguishability)给定输入规模l和随机序列集合A=a1，a2，a3，和B=b1，b2，b3，若不存在对它们的有效辨认，则称A、B多项式时间不可区分。在计算复杂性领域，一个被广泛接受的假设是：存在多项式时间不可区分的随机序列集合。其特例是伪随机序列和真实随机序列的多项式时间不可区分性，即存在伪随机序列产生器，它产生的伪随机序列和真实随机序列是多项式时间不可区分的。这个假设相当有用，密码学中的许多判断均基于此。习习 题题1.若插入排序算法中程序执行的步数呈等概率分布，讨论平均情况下该算法的时间复杂度。2.修改例8.2的素性测试，若将结束循环的上界改成，证明该算法依然是指数算法。3.考虑路径长度均为非负实数的情况，找出最短路径问题对应的判定问题，并用它解决最短路径问题。*4.证明例8.7是Monte Carlo算法。*5.证明例8.8是Las Vegas算法。x
