資源描述:
《現(xiàn)代密碼學(xué)第3講:復(fù)雜性理論.ppt》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、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試問
2、77是否是素數(shù)?5試問79是否是素數(shù)?6已知整數(shù)N,求N的素分解式.7已知整數(shù)177,求其素分解式.問題的定義及分類問題:描述參量陳述解答應(yīng)當(dāng)滿足的性質(zhì)(稱為詢問).參量為具體數(shù)值時,稱為問題的一個實例.判定問題:回答只有Yes或No.計算問題:從其可行解集合中搜索出最優(yōu)解.7算法復(fù)雜度的定義例設(shè)x是小于100的某個整數(shù),問x是否是素數(shù)?解答一:取2~的所有整數(shù),依次試除x,若存在某個整數(shù)可以整除x,則程序停止,輸出x為合數(shù),否則輸出x為素數(shù).最壞試除次數(shù):存儲空間:0解答二:預(yù)先將所有小于100的素數(shù)存
3、儲在寄存器中;然后將X與存儲器中的元素比較,若存在某個素數(shù)等于x,則程序停止,輸出x為素數(shù),否則輸出x為合數(shù).最壞比較次數(shù):100/ln100,存儲空間:100/ln1008算法復(fù)雜度的定義時間(計算)復(fù)雜性:考慮算法的主要操作步驟,計算執(zhí)行中所需的總操作次數(shù).空間復(fù)雜性:執(zhí)行過程中所需存儲器的單元數(shù)目.數(shù)據(jù)復(fù)雜性:信息資源.計算模型----確定性圖靈機(有限帶符號集合,有限狀態(tài)集,轉(zhuǎn)換函數(shù))(讀寫頭,讀寫帶).算法復(fù)雜度的定義不同的編程語言,不同的編譯器導(dǎo)致執(zhí)行一次操作的時間各不相同,為了方便不同算法比
4、較,通常假定所有計算機執(zhí)行相同的一次基本操作所需時間相同,而把算法中基本操作執(zhí)行的最大次數(shù)作為執(zhí)行時間.基本操作數(shù)量運行時間=機器速度10算法復(fù)雜度的定義定義假設(shè)一個算法的計算復(fù)雜度為O(nt),其中t為常數(shù),n為輸入問題的長度,則稱這算法的復(fù)雜度是多項式的。具有多項式時間復(fù)雜度的算法為多項式時間算法.函數(shù)g(n)=O(nt)表示存在常數(shù)c>0和n0>=0,對一切n>n0均有
5、g(n)
6、<=c
7、nt
8、成立,也就是說,當(dāng)n足夠大時,g(n)存在上界.定義非多項式時間算法:算法的計算復(fù)雜性寫不成O(P(n))
9、形式,其中P(n)表示n的多項式函數(shù).算法復(fù)雜度的定義例設(shè)x是小于100的某個整數(shù),問x是否是素數(shù)?解法1是否是多項式時間算法?解法2是否是多項式時間算法?12P問題和NP問題定義(P問題)如果一個判定問題存在解它的多項式時間的算法,則稱該問題屬于P類.定義(NP問題)如果一個判定問題不存在解它的多項式時間的算法,且對于一個解答可以在多項式時間驗證其是否正確,則稱該問題屬于NP類.公開問題:P≠NP?它是Clay研究所的七個百萬美元大獎問題之一密碼算法的計算安全性二次函數(shù)、三次函數(shù)、2x函數(shù)的示意圖14密
10、碼算法的計算安全性例.設(shè)問題輸入長度為n,在一個每秒鐘運行百萬次的計算機上的運行時間如下:10305060T(n)=n20.0001s0.0009s0.0025s0.0036sT(n)=2n0.001s17.9月35.7年366世紀(jì)密碼算法的計算安全性當(dāng)問題輸入長度足夠大,分析密碼體制的算法的復(fù)雜度較大,可能的計算能力下,在保密的期間內(nèi)可以保證算法不被攻破,這就是密碼體制的計算安全性思想。注:分析方法是無窮無盡的,類似于解決問題的算法,目前不存在非多項式時間的分析方法,將來可能存在,即算法將來可能不堪一擊
11、.如差分分析出現(xiàn)。。。16密碼算法的計算安全性密碼系統(tǒng)設(shè)計:合法用戶——易(多項式)攻擊者——難(非多項式)注:計算模型----圖靈機量子計算機出現(xiàn)導(dǎo)致分解因子問題容易,從而RSA等密碼系統(tǒng)不再安全,緣由是計算模型不同.非多項式時間問題多項式問題17規(guī)約思想與NPC類定義判定問題,.若存在的解法S1,那么通過調(diào)用S1(作為子程序),可以在多項式時間內(nèi)解問題,則稱可多項式規(guī)約至“∝”定義若判定問題∈NP,對每個判定問題∈NP,都有∝,則稱屬于NPC類,或稱為NP完全的.規(guī)約思想與NPC類主要知識點小結(jié)算法的
12、復(fù)雜度定義及分類密碼算法的計算復(fù)雜度20作業(yè)1求冒泡排序法的計算復(fù)雜度,該算法是否為多項式的?2超遞增背包問題:設(shè)A=(a1,a2,…,an)是由n個不同的正整數(shù)構(gòu)成的n元組,且,S是另一已知的正整數(shù)。求A的子集A’,使.(1)給出該問題的求解算法;(2)求算法的計算復(fù)雜度.21THEEND!