現(xiàn)代密碼學(xué)第三講：復(fù)雜性理論

1復(fù)雜性理論《現(xiàn)代密碼學(xué)》第三講上講內(nèi)容回憶Shannon通信保密系統(tǒng)熵和無條件保密分組密碼的設(shè)計(jì)思想本章主要內(nèi)容問題的定義及分類算法復(fù)雜度定義及分類P問題和NP問題規(guī)約思想與NPC類密碼算法的計(jì)算平安性問題的定義及分類1設(shè)A=(a1,a2,…,an)是由n個(gè)不同的正整數(shù)構(gòu)成的n元組，S是另一的正整數(shù).A稱為背包向量，S稱為背包容積.求A中元素集合A’，使.2設(shè)背包向量A=(1,2,5,10,20,50,100),背包容積為177，求向量，使得.問題的定義及分類3整數(shù)N，問N是否是一個(gè)素?cái)?shù)？4試問77是否是素?cái)?shù)？5試問79是否是素?cái)?shù)？6整數(shù)N，求N的素分解式.7整數(shù)177，求其素分解式.問題的定義及分類問題：描述參量陳述解容許當(dāng)滿足的性質(zhì)〔稱為詢問〕.參量為具體數(shù)值時(shí)，稱為問題的一個(gè)實(shí)例.判定問題：答復(fù)只有Yes或No.計(jì)算問題：從其可行解集合中搜索出最優(yōu)解.7算法復(fù)雜度的定義例設(shè)x是小于100的某個(gè)整數(shù)，問x是否是素?cái)?shù)？解答一：取2～的所有整數(shù)，依次試除x，假設(shè)存在某個(gè)整數(shù)可以整除x，那么程序停止，輸出x為合數(shù)，否那么輸出x為素?cái)?shù).最壞試除次數(shù)：存儲(chǔ)空間：0解答二：預(yù)先將所有小于100的素?cái)?shù)存儲(chǔ)在存放器中；然后將X與存儲(chǔ)器中的元素比較，假設(shè)存在某個(gè)素?cái)?shù)等于x，那么程序停止，輸出x為素?cái)?shù)，否那么輸出x為合數(shù).最壞比較次數(shù):100/ln100,存儲(chǔ)空間:100/ln1008算法復(fù)雜度的定義時(shí)間〔計(jì)算〕復(fù)雜性：考慮算法的主要操作步驟，計(jì)算執(zhí)行中所需的總操作次數(shù).空間復(fù)雜性：執(zhí)行過程中所需存儲(chǔ)器的單元數(shù)目.數(shù)據(jù)復(fù)雜性：信息資源.計(jì)算模型----確定性圖靈機(jī)〔有限帶符號(hào)集合，有限狀態(tài)集，轉(zhuǎn)換函數(shù)〕〔讀寫頭，讀寫帶〕.算法復(fù)雜度的定義不同的編程語言，不同的編譯器導(dǎo)致執(zhí)行一次操作的時(shí)間各不相同，為了方便不同算法比較，通常假定所有計(jì)算機(jī)執(zhí)行相同的一次根本操作所需時(shí)間相同，而把算法中根本操作執(zhí)行的最大次數(shù)作為執(zhí)行時(shí)間.根本操作數(shù)量運(yùn)行時(shí)間=機(jī)器速度10算法復(fù)雜度的定義定義假設(shè)一個(gè)算法的計(jì)算復(fù)雜度為O(nt)，其中t為常數(shù)，n為輸入問題的長度，那么稱這算法的復(fù)雜度是多項(xiàng)式的。具有多項(xiàng)式時(shí)間復(fù)雜度的算法為多項(xiàng)式時(shí)間算法.函數(shù)g(n)=O(nt)表示存在常數(shù)c>0和n0>=0，對(duì)一切n>n0均有|g(n)|<=c|nt|成立，也就是說，當(dāng)n足夠大時(shí)，g(n)存在上界.定義非多項(xiàng)式時(shí)間算法：算法的計(jì)算復(fù)雜性寫不成O(P(n))形式，其中P(n)表示n的多項(xiàng)式函數(shù).算法復(fù)雜度的定義例

設(shè)x是小于100的某個(gè)整數(shù)，問x是否是素?cái)?shù)？

解法1是否是多項(xiàng)式時(shí)間算法？

解法2是否是多項(xiàng)式時(shí)間算法？12P問題和NP問題定義(P問題)如果一個(gè)判定問題存在解它的多項(xiàng)式時(shí)間的算法，那么稱該問題屬于P類.定義(NP問題)如果一個(gè)判定問題不存在解它的多項(xiàng)式時(shí)間的算法，且對(duì)于一個(gè)解答可以在多項(xiàng)式時(shí)間驗(yàn)證其是否正確，那么稱該問題屬于NP類.公開問題：P≠NP？它是Clay研究所的七個(gè)百萬美元大獎(jiǎng)問題之一密碼算法的計(jì)算平安性二次函數(shù)、三次函數(shù)、2x函數(shù)的示意圖

14密碼算法的計(jì)算平安性例.設(shè)問題輸入長度為n，在一個(gè)每秒鐘運(yùn)行百萬次的計(jì)算機(jī)上的運(yùn)行時(shí)間如下:10305060T(n)=n20.0001s0.0009s0.0025s0.0036sT(n)=2n0.001s17.9月35.7年366世紀(jì)密碼算法的計(jì)算平安性當(dāng)問題輸入長度足夠大，分析密碼體制的算法的復(fù)雜度較大，可能的計(jì)算能力下，在保密的期間內(nèi)可以保證算法不被攻破，這就是密碼體制的計(jì)算平安性思想。注：分析方法是無窮無盡的，類似于解決問題的算法，目前不存在非多項(xiàng)式時(shí)間的分析方法，將來可能存在，即算法將來可能不堪一擊.如差分分析出現(xiàn)。。。16密碼算法的計(jì)算平安性密碼系統(tǒng)設(shè)計(jì)：合法用戶——易〔多項(xiàng)式〕攻擊者——難〔非多項(xiàng)式〕注：計(jì)算模型----圖靈機(jī)量子計(jì)算機(jī)出現(xiàn)導(dǎo)致分解因子問題容易，從而RSA等密碼系統(tǒng)不再平安，緣由是計(jì)算模型不同.非多項(xiàng)式時(shí)間問題多項(xiàng)式問題17規(guī)約思想與NPC類定義判定問題，.假設(shè)存在的解法S1，那么通過調(diào)用S1〔作為子程序〕，可以在多項(xiàng)式時(shí)間內(nèi)解問題，那么稱可多項(xiàng)式規(guī)約至“∝〞定義假設(shè)判定問題∈NP，對(duì)每個(gè)判定問題∈NP，都有∝，那么稱屬于NPC類，或稱為NP完全的.規(guī)約思想與NPC類主要知識(shí)點(diǎn)小結(jié)算法的復(fù)雜度定義及分類密碼算法的計(jì)算復(fù)雜度20作業(yè)1求冒泡排序法的計(jì)算復(fù)雜度,該算法是否為多項(xiàng)式的？2超遞增背包問題：設(shè)A=(a1,a2,…,an)是由n個(gè)不同的正整數(shù)構(gòu)成的n元組，且