《信息安全數(shù)學(xué)基礎(chǔ)》知識(shí)點(diǎn)及關(guān)系 電子教案

PAGEPAGE1《信息安全數(shù)學(xué)基礎(chǔ)》（姜正濤，電子工業(yè)出版社，2017.12）知識(shí)點(diǎn)及關(guān)系第1章整數(shù)的整除與唯一分解推廣的歐幾里德算法（定理1.5）√√推廣的歐幾里德算法（定理1.5）√√輾轉(zhuǎn)相除法（歐幾里德算法、定理1.3）√√輾轉(zhuǎn)相除法（歐幾里德算法、定理1.3）√√算法1.1(歐幾里德算法)多個(gè)整數(shù)的公因子、最大公因子、定理1.7*定理1.2(帶余除法最大公因子關(guān)系)定理1.2(帶余除法最大公因子關(guān)系)→互素√→互素√公因子、最大公因子不整除整數(shù)、自然數(shù)→整除、→因子（真因子、平凡因子）、倍數(shù)→公倍數(shù)、最小公倍數(shù)→最小公倍數(shù)求法（定理1.8、定理1.9*）不整除→整數(shù)的a→整數(shù)的a進(jìn)制表示帶余除法（歐幾里德除法）√素?cái)?shù)素?cái)?shù)√、合數(shù)→整數(shù)唯一分解定理（定理1.12）√素?cái)?shù)與整數(shù)的關(guān)系（定理1.10）、素?cái)?shù)與整數(shù)乘積的關(guān)系（定理1.11）→整數(shù)唯一分解定理（定理1.12）√素?cái)?shù)與整數(shù)的關(guān)系（定理1.10）、素?cái)?shù)與整數(shù)乘積的關(guān)系（定理1.11）Mersenne（素）數(shù)Mersenne（素）數(shù)*、Fermat（素）數(shù)*素?cái)?shù)有無(wú)窮多（定理1.14）、素?cái)?shù)定理（定理1.16）素?cái)?shù)有無(wú)窮多（定理1.14）、素?cái)?shù)定理（定理1.16）素?cái)?shù)判斷定理（定理1.17）孿生素?cái)?shù)、哥德巴赫猜想孿生素?cái)?shù)、哥德巴赫猜想*第2章同余式不同余整除、帶余除法（第1章）→同余→兩個(gè)整數(shù)同余的充要條件（定理2.1、推論2.1）→同余的性質(zhì)（定理2.2、推論2.2√）不同余剩余類剩余類√、完全剩余類、完全剩余系、最小完全剩余系縮系完全剩余系的判斷（定理2.4）與性質(zhì)（定理2.5）剩余類的性質(zhì)（定理2.3）縮系完全剩余系的判斷（定理2.4）與性質(zhì)（定理2.5）剩余類的性質(zhì)（定理2.3）歐拉函數(shù)（定義2.4）√→縮系個(gè)數(shù)（定理2.6）→縮系性質(zhì)（定理2.7）→歐拉定理（定理2.8）√√→費(fèi)馬小定理（定理2.9）√→定理2.10√→推論2.3→推論2.3√√定理2.11、定理2.12→歐拉函數(shù)計(jì)算式（定理2.13）√→→歐拉函數(shù)計(jì)算式（定理2.13）√→歐拉函數(shù)為積性函數(shù)積性函數(shù)歐拉函數(shù)的一個(gè)性質(zhì)（定理2.14歐拉函數(shù)的一個(gè)性質(zhì)（定理2.14*）→模逆元計(jì)算（定理2.16）√→模逆元計(jì)算（定理2.16）√→一次同余式系數(shù)與?；ニ貢r(shí)同余式解數(shù)（定理2.15）√同余式→一次同余式的解數(shù)（定理2.18）√一次同余式可解性判斷（定理2.17）√→一次同余式的解數(shù)（定理2.18）√一次同余式可解性判斷（定理2.17）√n次同余式的解數(shù)（定理2.20）一次同余式的求解（定理2.19）n次同余式的解數(shù)（定理2.20）一次同余式的求解（定理2.19）√→模為合數(shù)時(shí)一般同余式的解數(shù)（定理2.23→模為合數(shù)時(shí)一般同余式的解數(shù)（定理2.23*）中國(guó)剩余定理（定理2.21）√√√RSA公鑰密碼體制（算法2.1）RSA公鑰密碼體制（算法2.1）√√√第3章二次剩余同余式（第2章）→二次剩余→二次同余式的解數(shù)（定理3.1）→二次剩余的歐拉判別法（定理3.2）√→二次剩余的性質(zhì)（推論3.1）→勒讓德符號(hào)的性質(zhì)（定理3.4）→→勒讓德符號(hào)的性質(zhì)（定理3.4）→勒讓德符號(hào)值計(jì)算√：（定理3.3、推論3.2、推論3.3、定理3.5）、二次互反律（定理3.6）√√勒讓德符號(hào)→→Goldwasser-Micali公鑰加密算法（算法3.1）→雅可比符號(hào)值計(jì)算√：（定理3.8、定理3.9）、雅可比符號(hào)互反律（定理3.10）√√雅可比符號(hào)→雅可比符號(hào)的性質(zhì)（定理3.7）二次同余式的求解→定理3.11(1)√(2)*、定理3.12*Rabin公鑰密碼體制（算法3.Rabin公鑰密碼體制（算法3.2）√√第4章原根與階模整數(shù)的階→階的性質(zhì)（定理4.1，推論4.1）→原根的定義√→模整數(shù)階的計(jì)算（定理4.11）→模→模整數(shù)階的計(jì)算（定理4.11）→模p原根的形式（定理4.10）模整數(shù)原根的形式（推論4.2、定理4.14）→模p原根個(gè)數(shù)（定理4.8）√模p階為d的元素個(gè)數(shù)（定理4.7）模整數(shù)原根的判斷（定理4.1模整數(shù)原根的判斷（定理4.16）√Fermat素性檢測(cè)的反例—卡米歇爾數(shù)（很少）第5Fermat素性檢測(cè)的反例—卡米歇爾數(shù)（很少）素性檢測(cè)定義→確定性算法（定理1.17、定理5.1、定理5.2、定理5.3、定理5.4）→（費(fèi)馬）擬素?cái)?shù)√擬素?cái)?shù)→→（費(fèi)馬）擬素?cái)?shù)√擬素?cái)?shù)→Fermat素性檢測(cè)（算法5.1）√→Fermat素性檢測(cè)的成功概率（定理5.8）→（費(fèi)馬）擬素?cái)?shù)無(wú)窮多（定理5.6、定理5.7）→基于歐拉定理的素性檢測(cè)成功概率（定理5.10）→歐拉擬素?cái)?shù)也是費(fèi)馬擬素?cái)?shù)（定理5.9）歐拉擬素?cái)?shù)→基于歐拉定理的素性檢測(cè)成功概率（定理5.10）→歐拉擬素?cái)?shù)也是費(fèi)馬擬素?cái)?shù)（定理5.9）歐拉擬素?cái)?shù)√Solavay-Steassen素性檢測(cè)Solavay-Steassen素性檢測(cè)（算法5.2）√→Rabin-Miller素性檢測(cè)（算法→Rabin-Miller素性檢測(cè)（算法5.3）√→強(qiáng)擬素?cái)?shù)概率（定理5.14）→強(qiáng)擬素?cái)?shù)無(wú)窮多（定理5.12）素?cái)?shù)的一個(gè)性質(zhì)（定理5.11）→強(qiáng)擬素?cái)?shù)√第6章群→子群的性質(zhì)（定理6.3）→子群的判斷（定理6.2）子群集合、二元運(yùn)算、單位元、逆元→群（定義6.5）√√√→群的性質(zhì)（定理6.1）→子群的性質(zhì)（定理6.3）→子群的判斷（定理6.2）子群→元素階的性質(zhì)（定理6.4）√群的階、元素的階→元素階的性質(zhì)（定理6.4）√群的階、元素的階√元素階與元素最大階的關(guān)系（定理6.5）√元素階與元素最大階的關(guān)系（定理6.5）√循環(huán)群（定義6.10）循環(huán)群（定義6.10）√√陪集要么相等要么無(wú)公共元（定理6.7）→陪集要么相等要么無(wú)公共元（定理6.7）→陪集的元素?cái)?shù)相等（定理6.6）→子群的指數(shù)（定義6.12）→群是不相交的子群陪集的并（定理6.8）陪集（定義6.11）正規(guī)子群（定義6.13）拉格朗日定理（群、子群、子群指數(shù)的關(guān)系）（定理6.9正規(guī)子群（定義6.13）拉格朗日定理（群、子群、子群指數(shù)的關(guān)系）（定理6.9）正規(guī)子群的所有陪集構(gòu)成一個(gè)群（定理6.12正規(guī)子群的所有陪集構(gòu)成一個(gè)群（定理6.12）元素階整除群階（定理6.10）√√商群（定義6.14）√商群（定義6.14）√群同態(tài)、群同構(gòu)（定義6.16）→群同態(tài)定理（定理6.13、定理6.14）有限階（無(wú)限階）循環(huán)群生成元的個(gè)數(shù)（定理6.17）√循環(huán)群（定義6.10）√√→有限階（無(wú)限階）循環(huán)群的性質(zhì)（定理6.15、推論6.1、推論6.2）→n階循環(huán)群當(dāng)且僅當(dāng)含n階元素（定理6.有限階（無(wú)限階）循環(huán)群生成元的個(gè)數(shù)（定理6.17）√與有限階（無(wú)限階）循環(huán)群同構(gòu)的群（定理6.18與有限階（無(wú)限階）循環(huán)群同構(gòu)的群（定理6.18）循環(huán)群的子群是循環(huán)群（定理6.循環(huán)群的子群是循環(huán)群（定理6.19）√√循環(huán)群的子群個(gè)數(shù)（定理6.循環(huán)群的子群個(gè)數(shù)（定理6.20）√置換群（定義6.21）→n元集合的全體置換構(gòu)成n!階群（定理6.22）→不同置換的乘法、平方、逆運(yùn)算→不同置換的乘法、平方、逆運(yùn)算k-循環(huán)置換（定義6.22）第7章環(huán)子環(huán)環(huán)的定義（定義7.1）→環(huán)中元素運(yùn)算（定理7.1）子環(huán)→整環(huán)（定義7.7）零因子→整環(huán)（定義7.7）零因子→無(wú)零因子環(huán)元素的特征相等（定理7.3）√→→無(wú)零因子環(huán)元素的特征相等（定理7.3）√→環(huán)的特征（定義7.1）√環(huán)中元素的（加法）階（定義7.10）→商環(huán)（定義7.15→商環(huán)（定義7.15）多項(xiàng)式環(huán)NTRU密碼體制(NTRU密碼體制(算法7.1)無(wú)零因子環(huán)的特征要么為0要么為素?cái)?shù)（定理7.4）√域的特征（定義8.4）√第8章域域的特征（定義8.4）√整環(huán)（定義7.7）整環(huán)（定義7.7）→分式域（定義8.3）Zp是域<=>p是素?cái)?shù)（定理8.2）√域（定義8.1）→擴(kuò)域、子域（定義8.2）Zp是域<=>p是素?cái)?shù)（定理8.2）√素域的定義（定義8.6）→每個(gè)域只包含一個(gè)素域（定理8.素域的定義（定義8.6）→每個(gè)域只包含一個(gè)素域（定理8.4）√→與素域同構(gòu)的兩類域（定理8.3）整除、帶余除法（第1章）多項(xiàng)式整除、因式、倍式、最大公因式整除、帶余除法（第1章）多項(xiàng)式整除、因式、倍式、最大公因式多項(xiàng)式帶余除法（定理8.6）多項(xiàng)式帶余除法（定理8.6）、多項(xiàng)式的擴(kuò)展歐幾里德算法（定理8.8）√不可約多項(xiàng)式不可約多項(xiàng)式（定義8.10）√、多項(xiàng)式唯一分解定理（定理8.11）pp(x)不可約則商環(huán)F[x]/(p(x))是域（定理8.12），即擴(kuò)域的構(gòu)造方法√域同構(gòu)（定義8.5）可通過(guò)逐步添加元素獲得更大的擴(kuò)域（定理8.13可通過(guò)逐步添加元素獲得更大的擴(kuò)域（定理8.13）→單代數(shù)擴(kuò)域（定義8.→單代數(shù)擴(kuò)域（定義8.13）代數(shù)元（定義8.12）→n→n次代數(shù)元（定義8.14）極小多項(xiàng)式（定義8.14）√→擴(kuò)張次數(shù)之間的關(guān)系（定理8.19）√n次代數(shù)擴(kuò)域的多項(xiàng)式基（定理8.1→擴(kuò)張次數(shù)之間的關(guān)系（定理8.19）√n次代數(shù)擴(kuò)域的多項(xiàng)式基（定理8.17、定義8.15）√→n次代數(shù)擴(kuò)域的構(gòu)造（定理8.16）√極小多項(xiàng)式唯一（定理8.15）擴(kuò)張次數(shù)（定義8.擴(kuò)張次數(shù)（定義8.17）→多項(xiàng)式的分裂域彼此同構(gòu)（定理8.→多項(xiàng)式的分裂域彼此同構(gòu)（定理8.23*）多項(xiàng)式的分裂域（定義8.19）*第9章有限域有限域（定義8.1）→有限域元素的個(gè)數(shù)（定理9.1、定理9.2）√Diffie-Hellman密鑰協(xié)商(算法9.1)√√q元有限域是子域上多項(xiàng)式xq–x的分裂域（定理9.8）元素階整除群階（定理6.10-11）→有限域中非零元素的（乘法）階（定理9.3、定理9.4）→有限域中的乘法群FDiffie-Hellman密鑰協(xié)商(算法9.1)√√q元有限域是子域上多項(xiàng)式xq–x的分裂域（定理9.8）q元有限域存在唯一性定理（定理9.9）q元有限域存在唯一性定理（定理9.9）√對(duì)于任何有限域存在任意次不可約多項(xiàng)式（定理9.11）→在有限域上可以構(gòu)造任意次擴(kuò)域（有限域擴(kuò)域的構(gòu)造）√√√→AES中的有限域運(yùn)算（9.6節(jié)）√有限域上多項(xiàng)式的階（定義9.7）→有限域上不可約多項(xiàng)式的階等于其任一根的階（定理9.19）→本原多項(xiàng)式（定義9.8）→本原多項(xiàng)式的階（定理9.20）√第10章有限域上的橢圓曲線橢圓曲線（定義10.1）→非奇異橢圓曲線（定理10.1）不同特征有限域上橢圓曲線的簡(jiǎn)化方程（10.2節(jié)）→char(F)>3時(shí)的橢圓曲線簡(jiǎn)化方程√一般域上橢圓曲線群加法規(guī)則（算法10.1）→不同特征有限域上的橢圓曲線群加法→char(F)>3時(shí)的橢圓曲線群加法（算法10.2）√√→橢圓曲線密碼體制（算法10.3）√第11章線性反饋移位寄存器線性反饋移位寄存器（LFSR）→LFSR的運(yùn)行過(guò)程√LFSR的特征多項(xiàng)式（定義11.1）√→不可約多項(xiàng)式的周期與相應(yīng)LFSR序列的周期相等（定理11.1）→輸出m序列<=>LFSR的特征多項(xiàng)式是本原多項(xiàng)式（定理11.3）√√→輸出m序列<=>LFSR的特征多項(xiàng)式是本原多項(xiàng)式（定理11.3）√√GF(2)上的n次本原多項(xiàng)式（定義11.5）m序列的隨機(jī)性（滿足Golomb隨機(jī)性假設(shè)）（定理11.4）m序列的安全性（沒(méi)有隱藏線性關(guān)閉）（11.4節(jié)）非線性序列生成器*（Geffe生成器、J-K觸發(fā)器→Pless生成器）（11.6節(jié)）SNOW流密碼算法*（11.6節(jié)）第12章計(jì)算復(fù)雜度算法的時(shí)間復(fù)雜度（定義12.2）→多項(xiàng)式時(shí)間算法（定義12.5）√、指數(shù)時(shí)間算法（定義12.6）確定型圖靈機(jī)（定義12.7）→P類問(wèn)題（定義12.8）√N(yùn)P問(wèn)題（定義12.9）√→幾個(gè)NP問(wèn)題NPC問(wèn)題（定義12.10）√→幾個(gè)NPC問(wèn)題（典型的NPC問(wèn)題）→NPC問(wèn)題的限制法證明NP-hard問(wèn)題（定義12.12）√→幾個(gè)NP-hard問(wèn)題第13章圖論圖、邊、頂點(diǎn)（定義13.1）、頂點(diǎn)的度√→鄰接矩陣、關(guān)聯(lián)矩陣√√子圖生→成子圖圖同構(gòu)（定義13.1）定點(diǎn)度與邊數(shù)關(guān)系（定理13.1）→圖中奇點(diǎn)個(gè)數(shù)的奇偶性（推論13.1）路徑、跡、路的定義、連通圖（13.4節(jié)）賦權(quán)圖、權(quán)→求最短路的Dijkstra算法√（13.5節(jié)）樹(shù)（定義13.4）→樹(shù)的性質(zhì)（定理13.1、定理13.2）生成樹(shù)割邊（定義13.6）→割邊的判斷（定理13.3）、樹(shù)的判斷（定理13.4）連通度（定義13.8）→2-連通定理（定理13.6、推論13.3）二叉樹(shù)定義→二叉樹(shù)的特點(diǎn)→二叉樹(shù)每層上的節(jié)點(diǎn)數(shù)（定理13.8）、總節(jié)點(diǎn)數(shù)（定理13.9）、節(jié)點(diǎn)間的關(guān)系（定理13.10）滿二叉樹(shù)、完全二叉樹(shù)的定義→結(jié)點(diǎn)數(shù)與完全二叉樹(shù)深度的關(guān)系一次性簽名方案→Merkle樹(shù)簽名方案第14章信息論與編碼通信系統(tǒng)模型√→信源、編碼器（信源編碼器、糾錯(cuò)編碼器、調(diào)制器）、信道、譯碼器、信宿、干擾源自信息量（定義14.1）√√√→聯(lián)合自信息量（定義14.2）√√互信息量（定義14.4）√√→平均互信息（定義14