8.1確定性多項式時間8.2非確定多項式時間8.3概率多項式時間8.4多項式時間不可區(qū)分性習題8.1確定性多項式時間8.1.1算法效率分析所謂算法(Algorithm)即是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。前面章節(jié)中已經(jīng)介紹了許多算法，但未對其做詳細的效率分析。本節(jié)主要給出衡量算法效率的方法，它是后續(xù)幾節(jié)的基礎。定義8.1.1

復雜度(Complexity)一般而言，分析某算法的效率存在如下兩個指標：

(1)時間復雜度(TimeComplexity)，該算法完全運行所需運算時間的多少。

(2)空間復雜度(SpaceComplexity)，該算法完全運行所需存儲空間的大小。在理論和實際中，由于使用者更關(guān)心問題解決的快慢，因此時間復雜度更為重要。隨著技術(shù)的發(fā)展，存儲設備的價格不斷下降，對空間復雜度的關(guān)注也越來越小。

衡量時間復雜度的最“精確”也最原始的辦法是在某臺計算機上執(zhí)行算法，經(jīng)過測量后得到關(guān)于它的評價。但這種時間復雜度的測試與具體機器有關(guān)，不同的計算機有不同的性能和結(jié)構(gòu)，測量值自然不同。即便在同一臺計算機上，算法的每次執(zhí)行時間也會有一些偏差。為此，對時間復雜度的漸進分析是必要的，通常采用階(Order)的概念來描述時間復雜度。

例8.1

插入排序效率分析

//這段程序?qū)nt型數(shù)組a進行插入排序，數(shù)組長度為n。

for(inti=0;i<n;i++)

{

//每次把a［i］插入到已經(jīng)排好序的a［0］,a［1］,...,a［i-1］中

inttemp=a［i］;

intj;

for(j=i-1;(j>=0)&&(temp<a［j］);j--)

a［j+1］=a［j］;

a［j+1］=temp;

}顯然每一次循環(huán)的程序步數(shù)最少是4，最多是2i+4。整個程序在最好情況下需要執(zhí)行4n次，在最壞情況下需要執(zhí)行次。計算出其上下界可了解該算法的執(zhí)行時間。

假定該算法有5次插入操作，并且假設這幾次實際的程序步數(shù)分別為4，4，6，10，8。那么，該操作序列的實際程序步數(shù)為4+4+6+10+8=32。該指標和上下界有一定的差距，而復雜的算法時間復雜度變化可能相當大。為描述輸入數(shù)據(jù)導致的時間復雜度差異，可用平均時間復雜度來描述，設算法需要執(zhí)行i步出現(xiàn)的概率為pi，則平均時間復雜度為。與此對應，漸近時間復雜度存在最好情況、最壞情況和平均情況三種度量指標。

最壞情況下的漸進時間復雜度分析由Hopcroft和Tarjan最先應用于實際問題，其目的是為算法分析給出一個不依賴于具體硬件的定量方法。

定義8.1.2

漸進記號(AsymptoticNotation)假定f(·)、g(·)均為非負函數(shù)，定義域均為N。問題的輸入規(guī)模為n，為描述漸進復雜度中的階，定義如下記號：

O：當且僅當c，n0，n(n≥n0→f(n)≤c×g(n))，稱f(n)=O(g(n))。

Ω：當且僅當c，n0，n(n≥n0→f(n)≥c×g(n))，稱f(n)=Ω(g(n))。

Θ：當且僅當f(n)=O(g(n))與f(n)=Ω(g(n))，稱f(n)=Θ(g(n))。

通常分析的是時間的漸進復雜度，需要估計出t(n)=O(tasymptotic(n))。O記號經(jīng)常被采用(PaulBachmann于1894年引入)，因為它指出了算法時間的上界，也較好估算。更為精確的Θ大多時候較難計算，較少采用。此外，O記號僅表示函數(shù)的上界，它不意味著最壞情況，各種情況下均有此記號。一般而言，各種階的增長速度不同，輸入規(guī)模增大時，增長速度慢的階可認為是快速算法。常用的階按照增長速度遞增排序為

O(c)，O(logn)，O(n)，O(nlogn)，O(n2)，O(2n)，O(n!)，O(nn)其中，O(c)一般寫為O(1)，它是理論上的最佳算法；O(n)稱為線性算法，它是實際中常見的最好算法；而O(nn)是最差算法，相當于窮舉搜索。

定義8.1.3

有效算法(EfficientAlgorithm)多項式算法是有效算法，即時間復雜度為O(nk)(k∈N)的算法是有效算法。

例8.2

素性測試(PrimalityTest)最壞情況下的時間復雜度。

//最原始的素性測試程序

boolPrimeQ(intx)

{

inti=2;

boolisPrime=true;//假定該數(shù)為素數(shù)

if(x<=1)

isPrime=false;

else

while((i<x)&&isPrime)

{

if(x%i==0)

isPrime=false;

++i;

}

returnisPrime;//返回值為該數(shù)是否是素數(shù)

}在最壞情況下，程序運行cx次，但它不是線性算法，其原因是該問題的輸入規(guī)模不隨x的增長而線性增長。事實上，在計算機中采用二進制表示整數(shù)，當x為大整數(shù)時，以長度為

［logx］的二進制序列表示之。若記n=［logx］，則該程序的時間復雜度為O(2n)，因此該算法是指數(shù)算法，并非有效算法。8.1.2問題的難度

對于某個問題而言，需要對其難度進行描述。一個自然的想法是：該問題若存在有效算法解決，則可認為它是較“簡單”的問題，反之則可認為它是較“困難”的問題。

例8.3

排序問題的難度。

元素的排序問題可用堆排序(HeapSort)解決，最壞情況下的時間復雜度為O(nlogn)。注意到O(nlogn)也是O(n2)，可知堆排序算法是有效算法，進而可認為排序問題是較“簡單”的問題。事實上，基于比較方法的排序算法時間下界是Ω(nlogn)，堆排序也是解決排序問題的最好算法之一。為引入更一般的定義，需要介紹圖靈機(TuringMachine，TM)的概念，引入它的主要目的是形式化給出“計算”

(Computation)的模型。

當然，計算模型不只TM一種，λ演算、遞歸函數(shù)等都是計算模型，它們相互等價。計算理論領域?qū)Υ擞幸粋€普遍被接受的論題，即著名的Church-Turing論題。

Church-Turing論題：直觀上可計算的函數(shù)類就是TM(以及任意與TM等價的計算模型)可計算的函數(shù)類。討論計算模型時，首先要對計算進行抽象。A.M.Turing仔細研究了人類進行計算的過程，他把人類的計算抽象成計算者、筆、紙三個基本要素。Turing認為只要存在這三個要素，即可模擬計算的全過程。假定存在某個旁觀者，他不認識計算者所采用的符號，以他所看到的過程為模擬。旁觀者認為計算者一直在進行兩種類型的操作：在紙上書寫某些符號和把筆移動到紙上某位置。計算者采用的符號類型是有限的，他每次書寫的符號可由紙上的現(xiàn)有符號和他自身的狀態(tài)決定。事實上，旁觀者觀察到的過程即是抽象化的計算過程。為方便以后的討論，Turing進一步把紙簡化成一條無限長的紙帶，該紙帶由無限方格組成。計算者每次只能移動紙帶或者改變某方格內(nèi)的符號，并且他每一時刻只能處于某一特定狀態(tài)，狀態(tài)的變化就是計算者行為的抽象。上面給出的這種簡單的TM是確定性的，即確定型圖靈機(DeterministicTuringMachine，DTM)，如圖8-1所示。DTM在給定輸入數(shù)據(jù)后，其后它每一步的動作即可完全確定。每一時刻的DTM可用格局(Configuration)來描述，它包括紙帶的內(nèi)容、讀寫頭的位置和控制器的狀態(tài)。圖8-1確定型圖靈機

定義8.1.4

確定型圖靈機一臺DTM由如下要素組成：

(1)符號表Σ：Σ由有限個符號組成，包括標識空白的特殊字符*。

(2)可雙向移動的無限長紙帶：該紙帶由無限個方格組成，方格上的符號均屬于Σ，除了有限個方格外，其他方格上的符號均為*。

(3)讀寫頭：可在任一時刻對某個確定的方格進行操作。此讀寫頭可向左(←)或向右(→)移動。

(4)控制器：它攜帶狀態(tài)集Γ，包括特定的起始狀態(tài)γ0和停機狀態(tài)集。

DTM的計算可由轉(zhuǎn)移函數(shù)(TransitionFunction)決定：

δ:?！力病！力病羬←，→}若控制器當前狀態(tài)為γn且讀寫頭指向方格內(nèi)容為σn，轉(zhuǎn)移函數(shù)δ(γn，σn)可完成如下工作：

(1)若γn∈，則計算停止(也稱停機)，否則確定控制器的下一步狀態(tài)γn+1；

(2)修改讀寫頭指向方格內(nèi)容，將其改為σn+1；

(3)確定讀寫頭移動的方向，要么向左(←)，要么向右(→)。

確定型圖靈機模型易于理解：輸入固定的程序和數(shù)據(jù)(此處隱含了馮·諾依曼結(jié)構(gòu)中不區(qū)分程序和數(shù)據(jù)的思想)，然后DTM按照輸入完全確定性地運行。不過DTM的構(gòu)造相當復雜，在實際中往往采用更接近現(xiàn)實計算機的模型如RASP、RAM等，它們均與DTM等效，此處不再贅述。一般而言，DTM如果停機，運行結(jié)果只能是兩種：接受或不接受，于是停機狀態(tài)集可劃分為接受狀態(tài)集

與不接受狀態(tài)集。接受格局(AcceptingConfiguration)意味著DTM停機時，控制器狀態(tài)屬于。稱DTM不接受該輸入就是控制器狀態(tài)屬于。于是DTM可等價于一臺能回答問題的機器,接受輸入數(shù)據(jù)計算后僅可回答Yes或No。DTM是否停機屬于可計算性(Computability)領域所研究的問題，可參閱相關(guān)書籍。

表面上，DTM只能以停機來表示接受輸入的程序和數(shù)據(jù)，它如何能和日常使用的計算機等價呢，這需要引入判定問題(DecisionProblem)。所謂判定問題，是指問題的答案僅有Yes或No。若該問題存在有效算法當且僅當其對應的判定問題存在有效算法，最優(yōu)化問題均可轉(zhuǎn)化為對應的判定問題。例8.4

最短路徑問題的判定問題。

僅考慮路徑長度均為非負整數(shù)的情況。定義判定問題為“是否存在長度小于等于L的路徑？”容易計算出路徑長度的上界M，于是可對L從0開始遞增直到M，給出一系列判定問題。解決每個判定問題，直到找到某個回答為Yes的L，該值即為所求最短路徑。利用此判定問題可解決最短路徑問題。

對于一般的問題，可先將該問題轉(zhuǎn)換成判定問題，然后利用DTM回答的答案解決之。密碼學中大量涉及的是離散優(yōu)化問題，它們均可以轉(zhuǎn)換成相應的判定問題，本章中的問題大部分為判定問題。一個粗略的結(jié)論是：DTM的計算能力與日常使用的計算機等效。DTM的輸入稱為語言(Language)，了解DTM的定義后，可給出較“簡單”問題的定義。定義8.1.5P確定型圖靈機上的具有有效算法的判定問題之集合。

從另一個角度看，DTM是有效算法的模型表示：任何確定性有效算法均可由DTM實現(xiàn)，且可以在多項式時間內(nèi)運行。這就是多項式時間Church-Turing論題(ThePolynomial-timeChurch-TuringThesis)。

通過對DTM的討論，可知DTM代表了計算的能力，于是問題的難度即可定義為：若某問題存在有效算法，則稱之為易解(Tractable)的；如果它不存在多項式算法，則稱它是難解的(Intractable)。該定義等價于：L是易解的當且僅當L∈P。這就是著名的Cook-Karp論題。

例8.5

素性測試問題屬于P。

2002年6月印度理工學院(IndianInstituteofTechnology，Kanpur)的ManindraAgrawal、NeerajKayal和NitinSaxena發(fā)表了題為“PRIMESisinP”的論文，隨后經(jīng)過修改，在2004年的AnnalsofMathematics上發(fā)表了修正后的“PRIMESisinP”。他們提出了一個確定性多項式算法，現(xiàn)在被命名為AKS算法或Agrawal-Kayal-Saxena算法。AKS算法短小精悍，極漂亮地解決了素性測試問題。8.2非確定多項式時間如果所有的問題都存在有效算法，那么密碼即無存在的價值，因為破譯密碼可以通過有效算法輕易解決。事實上，大多數(shù)問題目前還未發(fā)現(xiàn)有效算法。這些“未解決”問題中有一個巨大的問題子集，它們擁有共同的特點，即對于這些問題的正確答案能在多項式時間內(nèi)驗證。一個最簡單的例子就是判定某數(shù)是否是合數(shù)，如果有人聲稱找到了其約數(shù)，可以在多項式時間內(nèi)驗證之。計算機科學和密碼學中可找到許多類似的問題，它們的集合稱之為NP。當然也有大量問題是超出NP的。輸出全排列是典型的例子，該問題屬于PSPACE(PolynomialSpace)。容易驗證P是NP的子集，但P是否是NP的真子集呢？此問題被稱為“P=NP?”問題，它是計算復雜性領域乃至于整個理論計算機科學的焦點問題。(注意：了解P的定義后，常有人認為NP是Non-Polynomial的縮寫。事實上，這里的N是“非確定性”(Non-deterministic)的縮寫。如果NP是Non-Polynomial，有關(guān)“P=NP?”的討論也將不復存在。)

例8.6

可滿足性問題(BooleanSatisfiability)。

給定某布爾表達式，是否存在某一組對其變量的真假賦值，使得該布爾表達式為真。此問題可在多項式內(nèi)驗證，所以它是NP問題。

例如S=((p1∨p2)∧p3)，需判斷p1、p2、p3在何種賦值下可使S為真。當p1、p2、p3分別為1、0、1情況下，可使S為真，易知該驗證算法為有效算法。

目前給出的解決可滿足性問題的算法均為指數(shù)算法，其上界為O(2n)。這些算法的基本思路均為回溯(BackTracking)?？蓾M足性問題最簡單的蠻力算法如圖8-2所示。圖8-2可滿足性問題的蠻力算法該算法從根結(jié)點開始進行搜索，分別給p1、p2、p3賦值為0或1，搜索每個可能的結(jié)點(可剪去某些不可能的子樹)，最終得到是否可滿足。

為介紹NP，下面簡要描述關(guān)于非確定型圖靈機(Non-deterministicTuringMachine，NTM)的概念，這里并不給出其精確定義，僅給出它的兩種直觀的解釋。

解釋1NTM在進行計算的時候，會自動選擇最優(yōu)路徑進行計算。在上面的可滿足性問題中，可假定NTM擁有一個具有預測能力的神奇硬幣，根據(jù)它拋擲后的結(jié)果進行選擇：正面提示下一步該選擇1，而反面則選擇0。這樣在NTM進行計算的時候，它會提示給p1、p2、p3賦值1、0、1。這樣可利用此解答來驗證出其可滿足性。

解釋2NTM進行計算時，碰到需要選擇的分支，則對自身進行復制，每個分支分配一個副本進行計算，這樣也只需要多項式時間即可判定其可滿足性。

顯然NTM的計算能力極強，遠遠超出目前計算機的能力。它不可能對應通常意義上的算法，更不可能在目前的實際計算中實現(xiàn)。

定義8.2.1NP非確定型圖靈機上的存在有效算法的判定問題之集合。

從此定義可看出NP問題的本質(zhì)不是多項式時間內(nèi)可驗證，而是在NTM上可找到有效算法。這意味著如果有相當“智能”的信息引導，有望對其獲得突破，即能在DTM上找到有效算法，這是多數(shù)組合優(yōu)化問題均不可回避的難點。

如果不用NTM進行描述，還可以僅從判定問題的角度來認識NP。這樣，P問題是指能夠在多項式時間求解的判定問題，而NP問題則是指那些其“肯定解”(回答為是)能夠在給定的正確信息下在多項式時間內(nèi)驗證的判定問題。前面的可滿足性問題目前僅能找到指數(shù)級的算法，很自然的問題就是它存在有效算法，目前的回答是不確定。除此之外，還有一大批NP問題，目前既找不到有效算法，又不能確定它不存在有效算法。這類問題具有非常特殊的性質(zhì)，即如果其中一個存在有效算法，那么此類問題均存在有效算法，這類問題統(tǒng)稱為NP完全(NP-Complete，NPC)問題。

Cook于1971年給出了第一個NPC問題，即可滿足性問題。此后，大量NPC問題被發(fā)現(xiàn)，對它們的研究集中在尋找有效算法上，如果在其中一個問題上取得突破，那么NPC問題全部存在有效算法，并可確定P=NP。不過，大多數(shù)學者認為NPC問題不存在有效算法，也即假定NPC問題是難解的。圖8-3給出了在此假設下NP中各類問題的關(guān)系。圖8-3NP中各類問題的關(guān)系密碼學家根據(jù)NPC問題是難解的假設，設計了相當多的加密體制。這些體制主要利用單向函數(shù)(OneWayFunction)的思想，原理是該類函數(shù)正向計算存在有效算法，對其反向計算是難解問題。基于單向函數(shù)思想的典型例子有ElGamal加密體制(基于離散對數(shù)問題)、Rabin加密體制(基于Rabin函數(shù))等，前面的章節(jié)中已有詳細的介紹。

一般而言，基于NPC問題設計的加密體制比較安全。值得注意的是，某些基于NPC問題設計的加密體制不甚安全，已經(jīng)被攻破。

例8.7MerkleHellman加密體制(Cryptosystem)。

它是最早提出的公鑰密碼體制，其本質(zhì)是背包加密算法。該方法基于子集和問題(SubsetSumProblem)，所謂子集和問題是：對于一個由正整數(shù)組成的集合和某個給定的數(shù)Sum，是否存在該集合的某個子集，其元素之和恰好等于Sum。子集和問題是NPC問題，從表面上看該體制很安全。1982年Shamir利用LenstraLenstraLovász(L3)格基約簡(LatticeBasisReduction)算法破解了Merkle-Hellman加密體制。不過Merkle-Hellman加密體制的加密和解密速度很快，盡管它已被破解，但依然有其價值。需要指出，此問題的解決不等于NPC問題存在有效算法。此外，有些加密算法所采用的NP問題雖然未被肯定是NPC問題，但在實踐上得到了良好的應用。RSA算法即是一個典型的例子，目前對其尚無有效算法破解。8.3概率多項式時間

NPC問題目前雖然尚無有效算法，但該類問題在實際中經(jīng)常出現(xiàn)，于是提出了兩類算法來部分的解決：概率算法(ProbabilisticAlgorithm，也稱隨機算法RandomizedAlgorithm)與近似算法(ApproximationAlgorithm)。密碼學中經(jīng)常用到概率算法，如何判定其優(yōu)劣，這是本節(jié)所討論的問題。

NTM從本質(zhì)上可認為是從不犯錯的機器，它總能找到正確的路徑。而人在預測中總會犯一定的錯誤，不同的人犯錯誤的可能性不同。一般來說，經(jīng)驗豐富的人犯的錯誤少，沒有經(jīng)驗的人犯的錯誤多，這種現(xiàn)象可用他們犯錯誤的概率定量描述。

定義8.3.1

概率圖靈機(ProbabilisticTuringMachine，PTM)是一臺總停機的NTM，它的每個當前格局至多有兩個后續(xù)格局，從當前格局等可能的到達其中之一。PTM停機的狀態(tài)有三種：接受、不接受和未知。如果PTM停機在未知狀態(tài)，則稱該計算無效。

如果PTM是多項式界限且沒有未知狀態(tài)，則稱該機為PP機(ProbabilisticPolynomial-timeMachine)，它能接受的語言類稱為PP。PP機滿足兩類概率的界限：

(1)輸入I屬于語言L時，PTM識別該輸入屬于語言L的概率，這是一種正確概率：

Pr［PTMrecognizesI∈L|I∈L］≥δC

(2)輸入I不屬于語言L時，PTM識別該輸入屬于語言L的概率，這是一種錯誤概率：

Pr［PTMrecognizesI∈L|I

L］≤δE

理想情況下，δC應當較大，δE應當較小。為此規(guī)定兩類界限分別滿足如果改變界限為，則PTM為BPP機(BoundedProbabilisticPolynomial-timeMachine)，所接受的語言類為BPP。

為了提高PTM的準確性，可將同一輸入多次交于PTM執(zhí)行。對其重復執(zhí)行n次，若識別次數(shù)達到以上，則認為該輸入可識別。

采用重復執(zhí)行的方案后，可證明

Pr［majorofPTMsrecognizeI∈L|I∈L］→1

Pr［majorofPTMsrecognizeI∈L|I

L］→0這兩個極限表明，如果運行次數(shù)足夠多，便能得到接近于正確的結(jié)果。值得注意的是，運行次數(shù)越多，Pr［PTMrecognizesI∈L|I∈L］越高，Pr［PTMrecognizesI∈L|I

L］越低，此種算法的性能可用于解決實際問題。此外，可證明兩類界限若為1/2，兩類概率則不能達到上面的極限。事實上，概率為1/2相當于隨機猜測，沒有任何經(jīng)驗知識支持，當然不能成功。

據(jù)此可給出一般意義下有效算法的定義。

定義8.3.2

廣義的有效算法在DTM或PP機下的多項式算法是有效算法。如果能找到這種意義下的有效算法用于密碼破解，那么這種攻擊也是相當有效的。

由于概率算法的特殊性，決定了衡量它的指標不僅是效率，還必須從正確率的角度考察。這些指標均可從其運作機理考察。

由于該方案僅討論接受的次數(shù)，易知Pr［PTMrecognizesI∈L|I∈L］越大，所需要重復運行的次數(shù)越少，這意味著該算法速度快。而Pr［PTMrecognizesI∈L|I

L］越小，表明被PTM接受的計算中犯錯的幾率越小，這意味著該算法的正確率高。依此可對概率算法做如下分類。

定義8.3.3MonteCarlo算法滿足下列特點的概率算法：

Pr［PTMrecognizesI∈L|I∈L］=1

Pr［PTMrecognizesI∈L|I

L］≤δE

這種算法的速度最快，但會犯一定的錯誤。它對應復雜性類PP(MonteCarlo)。

例8.8

素性測試的一個隨機算法。

boolPrimeQ(intx)

{

inti=0;

intL=logx/log2;

inttemp;

boolisPrime=true;//假定該數(shù)為素數(shù)

booltag=false;

if(x<=1)

isPrime=false;

else

while((i<L)&&isPrime)

{

任取(1,x)內(nèi)的隨機數(shù)r;

temp=pow(r，(x-1)/2);

if((temp%x)==x-1)

tag=true; if(gcd(r，x)>1||((temp%x)!=1&&temp%x)!=x-1)

{

isPrime=false;

++i;

}

}

if(!tag)

isPrime=false;

returnisPrime;//返回值為該數(shù)是否是素數(shù)

}可證明該算法屬于MonteCarlo算法。從此程序中也可看出，MonteCarlo算法測試的范圍廣，驗證手段較簡單，因此速度快但易犯錯誤。

定義8.3.4LasVegas算法滿足下列特點的概率算法：

Pr［PTMrecognizesI∈L|I∈L］≥δC

Pr［PTMrecognizesI∈L|I

L］=0

這種算法幾乎完全正確，但速度較慢。它對應復雜性類PP(LasVegas)。

例8.9

素性測試的另一個隨機算法。

intPrimeQ(intx，intq［］，intk)

{

//數(shù)組q存放著所有x-1的素因子，長度為k

inti=0;

intL=logx;

inttemp;

intisPrime=1;//假定該數(shù)為素數(shù)

boolDecision=true;

任取(1,x)內(nèi)的隨機數(shù)r; if(x<=1)

isPrime=false;

else

while((i<k)‖Decision)

{

if((pow(x-1)，q［i］%x)!=1)

Decision=false;

++i;

} if(!Decision)

isPrime=2;//返回值為不確定

elseif((pow(r，x-1)%x)!=1)

isPrime=0;//該數(shù)為合數(shù)

returnisPrime;//返回值為該數(shù)是否是素數(shù)或不確定

}

可證明該算法屬于LasVegas算法。從此程序中也可看出，LasVegas算法測試的范圍較窄，驗證手段較多，因而正確率高但速度稍慢。

定義8.3.5Zero-sided-error算法滿足下列特點的概率算法：

Pr［PTMrecognizesI∈L|I∈L］=1

Pr［PTMrecognizesI∈L|I

L］=0

Zero-sided-error算法較為特殊，它的速度最快，也幾乎完全正確。Zero-sided-error算法對應復雜性類ZPP，從定義上可知ZPP是PP(MonteCarlo)與PP(LasVegas)的交集。

這些復雜性類之間滿足如下關(guān)系：

8.4多項式時間不可區(qū)分性某些加密體制雖然暫時不存在有效算法破解，但這并不意味著它們是安全的。如果某人截獲密文后偽造之再予以發(fā)送，這種