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

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

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

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

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

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