信息安全數(shù)學(xué)基礎(chǔ)(計(jì)算復(fù)雜性)課件

信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)題復(fù)雜性算法復(fù)雜性信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)題復(fù)雜性算法第2章信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)題復(fù)雜性算法復(fù)雜性第2章信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)計(jì)算復(fù)雜性基礎(chǔ)

2023/1/8

－古書(shū)《孟子·離婁上》有這樣的記載： 淳于髡曰：男女授受不親，禮與？ 孟子曰：禮也。 曰：嫂溺則授之以手乎？ 曰：嫂溺不授，是豺狼也。男女授受不親，禮也；嫂溺授之以手，權(quán)也。－雖然有“男女授受不親”的原則存在，但嫂子落水快淹死時(shí)，必須拉她、救她，這是“權(quán)”(變通)，否則，見(jiàn)死不救，就是豺狼。－曰：「今天下溺矣，夫子之不援何也？」

曰：「天下溺援之以道；嫂溺援之以手。子欲手援天下乎？」計(jì)算復(fù)雜性基礎(chǔ)2023/1/8計(jì)算復(fù)雜性為什么要學(xué)習(xí)計(jì)算復(fù)雜性？計(jì)算復(fù)雜性是研究密碼分析對(duì)于計(jì)算量的需求和密碼分析的困難程度，從而得出這些密碼技術(shù)和算法在現(xiàn)有可行的條件下是否具有足夠的安全性。學(xué)習(xí)計(jì)算復(fù)雜性，需要掌握兩個(gè)概念：?jiǎn)栴}算法2023/1/8計(jì)算復(fù)雜性為什么要學(xué)習(xí)計(jì)算復(fù)雜性？2023/1/8問(wèn)題（problem）

（問(wèn)題）定義：即需要回答的一般性提問(wèn):它通常含有若干個(gè)參數(shù)。對(duì)于一個(gè)問(wèn)題進(jìn)行描述應(yīng)該包括兩方面的內(nèi)容：必須對(duì)問(wèn)題的所有給定參數(shù)給出一般性描述；必須描述該問(wèn)題的答案（或解）應(yīng)該滿足的性質(zhì)。當(dāng)問(wèn)題的所有參數(shù)都有了確定的取值時(shí)，我們稱得到了該問(wèn)題的一個(gè)實(shí)例（instance）。2023/1/8問(wèn)題（problem）（問(wèn)題）定義：即需要回答的一般性提問(wèn)算法（algorithm）

定義（算法）：即求解某個(gè)問(wèn)題的一系列具體步驟（通常被理解為求解所需的通用計(jì)算程序）。算法總是針對(duì)具體問(wèn)題而言的，求解一個(gè)問(wèn)題的算法通常不止一個(gè)。當(dāng)某個(gè)算法能夠回答一個(gè)問(wèn)題的任何實(shí)例時(shí)，我們稱該算法能夠回答這個(gè)問(wèn)題。當(dāng)一個(gè)問(wèn)題至少有一個(gè)能夠回答該問(wèn)題的算法時(shí)，我們稱該問(wèn)題可解（resolvable），否則稱該問(wèn)題不可解（unresolvable）。2023/1/8算法（algorithm）定義（算法）：即求解某個(gè)問(wèn)題的算法（algorithm）（續(xù)）

有關(guān)算法的幾點(diǎn)注釋：算法總有輸入和輸出算法輸入大小一般用輸入變量的長(zhǎng)度（單位為位）來(lái)表示一般來(lái)說(shuō)，算法用某種編程語(yǔ)言來(lái)實(shí)現(xiàn)的計(jì)算機(jī)程序一般來(lái)說(shuō)，我們僅僅關(guān)注解決問(wèn)題最有效的算法2023/1/8算法（algorithm）（續(xù)）有關(guān)算法的幾點(diǎn)注釋：202問(wèn)題與算法問(wèn)題：如何求解兩個(gè)整數(shù)a和b的最大公約數(shù)？參數(shù)：a和b問(wèn)題實(shí)例：a＝20，b＝30算法：利用因子分解求a＝20和b＝30的最大公約數(shù)a＝22×5b＝2×3×5因此a和b的最大公約數(shù)是2×5＝102023/1/8問(wèn)題與算法問(wèn)題：如何求解兩個(gè)整數(shù)a和b的最大公約數(shù)？2023算法復(fù)雜性

（算法復(fù)雜度）定義：即度量該算法所需的計(jì)算能力，包括：時(shí)間復(fù)雜性T（timecomplexity）；空間復(fù)雜性S（spacecomplexity）；信道帶寬；數(shù)據(jù)總量；……2023/1/8算法復(fù)雜性（算法復(fù)雜度）定義：即度量該算法所需的計(jì)算能力算法復(fù)雜性（續(xù)）計(jì)算復(fù)雜性的表示符號(hào)為“O”（稱為“大O”，即算法的階號(hào)），表示計(jì)算復(fù)雜性的數(shù)量級(jí)

好處：使算法復(fù)雜性度量與處理器的運(yùn)行速度和指令運(yùn)行時(shí)間無(wú)關(guān)；明確地揭示了輸入的數(shù)據(jù)長(zhǎng)度對(duì)算法復(fù)雜性的影響。

2023/1/8算法復(fù)雜性（續(xù)）計(jì)算復(fù)雜性的表示符號(hào)為“O”（稱為“大O算法復(fù)雜性（續(xù)）算法常見(jiàn)復(fù)雜性分類（1）常數(shù)算法（constantAlgorithm）：如果運(yùn)行時(shí)間是O(1)，即該算法的復(fù)雜性不依賴于n。（2）線性算法（linearAlgorithm）：如果運(yùn)行時(shí)間是O(n)。（3）多項(xiàng)式算法（polynomialAlgorithm）：如果運(yùn)行時(shí)間是O(nm)，其中m是一個(gè)常數(shù)。具有多項(xiàng)式復(fù)雜性的算法族被稱為多項(xiàng)式時(shí)間算法。（4）超多項(xiàng)式算法（superpolynomialAlgorithm）：如果運(yùn)行時(shí)間是，其中c是一個(gè)常數(shù)，而s(n)是關(guān)于n的大于常數(shù)而小于線性的函數(shù)。（5）指數(shù)算法（exponentialAlgorithm）：如果運(yùn)行時(shí)間是，其中t是大于1的常數(shù)，f(n)是關(guān)于n的多項(xiàng)式函數(shù)。2023/1/8算法復(fù)雜性（續(xù)）算法常見(jiàn)復(fù)雜性分類2023/1/8算法復(fù)雜性（續(xù)）算法常見(jiàn)復(fù)雜性分類一般而言，常數(shù)算法、線性算法、多項(xiàng)式算法和超多項(xiàng)式算法統(tǒng)稱為多項(xiàng)式算法。所謂多項(xiàng)式，就是具有下列形式的一個(gè)函數(shù)：2023/1/8其中，k和ck是常數(shù)，且ci稱≠0為。當(dāng)k>0時(shí)，k稱為多項(xiàng)式的次數(shù)，ci稱為多項(xiàng)式的系數(shù)。

算法復(fù)雜性（續(xù)）算法常見(jiàn)復(fù)雜性分類2023/1/8其中，k和算法復(fù)雜性算法的分類及其運(yùn)行時(shí)間

算法類型復(fù)雜性運(yùn)算次數(shù)n＝106時(shí)間多項(xiàng)式算法常數(shù)算法O(1)11微秒線性算法O(n)1061秒二次多項(xiàng)式算法O(n2)101211.6天三次多項(xiàng)式算法O(n3)101832,000年指數(shù)算法O(2n)1030103010301006年2023/1/8算法復(fù)雜性（續(xù)）算法復(fù)雜性算法的分類及其運(yùn)行時(shí)間算法類型復(fù)雜性運(yùn)算算法復(fù)雜性算法復(fù)雜度的增長(zhǎng)速度2023/1/8算法復(fù)雜性（續(xù)）亞指數(shù)指數(shù)多項(xiàng)式算法復(fù)雜性算法復(fù)雜度的增長(zhǎng)速度2023/1/8算法復(fù)算法復(fù)雜性（續(xù)）研究問(wèn)題的內(nèi)在復(fù)雜性，即在圖靈機(jī)上解決最難的問(wèn)題實(shí)例所需的最小時(shí)間和空間條件。圖靈機(jī)是一種具有無(wú)限讀、寫(xiě)存儲(chǔ)帶的有限狀態(tài)機(jī)，可以被當(dāng)作一個(gè)實(shí)際可用的計(jì)算模型。2023/1/8算法復(fù)雜性（續(xù)）研究問(wèn)題的內(nèi)在復(fù)雜性，即在圖靈機(jī)上解決最難的第2章信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)題復(fù)雜性算法復(fù)雜性第2章信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)問(wèn)題復(fù)雜性

圖靈機(jī)分為兩類：確定性圖靈機(jī)。非確定性圖靈機(jī)2023/1/8問(wèn)題復(fù)雜性圖靈機(jī)分為兩類：2023/1/8問(wèn)題復(fù)雜性（續(xù)）確定性圖靈機(jī)。確定性圖靈機(jī)的輸出結(jié)果只取決于輸入和初始狀態(tài)。因此，對(duì)于具有相同輸入和初始狀態(tài)，運(yùn)行一個(gè)確定性圖靈機(jī)所得到的結(jié)果是完全相同的。非確定性圖靈機(jī)：能夠進(jìn)行猜測(cè)。求解一個(gè)問(wèn)題分兩個(gè)階段：猜測(cè)階段和驗(yàn)證階段。2023/1/8問(wèn)題復(fù)雜性（續(xù)）確定性圖靈機(jī)。2023/1/8圖靈機(jī)圖靈機(jī)包括一個(gè)有限狀態(tài)控制單元、k（≥1）條紙帶（Tape）和k個(gè)讀寫(xiě)頭（Tapehead）。有限狀態(tài)控制單元控制每個(gè)讀寫(xiě)頭訪問(wèn)一條紙帶，并沿著紙帶左右移動(dòng)圖靈機(jī)求解問(wèn)題的輸入是一個(gè)有限長(zhǎng)度的字符串，該輸入占據(jù)每條紙帶無(wú)限個(gè)單元的最左邊的有限個(gè)單元。讀寫(xiě)頭對(duì)紙帶的一次訪問(wèn)稱之為一個(gè)合法移動(dòng)（Move）。2023/1/8圖靈機(jī)圖靈機(jī)包括一個(gè)有限狀態(tài)控制單元、k（≥1）條紙帶（Ta圖靈機(jī)（續(xù)）圖靈機(jī)求解問(wèn)題時(shí)，被賦予一個(gè)初始狀態(tài)（InitialState），且一步一步地移動(dòng)，從而完成對(duì)輸入的掃描。如果圖靈機(jī)最終掃描了整個(gè)輸入串，且滿足了中止條件而停止下來(lái)，則稱圖靈機(jī)識(shí)別了該輸入。否則，圖靈機(jī)在某一點(diǎn)沒(méi)有合法移動(dòng)，因此會(huì)沒(méi)有識(shí)別輸入串而停止下來(lái)，此時(shí)稱圖靈機(jī)無(wú)法識(shí)別該輸入。圖靈機(jī)所識(shí)別的一個(gè)輸入，稱為一種可識(shí)別語(yǔ)言的一個(gè)實(shí)例。2023/1/8圖靈機(jī)（續(xù)）圖靈機(jī)求解問(wèn)題時(shí)，被賦予一個(gè)初始狀態(tài)（Initi圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1100)能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)不能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11問(wèn)題復(fù)雜性

借助于圖靈機(jī)理論，問(wèn)題復(fù)雜型實(shí)際上就是在圖靈機(jī)上解決最難的問(wèn)題實(shí)例所需要的最小時(shí)間最小空間2023/1/8問(wèn)題復(fù)雜性借助于圖靈機(jī)理論，問(wèn)題復(fù)雜型實(shí)際上就是在圖靈機(jī)上圖靈機(jī)（續(xù)）圖靈機(jī)M識(shí)別一個(gè)長(zhǎng)度為n的輸入串而移動(dòng)的步數(shù)稱為圖靈機(jī)的時(shí)間復(fù)雜性，記為：當(dāng)圖靈機(jī)M識(shí)別一個(gè)長(zhǎng)度為n的輸入串，其寫(xiě)操作中讀寫(xiě)頭所訪問(wèn)的紙帶單元數(shù)稱為圖靈機(jī)的空間復(fù)雜性，記為：2023/1/8圖靈機(jī)（續(xù)）圖靈機(jī)M識(shí)別一個(gè)長(zhǎng)度為n的輸入串而移動(dòng)的步數(shù)稱為圖靈機(jī)（續(xù)）2023/1/8圖靈機(jī)（續(xù)）2023/1/8問(wèn)題分類如果一個(gè)問(wèn)題在確定性圖靈機(jī)上能夠在多項(xiàng)式時(shí)間內(nèi)得到處理，則稱該問(wèn)題時(shí)易處理的（tractable）。也既是說(shuō)，能夠用多項(xiàng)式時(shí)間解決的問(wèn)題稱之為易處理的。不能夠在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題是難處理的。因?yàn)殡S著輸入尺寸的增加，求解這類問(wèn)題需要的時(shí)間迅速變得很長(zhǎng)，以至于不可能有效的求解。難處理的問(wèn)題也被稱為是難解的。2023/1/8問(wèn)題分類如果一個(gè)問(wèn)題在確定性圖靈機(jī)上能夠在多項(xiàng)式時(shí)間內(nèi)得到處P類問(wèn)題易處理問(wèn)題的全體稱為“多項(xiàng)式時(shí)間可解類”，記為P類。復(fù)雜度類P包含所有能用多項(xiàng)式時(shí)間解決的問(wèn)題。2023/1/8上述定義表明，如果L是多項(xiàng)式時(shí)間內(nèi)可識(shí)別的語(yǔ)言，則確定性圖靈機(jī)可以在多項(xiàng)式時(shí)間內(nèi)，判定一個(gè)字符串是否屬于語(yǔ)言L。P類問(wèn)題易處理問(wèn)題的全體稱為“多項(xiàng)式時(shí)間可解類”，記為P類。NP類問(wèn)題有這樣一類問(wèn)題，雖然不能夠用確定性圖靈機(jī)來(lái)有效求解，但是卻可以用非確定性圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)得到處理這類問(wèn)題稱為“非確定性多項(xiàng)式時(shí)間可解問(wèn)題”，簡(jiǎn)稱NP問(wèn)題。2023/1/8定義（NP類）NP類表示用非確定性圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可以識(shí)別的語(yǔ)言類。NP類問(wèn)題有這樣一類問(wèn)題，雖然不能夠用確定性圖靈機(jī)來(lái)有效求解NP類問(wèn)題（續(xù)）意義：能夠通過(guò)非確定性的多項(xiàng)式時(shí)間算法對(duì)許多對(duì)稱密鑰算法和所有公鑰算法進(jìn)行攻擊。NP完全問(wèn)題：指NP中的任何一個(gè)問(wèn)題都可以通過(guò)多項(xiàng)式時(shí)間轉(zhuǎn)化為該問(wèn)題。NP完全問(wèn)題的全體被記為NPC。NP完全問(wèn)題是NP問(wèn)題中最難的問(wèn)題。

2023/1/8定義2.3.3（NP完全類）如果任意:

是非確定性多項(xiàng)式時(shí)間完全的（NP完全的）都可以多項(xiàng)式規(guī)約到語(yǔ)言，則稱:NP類問(wèn)題（續(xù)）意義：能夠通過(guò)非確定性的多項(xiàng)式時(shí)間算法對(duì)許多NP類問(wèn)題（續(xù)）NP中的任何一個(gè)問(wèn)題都可以通過(guò)多項(xiàng)式時(shí)間轉(zhuǎn)化為該問(wèn)題。NP完全問(wèn)題的全體被記為NPC。NP完全問(wèn)題是NP問(wèn)題中最難的問(wèn)題。2023/1/8NP類問(wèn)題（續(xù)）NP中的任何一個(gè)問(wèn)題都可以通過(guò)多項(xiàng)式時(shí)間轉(zhuǎn)化算法復(fù)雜性算法時(shí)間復(fù)雜度的度量方法圖靈機(jī)解決問(wèn)題所移動(dòng)的步數(shù)（該時(shí)間稱之為算法的運(yùn)行時(shí)間）該度量方法的缺點(diǎn)：沒(méi)有考慮每一步具體的操作例如：加法和乘法的計(jì)算開(kāi)銷是不同的為此，引入算法“按位”的計(jì)算復(fù)雜度度量方法：考慮操作如果按位進(jìn)行所需要執(zhí)行的“步數(shù)”2023/1/8算法復(fù)雜性算法時(shí)間復(fù)雜度的度量方法2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性-普通代數(shù)運(yùn)算2023/1/8算法復(fù)雜性-普通代數(shù)運(yùn)算2023/1/8算法復(fù)雜性-模運(yùn)算2023/1/8算法復(fù)雜性-模運(yùn)算2023/1/8算法復(fù)雜性-有限域2023/1/8算法復(fù)雜性-有限域2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8如果將模運(yùn)算視為基本運(yùn)算單位（即一次模運(yùn)算花費(fèi)一個(gè)時(shí)間單位），則算法的時(shí)間復(fù)雜度為2max(|a|,|b|)。

算法復(fù)雜性（續(xù)）2023/1/8如果將模運(yùn)算視為基本運(yùn)算單位算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8計(jì)算復(fù)雜性在信息安全中的應(yīng)用

在信息安全中，很難界定一個(gè)密碼體制是否是安全的。在經(jīng)典密碼學(xué)中，安全性的判定是基于信息論的。信息論關(guān)注的是密文當(dāng)中到底包含多少關(guān)于明文的信息。密文中關(guān)于明文的信息量越大，密碼體制就越不安全。而只有當(dāng)密文中不包含關(guān)于明文的信息時(shí)，密碼體制才是絕對(duì)安全的。香農(nóng)證明過(guò)這種完美的安全性只有當(dāng)密鑰跟明文長(zhǎng)度相等時(shí)，才能達(dá)到。這種安全性限制下的密碼體制，其應(yīng)用是非常困難。2023/1/8計(jì)算復(fù)雜性在信息安全中的應(yīng)用在信息安全中，很難界定一個(gè)密碼計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）

在現(xiàn)代密碼學(xué)當(dāng)中，對(duì)安全性的判定是基于計(jì)算復(fù)雜性的。密文中是否包含明文的信息，這個(gè)問(wèn)題對(duì)安全性來(lái)說(shuō)并不重要。關(guān)鍵是有沒(méi)有有效的方法將密文中關(guān)于明文的信息提取出來(lái)。換句話說(shuō)，基于計(jì)算復(fù)雜性的密碼學(xué)所關(guān)心的不是密碼分析者是否有可能破譯算法（實(shí)際上，除了一次一密外，所有的密碼體制都是有可能被破譯），而是關(guān)心密碼分析者是否具有相應(yīng)的資源和時(shí)間來(lái)破譯算法。2023/1/8計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）在現(xiàn)代密碼學(xué)當(dāng)中，對(duì)安全計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）例如:如果一個(gè)密碼算法的破譯只是一個(gè)P類問(wèn)題，這個(gè)算法當(dāng)然會(huì)被認(rèn)為是不安全。一個(gè)需要宇宙年齡那么長(zhǎng)的時(shí)間才能破譯的算法，當(dāng)然有理由認(rèn)為是安全的。2023/1/8計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）例如:2023/1/8計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）基于復(fù)雜性理論的現(xiàn)代密碼學(xué)將NP≠P作為一個(gè)必要條件，加密算法中，擁有正確加密/解密密鑰的用戶進(jìn)行加密/解密是易處理的問(wèn)題，而對(duì)于密碼攻擊者或分析者，從密文中提取明文或不用正確的密鑰構(gòu)造合法的密文應(yīng)該是一個(gè)難解的問(wèn)題。而很多加密算法是基于NP完全問(wèn)題的，即這類型的算法中，分析和破譯是一個(gè)NP完全問(wèn)題。我們稱之為NP≠P猜想。2023/1/8計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）基于復(fù)雜性理論的現(xiàn)代密碼學(xué)計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）如果NP＝P，則分析和破譯加密算法是一個(gè)多項(xiàng)式時(shí)間問(wèn)題，即易處理的問(wèn)題。那么這些加密算法將失去其安全性。因此，如果這個(gè)猜想不正確，現(xiàn)在密碼學(xué)將失去其一個(gè)至關(guān)重要的理論基礎(chǔ)。2023/1/8計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）如果NP＝P，則分析和破譯計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）另一方面，即使NP≠P猜想成立，基于NP完全問(wèn)題難解性的密碼算法也不一定是安全的。例如：基于NP完全的著名的背包問(wèn)題破解就是一個(gè)反例。這是因?yàn)榧词挂粋€(gè)問(wèn)題只有可以忽略的少數(shù)困難實(shí)例，該問(wèn)題也被認(rèn)為是困難的。相反，密碼分析只要能破解不可忽略比例的實(shí)例，就認(rèn)為是成功的。這就是為什么破解一個(gè)基于NP完全問(wèn)題的密碼體制未必導(dǎo)致其基于的NP完全問(wèn)題的求解。2023/1/8計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）另一方面，即使NP≠P猜想計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）基于復(fù)雜性理論中的困難性作為現(xiàn)代密碼學(xué)的安全性基礎(chǔ)是不充分的近年來(lái)，密碼學(xué)界廣泛推崇一種被稱為可證明安全性的密碼系統(tǒng)。這種密碼系統(tǒng)采用一種被稱為多項(xiàng)式規(guī)約技術(shù)的形式化方法來(lái)證明一種密碼體制的安全性。在多項(xiàng)式規(guī)約技術(shù)中，將對(duì)密碼體制的攻擊規(guī)約到求解一類已知的NP問(wèn)題的一個(gè)實(shí)例。這種方法證明如果這種密碼體制是可破譯的，則它所基于的NP問(wèn)題實(shí)例是可解的。2023/1/8計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）基于復(fù)雜性理論中的困難性作計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）例如，最常用的多項(xiàng)式規(guī)約技術(shù)，就是將密碼算法的安全性規(guī)約到大整數(shù)分解困難性問(wèn)題。由于人們廣泛相信這種實(shí)例沒(méi)有有效的解法，所以對(duì)于考慮中的密碼體制的安全性，這樣的一個(gè)證明提供了很高的可信度。

2023/1/8計(jì)算復(fù)雜性在信息安全中的應(yīng)用（續(xù)）例如，最常用的多項(xiàng)式規(guī)約技教材與參考書(shū)教材：李毅超曹躍，網(wǎng)絡(luò)與系統(tǒng)攻擊技術(shù)電子科大出版社2007周世杰陳偉鐘婷，網(wǎng)絡(luò)與系統(tǒng)防御技術(shù)電子科大出版社2007

參考書(shū)闕喜戎等編著，信息安全原理及應(yīng)用，清華大學(xué)出版社ChristopherM.King,CuritisE.Dalton,T.ErtemOsmanoglu（常曉波等譯）.安全體系結(jié)構(gòu)的設(shè)計(jì)、部署與操作，清華大學(xué)出版社，2003(ChristopherM.King,etal,SecurityArchitecture,design,deployment&Operations)WilliamStallings，密碼編碼學(xué)與網(wǎng)絡(luò)安全－原理與實(shí)踐（第四版），電子工業(yè)出版社蔡皖東，網(wǎng)絡(luò)與信息安全，西北工業(yè)大學(xué)出版社，2004李建平，小波分析與信息處理---理論、應(yīng)用及軟件實(shí)現(xiàn)，1997年第一版，2001年第二版，2003年第二版修訂版。張世永，網(wǎng)絡(luò)安全原理與應(yīng)用，科學(xué)出版社，2003楊義先等，信息安全理論與技術(shù)，郵電出版社2023/1/8教材與參考書(shū)教材：2023/1/8AnyQuestion?Q&A2023/1/8AnyQuestion?2023/1/880Thankyou!80Thankyou!信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)題復(fù)雜性算法復(fù)雜性信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)題復(fù)雜性算法第2章信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)題復(fù)雜性算法復(fù)雜性第2章信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)計(jì)算復(fù)雜性基礎(chǔ)

2023/1/8

－古書(shū)《孟子·離婁上》有這樣的記載： 淳于髡曰：男女授受不親，禮與？ 孟子曰：禮也。 曰：嫂溺則授之以手乎？ 曰：嫂溺不授，是豺狼也。男女授受不親，禮也；嫂溺授之以手，權(quán)也。－雖然有“男女授受不親”的原則存在，但嫂子落水快淹死時(shí)，必須拉她、救她，這是“權(quán)”(變通)，否則，見(jiàn)死不救，就是豺狼。－曰：「今天下溺矣，夫子之不援何也？」

曰：「天下溺援之以道；嫂溺援之以手。子欲手援天下乎？」計(jì)算復(fù)雜性基礎(chǔ)2023/1/8計(jì)算復(fù)雜性為什么要學(xué)習(xí)計(jì)算復(fù)雜性？計(jì)算復(fù)雜性是研究密碼分析對(duì)于計(jì)算量的需求和密碼分析的困難程度，從而得出這些密碼技術(shù)和算法在現(xiàn)有可行的條件下是否具有足夠的安全性。學(xué)習(xí)計(jì)算復(fù)雜性，需要掌握兩個(gè)概念：?jiǎn)栴}算法2023/1/8計(jì)算復(fù)雜性為什么要學(xué)習(xí)計(jì)算復(fù)雜性？2023/1/8問(wèn)題（problem）

（問(wèn)題）定義：即需要回答的一般性提問(wèn):它通常含有若干個(gè)參數(shù)。對(duì)于一個(gè)問(wèn)題進(jìn)行描述應(yīng)該包括兩方面的內(nèi)容：必須對(duì)問(wèn)題的所有給定參數(shù)給出一般性描述；必須描述該問(wèn)題的答案（或解）應(yīng)該滿足的性質(zhì)。當(dāng)問(wèn)題的所有參數(shù)都有了確定的取值時(shí)，我們稱得到了該問(wèn)題的一個(gè)實(shí)例（instance）。2023/1/8問(wèn)題（problem）（問(wèn)題）定義：即需要回答的一般性提問(wèn)算法（algorithm）

定義（算法）：即求解某個(gè)問(wèn)題的一系列具體步驟（通常被理解為求解所需的通用計(jì)算程序）。算法總是針對(duì)具體問(wèn)題而言的，求解一個(gè)問(wèn)題的算法通常不止一個(gè)。當(dāng)某個(gè)算法能夠回答一個(gè)問(wèn)題的任何實(shí)例時(shí)，我們稱該算法能夠回答這個(gè)問(wèn)題。當(dāng)一個(gè)問(wèn)題至少有一個(gè)能夠回答該問(wèn)題的算法時(shí)，我們稱該問(wèn)題可解（resolvable），否則稱該問(wèn)題不可解（unresolvable）。2023/1/8算法（algorithm）定義（算法）：即求解某個(gè)問(wèn)題的算法（algorithm）（續(xù)）

有關(guān)算法的幾點(diǎn)注釋：算法總有輸入和輸出算法輸入大小一般用輸入變量的長(zhǎng)度（單位為位）來(lái)表示一般來(lái)說(shuō)，算法用某種編程語(yǔ)言來(lái)實(shí)現(xiàn)的計(jì)算機(jī)程序一般來(lái)說(shuō)，我們僅僅關(guān)注解決問(wèn)題最有效的算法2023/1/8算法（algorithm）（續(xù)）有關(guān)算法的幾點(diǎn)注釋：202問(wèn)題與算法問(wèn)題：如何求解兩個(gè)整數(shù)a和b的最大公約數(shù)？參數(shù)：a和b問(wèn)題實(shí)例：a＝20，b＝30算法：利用因子分解求a＝20和b＝30的最大公約數(shù)a＝22×5b＝2×3×5因此a和b的最大公約數(shù)是2×5＝102023/1/8問(wèn)題與算法問(wèn)題：如何求解兩個(gè)整數(shù)a和b的最大公約數(shù)？2023算法復(fù)雜性

（算法復(fù)雜度）定義：即度量該算法所需的計(jì)算能力，包括：時(shí)間復(fù)雜性T（timecomplexity）；空間復(fù)雜性S（spacecomplexity）；信道帶寬；數(shù)據(jù)總量；……2023/1/8算法復(fù)雜性（算法復(fù)雜度）定義：即度量該算法所需的計(jì)算能力算法復(fù)雜性（續(xù)）計(jì)算復(fù)雜性的表示符號(hào)為“O”（稱為“大O”，即算法的階號(hào)），表示計(jì)算復(fù)雜性的數(shù)量級(jí)

好處：使算法復(fù)雜性度量與處理器的運(yùn)行速度和指令運(yùn)行時(shí)間無(wú)關(guān)；明確地揭示了輸入的數(shù)據(jù)長(zhǎng)度對(duì)算法復(fù)雜性的影響。

2023/1/8算法復(fù)雜性（續(xù)）計(jì)算復(fù)雜性的表示符號(hào)為“O”（稱為“大O算法復(fù)雜性（續(xù)）算法常見(jiàn)復(fù)雜性分類（1）常數(shù)算法（constantAlgorithm）：如果運(yùn)行時(shí)間是O(1)，即該算法的復(fù)雜性不依賴于n。（2）線性算法（linearAlgorithm）：如果運(yùn)行時(shí)間是O(n)。（3）多項(xiàng)式算法（polynomialAlgorithm）：如果運(yùn)行時(shí)間是O(nm)，其中m是一個(gè)常數(shù)。具有多項(xiàng)式復(fù)雜性的算法族被稱為多項(xiàng)式時(shí)間算法。（4）超多項(xiàng)式算法（superpolynomialAlgorithm）：如果運(yùn)行時(shí)間是，其中c是一個(gè)常數(shù)，而s(n)是關(guān)于n的大于常數(shù)而小于線性的函數(shù)。（5）指數(shù)算法（exponentialAlgorithm）：如果運(yùn)行時(shí)間是，其中t是大于1的常數(shù)，f(n)是關(guān)于n的多項(xiàng)式函數(shù)。2023/1/8算法復(fù)雜性（續(xù)）算法常見(jiàn)復(fù)雜性分類2023/1/8算法復(fù)雜性（續(xù)）算法常見(jiàn)復(fù)雜性分類一般而言，常數(shù)算法、線性算法、多項(xiàng)式算法和超多項(xiàng)式算法統(tǒng)稱為多項(xiàng)式算法。所謂多項(xiàng)式，就是具有下列形式的一個(gè)函數(shù)：2023/1/8其中，k和ck是常數(shù)，且ci稱≠0為。當(dāng)k>0時(shí)，k稱為多項(xiàng)式的次數(shù)，ci稱為多項(xiàng)式的系數(shù)。

算法復(fù)雜性（續(xù)）算法常見(jiàn)復(fù)雜性分類2023/1/8其中，k和算法復(fù)雜性算法的分類及其運(yùn)行時(shí)間

算法類型復(fù)雜性運(yùn)算次數(shù)n＝106時(shí)間多項(xiàng)式算法常數(shù)算法O(1)11微秒線性算法O(n)1061秒二次多項(xiàng)式算法O(n2)101211.6天三次多項(xiàng)式算法O(n3)101832,000年指數(shù)算法O(2n)1030103010301006年2023/1/8算法復(fù)雜性（續(xù)）算法復(fù)雜性算法的分類及其運(yùn)行時(shí)間算法類型復(fù)雜性運(yùn)算算法復(fù)雜性算法復(fù)雜度的增長(zhǎng)速度2023/1/8算法復(fù)雜性（續(xù)）亞指數(shù)指數(shù)多項(xiàng)式算法復(fù)雜性算法復(fù)雜度的增長(zhǎng)速度2023/1/8算法復(fù)算法復(fù)雜性（續(xù)）研究問(wèn)題的內(nèi)在復(fù)雜性，即在圖靈機(jī)上解決最難的問(wèn)題實(shí)例所需的最小時(shí)間和空間條件。圖靈機(jī)是一種具有無(wú)限讀、寫(xiě)存儲(chǔ)帶的有限狀態(tài)機(jī)，可以被當(dāng)作一個(gè)實(shí)際可用的計(jì)算模型。2023/1/8算法復(fù)雜性（續(xù)）研究問(wèn)題的內(nèi)在復(fù)雜性，即在圖靈機(jī)上解決最難的第2章信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)題復(fù)雜性算法復(fù)雜性第2章信息安全數(shù)學(xué)基礎(chǔ)（計(jì)算復(fù)雜性）2023/1/8問(wèn)問(wèn)題復(fù)雜性

圖靈機(jī)分為兩類：確定性圖靈機(jī)。非確定性圖靈機(jī)2023/1/8問(wèn)題復(fù)雜性圖靈機(jī)分為兩類：2023/1/8問(wèn)題復(fù)雜性（續(xù)）確定性圖靈機(jī)。確定性圖靈機(jī)的輸出結(jié)果只取決于輸入和初始狀態(tài)。因此，對(duì)于具有相同輸入和初始狀態(tài)，運(yùn)行一個(gè)確定性圖靈機(jī)所得到的結(jié)果是完全相同的。非確定性圖靈機(jī)：能夠進(jìn)行猜測(cè)。求解一個(gè)問(wèn)題分兩個(gè)階段：猜測(cè)階段和驗(yàn)證階段。2023/1/8問(wèn)題復(fù)雜性（續(xù)）確定性圖靈機(jī)。2023/1/8圖靈機(jī)圖靈機(jī)包括一個(gè)有限狀態(tài)控制單元、k（≥1）條紙帶（Tape）和k個(gè)讀寫(xiě)頭（Tapehead）。有限狀態(tài)控制單元控制每個(gè)讀寫(xiě)頭訪問(wèn)一條紙帶，并沿著紙帶左右移動(dòng)圖靈機(jī)求解問(wèn)題的輸入是一個(gè)有限長(zhǎng)度的字符串，該輸入占據(jù)每條紙帶無(wú)限個(gè)單元的最左邊的有限個(gè)單元。讀寫(xiě)頭對(duì)紙帶的一次訪問(wèn)稱之為一個(gè)合法移動(dòng)（Move）。2023/1/8圖靈機(jī)圖靈機(jī)包括一個(gè)有限狀態(tài)控制單元、k（≥1）條紙帶（Ta圖靈機(jī)（續(xù)）圖靈機(jī)求解問(wèn)題時(shí)，被賦予一個(gè)初始狀態(tài)（InitialState），且一步一步地移動(dòng)，從而完成對(duì)輸入的掃描。如果圖靈機(jī)最終掃描了整個(gè)輸入串，且滿足了中止條件而停止下來(lái)，則稱圖靈機(jī)識(shí)別了該輸入。否則，圖靈機(jī)在某一點(diǎn)沒(méi)有合法移動(dòng)，因此會(huì)沒(méi)有識(shí)別輸入串而停止下來(lái)，此時(shí)稱圖靈機(jī)無(wú)法識(shí)別該輸入。圖靈機(jī)所識(shí)別的一個(gè)輸入，稱為一種可識(shí)別語(yǔ)言的一個(gè)實(shí)例。2023/1/8圖靈機(jī)（續(xù)）圖靈機(jī)求解問(wèn)題時(shí)，被賦予一個(gè)初始狀態(tài)（Initi圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)?jiān)O(shè)計(jì)一個(gè)圖靈機(jī)，用于證明某個(gè)非負(fù)整數(shù)是否圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1100)能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制1011)能被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝12(二進(jìn)制10圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)不能被3整除。2023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制1101)被3整除。當(dāng)前狀態(tài)紙帶上的符號(hào)下一步移動(dòng)下一個(gè)狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22023/1/8圖靈機(jī)（續(xù)）例如：請(qǐng)用DIV3圖靈機(jī)證明a＝13(二進(jìn)制11問(wèn)題復(fù)雜性

借助于圖靈機(jī)理論，問(wèn)題復(fù)雜型實(shí)際上就是在圖靈機(jī)上解決最難的問(wèn)題實(shí)例所需要的最小時(shí)間最小空間2023/1/8問(wèn)題復(fù)雜性借助于圖靈機(jī)理論，問(wèn)題復(fù)雜型實(shí)際上就是在圖靈機(jī)上圖靈機(jī)（續(xù)）圖靈機(jī)M識(shí)別一個(gè)長(zhǎng)度為n的輸入串而移動(dòng)的步數(shù)稱為圖靈機(jī)的時(shí)間復(fù)雜性，記為：當(dāng)圖靈機(jī)M識(shí)別一個(gè)長(zhǎng)度為n的輸入串，其寫(xiě)操作中讀寫(xiě)頭所訪問(wèn)的紙帶單元數(shù)稱為圖靈機(jī)的空間復(fù)雜性，記為：2023/1/8圖靈機(jī)（續(xù)）圖靈機(jī)M識(shí)別一個(gè)長(zhǎng)度為n的輸入串而移動(dòng)的步數(shù)稱為圖靈機(jī)（續(xù)）2023/1/8圖靈機(jī)（續(xù)）2023/1/8問(wèn)題分類如果一個(gè)問(wèn)題在確定性圖靈機(jī)上能夠在多項(xiàng)式時(shí)間內(nèi)得到處理，則稱該問(wèn)題時(shí)易處理的（tractable）。也既是說(shuō)，能夠用多項(xiàng)式時(shí)間解決的問(wèn)題稱之為易處理的。不能夠在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題是難處理的。因?yàn)殡S著輸入尺寸的增加，求解這類問(wèn)題需要的時(shí)間迅速變得很長(zhǎng)，以至于不可能有效的求解。難處理的問(wèn)題也被稱為是難解的。2023/1/8問(wèn)題分類如果一個(gè)問(wèn)題在確定性圖靈機(jī)上能夠在多項(xiàng)式時(shí)間內(nèi)得到處P類問(wèn)題易處理問(wèn)題的全體稱為“多項(xiàng)式時(shí)間可解類”，記為P類。復(fù)雜度類P包含所有能用多項(xiàng)式時(shí)間解決的問(wèn)題。2023/1/8上述定義表明，如果L是多項(xiàng)式時(shí)間內(nèi)可識(shí)別的語(yǔ)言，則確定性圖靈機(jī)可以在多項(xiàng)式時(shí)間內(nèi)，判定一個(gè)字符串是否屬于語(yǔ)言L。P類問(wèn)題易處理問(wèn)題的全體稱為“多項(xiàng)式時(shí)間可解類”，記為P類。NP類問(wèn)題有這樣一類問(wèn)題，雖然不能夠用確定性圖靈機(jī)來(lái)有效求解，但是卻可以用非確定性圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)得到處理這類問(wèn)題稱為“非確定性多項(xiàng)式時(shí)間可解問(wèn)題”，簡(jiǎn)稱NP問(wèn)題。2023/1/8定義（NP類）NP類表示用非確定性圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)可以識(shí)別的語(yǔ)言類。NP類問(wèn)題有這樣一類問(wèn)題，雖然不能夠用確定性圖靈機(jī)來(lái)有效求解NP類問(wèn)題（續(xù)）意義：能夠通過(guò)非確定性的多項(xiàng)式時(shí)間算法對(duì)許多對(duì)稱密鑰算法和所有公鑰算法進(jìn)行攻擊。NP完全問(wèn)題：指NP中的任何一個(gè)問(wèn)題都可以通過(guò)多項(xiàng)式時(shí)間轉(zhuǎn)化為該問(wèn)題。NP完全問(wèn)題的全體被記為NPC。NP完全問(wèn)題是NP問(wèn)題中最難的問(wèn)題。

2023/1/8定義2.3.3（NP完全類）如果任意:

是非確定性多項(xiàng)式時(shí)間完全的（NP完全的）都可以多項(xiàng)式規(guī)約到語(yǔ)言，則稱:NP類問(wèn)題（續(xù)）意義：能夠通過(guò)非確定性的多項(xiàng)式時(shí)間算法對(duì)許多NP類問(wèn)題（續(xù)）NP中的任何一個(gè)問(wèn)題都可以通過(guò)多項(xiàng)式時(shí)間轉(zhuǎn)化為該問(wèn)題。NP完全問(wèn)題的全體被記為NPC。NP完全問(wèn)題是NP問(wèn)題中最難的問(wèn)題。2023/1/8NP類問(wèn)題（續(xù)）NP中的任何一個(gè)問(wèn)題都可以通過(guò)多項(xiàng)式時(shí)間轉(zhuǎn)化算法復(fù)雜性算法時(shí)間復(fù)雜度的度量方法圖靈機(jī)解決問(wèn)題所移動(dòng)的步數(shù)（該時(shí)間稱之為算法的運(yùn)行時(shí)間）該度量方法的缺點(diǎn)：沒(méi)有考慮每一步具體的操作例如：加法和乘法的計(jì)算開(kāi)銷是不同的為此，引入算法“按位”的計(jì)算復(fù)雜度度量方法：考慮操作如果按位進(jìn)行所需要執(zhí)行的“步數(shù)”2023/1/8算法復(fù)雜性算法時(shí)間復(fù)雜度的度量方法2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性-普通代數(shù)運(yùn)算2023/1/8算法復(fù)雜性-普通代數(shù)運(yùn)算2023/1/8算法復(fù)雜性-模運(yùn)算2023/1/8算法復(fù)雜性-模運(yùn)算2023/1/8算法復(fù)雜性-有限域2023/1/8算法復(fù)雜性-有限域2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8如果將模運(yùn)算視為基本運(yùn)算單位（即一次模運(yùn)算花費(fèi)一個(gè)時(shí)間單位），則算法的時(shí)間復(fù)雜度為2max(|a|,|b|)。

算法復(fù)雜性（續(xù)）2023/1/8如果將模運(yùn)算視為基本運(yùn)算單位算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8算法復(fù)雜性（續(xù)）2023/1/8計(jì)算復(fù)雜性在信息安全中的應(yīng)用

在信