第4章-密碼學(xué)的計(jì)算復(fù)雜性理論基礎(chǔ)ppt課件

1、第4章 密碼學(xué)的計(jì)算復(fù)雜性理論基礎(chǔ),4.1 問(wèn)題與算法的復(fù)雜性,4.1.1 問(wèn)題與語(yǔ)言 例4.1 . 整數(shù)的因子分解問(wèn)題。 例4.2 . 背包問(wèn)題。 實(shí)際應(yīng)用中的絕大多數(shù)問(wèn)題都可直接或間接地轉(zhuǎn)化為判定問(wèn)題,定義4.1 的任一子集L稱為一個(gè)B語(yǔ)言（或簡(jiǎn)稱語(yǔ)言）。語(yǔ)言L中的字稱為語(yǔ)言L的成員。 定義4.2 設(shè)一個(gè)語(yǔ)言 已給定。語(yǔ)言L成員的識(shí)別問(wèn)題可描述為：任給 （參數(shù)），問(wèn)是否x是L語(yǔ)言的成員（是否 ）？ 定義4.3 設(shè) 為一個(gè)問(wèn)題，B為一個(gè)字符集。從I到 中的一個(gè)映射c，滿足條件 （空集），稱為問(wèn)題D的一個(gè)B編碼。若c為D的一個(gè)編碼，集 稱為D的一個(gè)c語(yǔ)言,引理4.1 若c為D的一個(gè)編碼，則求解

2、問(wèn)題D和求解語(yǔ)言 的成員識(shí)別問(wèn)題是等價(jià)的，即問(wèn)題D的任一例子 ，其答案與語(yǔ)言 的成員識(shí)別問(wèn)題的例子的答案 是相同的。 一個(gè)合理編碼還應(yīng)滿足下列兩個(gè)基本要求： 1） 編碼是容易實(shí)現(xiàn)的； 2） 求解問(wèn)題的任一例子的計(jì)算復(fù)雜性（通常用計(jì)算時(shí)間來(lái)表示）與的長(zhǎng)有某種正比關(guān)系,4.1.2 算法與圖靈機(jī),定義 4.4 一個(gè)確定性單帶圖靈機(jī)由下列集和函數(shù)構(gòu)成。 1.1）帶中所用字符集B，通?？稍O(shè) ，其中 表示空。 2）讀寫頭所處的可能狀態(tài)集S，其中包含一個(gè)初始狀態(tài) 和若干個(gè)停機(jī)狀態(tài) 。 3）讀寫頭所處狀態(tài)的轉(zhuǎn)移函數(shù) ，它是讀寫頭現(xiàn)在所處狀態(tài)s和所讀字符b的函數(shù)，表示為 。 4）讀寫頭動(dòng)作的指令函數(shù) ，它也是讀

3、寫頭現(xiàn)在所處狀態(tài)s和所讀字符b的函數(shù)，表示為 ，其中 且都不屬于B。若 ，則讀寫頭寫字符 代替b，且保持原位不動(dòng)。若 ，則原字符b保持不變，讀寫頭向左（或向右）移動(dòng)一個(gè)小方格。 2.磁帶上的每個(gè)小方格用一個(gè)整數(shù)坐標(biāo)i表示。小方格i中的字符記作t(i)，磁帶表示為函數(shù),3.圖靈機(jī)在某一時(shí)刻的形是指一個(gè)三元組 ，它們分別表示該時(shí)刻讀寫頭所處狀態(tài)，磁帶和讀寫頭所掃描的小方格坐標(biāo)，t(i)為讀寫頭在該時(shí)刻所讀字符。 一個(gè)圖靈機(jī)的計(jì)算程序（算法）是一個(gè)形的有限或無(wú)限序列 ，其中 為圖靈機(jī)在初始時(shí)刻的形，即 為初始狀態(tài)，為初始磁帶，它由輸入數(shù)據(jù)（字） 給出，通常存放在 小方格中，其它小方格中為空字符 ，通

4、常 。圖靈機(jī)在k時(shí)刻的形 由下面的遞推式給出。 若存在形 使 ，則計(jì)算在時(shí)刻 終止，同時(shí)停機(jī)，稱 或 為計(jì)算的輸出結(jié)果，K稱為圖靈機(jī)（算法）的運(yùn)行（計(jì)算）時(shí)間。否則計(jì)算將不終止，不停機(jī)，直到無(wú)限,定義 4.5 稱一個(gè)圖靈機(jī)M可解一個(gè)語(yǔ)言L的成員識(shí)別問(wèn)題,若對(duì)任一輸入數(shù)據(jù) ，M在有限時(shí)刻 停機(jī)，且M的輸出 ，若 。否則 。圖靈機(jī)的計(jì)算復(fù)雜性定義為 定義 4.6 設(shè)f(n)和g(n)為兩個(gè)正整數(shù)函數(shù)，若存在正整數(shù) 和常數(shù)c使當(dāng) 時(shí)有 ，則記作 ；若 ， ，則記作,定義4.7 設(shè) 和 為圖靈機(jī)M和 的計(jì)算復(fù)雜性，若 ，則稱算法 不比算法M有效；若 ，則稱算法M和 是等效的；若存在正整數(shù)d， ，則稱M

5、為多項(xiàng)式時(shí)間算法，按密碼學(xué)中的傳統(tǒng)觀念，認(rèn)為多項(xiàng)式時(shí)間算法為有效算法；若 ，則稱M為亞指數(shù)時(shí)間算法；若 ，則稱M為指數(shù)時(shí)間算法。亞指數(shù)和指數(shù)時(shí)間算法也被稱為超多項(xiàng)式時(shí)間算法，被認(rèn)為不是有效算法,42 問(wèn)題的計(jì)算復(fù)雜性分類,4.2.1 P，NP，NP完全類問(wèn)題 定義4.8 一個(gè)語(yǔ)言L的成員識(shí)別問(wèn)題屬于P類，若存在一個(gè)可解該問(wèn)題的圖靈機(jī)M和一個(gè)正多項(xiàng)式 ，使M的計(jì)算復(fù)雜性 ，所有P類問(wèn)題構(gòu)成的集記作P。 定義4.9 一個(gè)語(yǔ)言L的成員識(shí)別問(wèn)題屬于NP類，若存在一個(gè) 的子集 （稱為一個(gè)布爾關(guān)系）及一個(gè)正多項(xiàng)式p(n)滿足下列兩個(gè)條件： 1） 的成員識(shí)別問(wèn)題屬于P類； 2） 當(dāng)且僅當(dāng)存在一個(gè)y，其長(zhǎng) ，

6、且 。這樣的y稱為是 的證據(jù)。所有NP類問(wèn)題構(gòu)成的集記作NP,定義4.9 一個(gè)語(yǔ)言的成員識(shí)別問(wèn)題屬于NP類，若存在一個(gè)的子集（稱為一個(gè)布爾關(guān)系）及一個(gè)正多項(xiàng)式(n)滿足下列兩個(gè)條件： 1）的成員識(shí)別問(wèn)題屬于P類； 2）當(dāng)且僅當(dāng)存在一個(gè)，其長(zhǎng)，且。這樣的稱為是的證據(jù)。所有NP類問(wèn)題構(gòu)成的集記作NP,定義 4.10 稱一個(gè)圖靈機(jī)M可計(jì)算一個(gè)函數(shù) ，若對(duì)任一輸入數(shù)據(jù) ，M在有限時(shí)刻 停機(jī)，且M的輸出磁帶 上的二進(jìn)數(shù)序列（不包含空 ） 。若M是多項(xiàng)式時(shí)間算法，則稱f(x)是多項(xiàng)式時(shí)間可計(jì)算的。 定義4.11 一個(gè)語(yǔ)言L稱為可多項(xiàng)式時(shí)間化為另一語(yǔ)言 ，若存在一個(gè)多項(xiàng)式時(shí)間可計(jì)算函數(shù)f(x)，使 當(dāng)且僅當(dāng)

7、 ，這時(shí)也稱語(yǔ)言L的成員識(shí)別問(wèn)題可多項(xiàng)式時(shí)間化為語(yǔ)言 的成員識(shí)別問(wèn)題。 定義 4.12 一個(gè)語(yǔ)言L的成員識(shí)別問(wèn)題屬于NP完全(NPC)類，若它屬于NP類，且每個(gè)NP類語(yǔ)言成員識(shí)別問(wèn)題都可多項(xiàng)式時(shí)間化為語(yǔ)言L的成員識(shí)別問(wèn)題。所有NP完全類問(wèn)題構(gòu)成的集記作NPC,4.2.2 概率算法與BPP類問(wèn)題,概率算法就是在執(zhí)行計(jì)算的過(guò)程中允許用隨機(jī)數(shù)。 定義 4.13 一個(gè)概率算法（圖靈機(jī)）稱為多項(xiàng)式時(shí)間概率算法。若存在一個(gè)多項(xiàng)式p(n)，對(duì)任一 ，有 。換句話說(shuō)，對(duì)所有扔硬幣結(jié)果r（可設(shè) ）都有,定義 4.14 稱一個(gè)多項(xiàng)式時(shí)間概率算法M可解一個(gè)語(yǔ)言L的成員識(shí)別問(wèn)題，若對(duì)任一輸入數(shù)據(jù) ，有 （1）若 ，則 （2）若 ，則 稱一個(gè)語(yǔ)言L的成員識(shí)別問(wèn)題屬于BPP類，若存在一個(gè)可解該問(wèn)題的多項(xiàng)式時(shí)間概率算法。所有BPP類問(wèn)題構(gòu)成的集記作BPP,小結(jié),計(jì)算復(fù)雜性理論是現(xiàn)代密碼學(xué)的理論基礎(chǔ)。 關(guān)于算法的時(shí)間復(fù)雜性有兩種定義方法：一