《信息安全数学基础》知识点及关系 电子教案

PAGEPAGE1《信息安全数学基础》（姜正涛，电子工业出版社，2017.12）知识点及关系第1章整数的整除与唯一分解推广的欧几里德算法（定理1.5）√√推广的欧几里德算法（定理1.5）√√辗转相除法（欧几里德算法、定理1.3）√√辗转相除法（欧几里德算法、定理1.3）√√算法1.1(欧几里德算法)多个整数的公因子、最大公因子、定理1.7*定理1.2(带余除法最大公因子关系)定理1.2(带余除法最大公因子关系)→互素√→互素√公因子、最大公因子不整除整数、自然数→整除、→因子（真因子、平凡因子）、倍数→公倍数、最小公倍数→最小公倍数求法（定理1.8、定理1.9*）不整除→整数的a→整数的a进制表示带余除法（欧几里德除法）√素数素数√、合数→整数唯一分解定理（定理1.12）√素数与整数的关系（定理1.10）、素数与整数乘积的关系（定理1.11）→整数唯一分解定理（定理1.12）√素数与整数的关系（定理1.10）、素数与整数乘积的关系（定理1.11）Mersenne（素）数Mersenne（素）数*、Fermat（素）数*素数有无穷多（定理1.14）、素数定理（定理1.16）素数有无穷多（定理1.14）、素数定理（定理1.16）素数判断定理（定理1.17）孪生素数、哥德巴赫猜想孪生素数、哥德巴赫猜想*第2章同余式不同余整除、带余除法（第1章）→同余→两个整数同余的充要条件（定理2.1、推论2.1）→同余的性质（定理2.2、推论2.2√）不同余剩余类剩余类√、完全剩余类、完全剩余系、最小完全剩余系缩系完全剩余系的判断（定理2.4）与性质（定理2.5）剩余类的性质（定理2.3）缩系完全剩余系的判断（定理2.4）与性质（定理2.5）剩余类的性质（定理2.3）欧拉函数（定义2.4）√→缩系个数（定理2.6）→缩系性质（定理2.7）→欧拉定理（定理2.8）√√→费马小定理（定理2.9）√→定理2.10√→推论2.3→推论2.3√√定理2.11、定理2.12→欧拉函数计算式（定理2.13）√→→欧拉函数计算式（定理2.13）√→欧拉函数为积性函数积性函数欧拉函数的一个性质（定理2.14欧拉函数的一个性质（定理2.14*）→模逆元计算（定理2.16）√→模逆元计算（定理2.16）√→一次同余式系数与模互素时同余式解数（定理2.15）√同余式→一次同余式的解数（定理2.18）√一次同余式可解性判断（定理2.17）√→一次同余式的解数（定理2.18）√一次同余式可解性判断（定理2.17）√n次同余式的解数（定理2.20）一次同余式的求解（定理2.19）n次同余式的解数（定理2.20）一次同余式的求解（定理2.19）√→模为合数时一般同余式的解数（定理2.23→模为合数时一般同余式的解数（定理2.23*）中国剩余定理（定理2.21）√√√RSA公钥密码体制（算法2.1）RSA公钥密码体制（算法2.1）√√√第3章二次剩余同余式（第2章）→二次剩余→二次同余式的解数（定理3.1）→二次剩余的欧拉判别法（定理3.2）√→二次剩余的性质（推论3.1）→勒让德符号的性质（定理3.4）→→勒让德符号的性质（定理3.4）→勒让德符号值计算√：（定理3.3、推论3.2、推论3.3、定理3.5）、二次互反律（定理3.6）√√勒让德符号→→Goldwasser-Micali公钥加密算法（算法3.1）→雅可比符号值计算√：（定理3.8、定理3.9）、雅可比符号互反律（定理3.10）√√雅可比符号→雅可比符号的性质（定理3.7）二次同余式的求解→定理3.11(1)√(2)*、定理3.12*Rabin公钥密码体制（算法3.Rabin公钥密码体制（算法3.2）√√第4章原根与阶模整数的阶→阶的性质（定理4.1，推论4.1）→原根的定义√→模整数阶的计算（定理4.11）→模→模整数阶的计算（定理4.11）→模p原根的形式（定理4.10）模整数原根的形式（推论4.2、定理4.14）→模p原根个数（定理4.8）√模p阶为d的元素个数（定理4.7）模整数原根的判断（定理4.1模整数原根的判断（定理4.16）√Fermat素性检测的反例—卡米歇尔数（很少）第5Fermat素性检测的反例—卡米歇尔数（很少）素性检测定义→确定性算法（定理1.17、定理5.1、定理5.2、定理5.3、定理5.4）→（费马）拟素数√拟素数→→（费马）拟素数√拟素数→Fermat素性检测（算法5.1）√→Fermat素性检测的成功概率（定理5.8）→（费马）拟素数无穷多（定理5.6、定理5.7）→基于欧拉定理的素性检测成功概率（定理5.10）→欧拉拟素数也是费马拟素数（定理5.9）欧拉拟素数→基于欧拉定理的素性检测成功概率（定理5.10）→欧拉拟素数也是费马拟素数（定理5.9）欧拉拟素数√Solavay-Steassen素性检测Solavay-Steassen素性检测（算法5.2）√→Rabin-Miller素性检测（算法→Rabin-Miller素性检测（算法5.3）√→强拟素数概率（定理5.14）→强拟素数无穷多（定理5.12）素数的一个性质（定理5.11）→强拟素数√第6章群→子群的性质（定理6.3）→子群的判断（定理6.2）子群集合、二元运算、单位元、逆元→群（定义6.5）√√√→群的性质（定理6.1）→子群的性质（定理6.3）→子群的判断（定理6.2）子群→元素阶的性质（定理6.4）√群的阶、元素的阶→元素阶的性质（定理6.4）√群的阶、元素的阶√元素阶与元素最大阶的关系（定理6.5）√元素阶与元素最大阶的关系（定理6.5）√循环群（定义6.10）循环群（定义6.10）√√陪集要么相等要么无公共元（定理6.7）→陪集要么相等要么无公共元（定理6.7）→陪集的元素数相等（定理6.6）→子群的指数（定义6.12）→群是不相交的子群陪集的并（定理6.8）陪集（定义6.11）正规子群（定义6.13）拉格朗日定理（群、子群、子群指数的关系）（定理6.9正规子群（定义6.13）拉格朗日定理（群、子群、子群指数的关系）（定理6.9）正规子群的所有陪集构成一个群（定理6.12正规子群的所有陪集构成一个群（定理6.12）元素阶整除群阶（定理6.10）√√商群（定义6.14）√商群（定义6.14）√群同态、群同构（定义6.16）→群同态定理（定理6.13、定理6.14）有限阶（无限阶）循环群生成元的个数（定理6.17）√循环群（定义6.10）√√→有限阶（无限阶）循环群的性质（定理6.15、推论6.1、推论6.2）→n阶循环群当且仅当含n阶元素（定理6.有限阶（无限阶）循环群生成元的个数（定理6.17）√与有限阶（无限阶）循环群同构的群（定理6.18与有限阶（无限阶）循环群同构的群（定理6.18）循环群的子群是循环群（定理6.循环群的子群是循环群（定理6.19）√√循环群的子群个数（定理6.循环群的子群个数（定理6.20）√置换群（定义6.21）→n元集合的全体置换构成n!阶群（定理6.22）→不同置换的乘法、平方、逆运算→不同置换的乘法、平方、逆运算k-循环置换（定义6.22）第7章环子环环的定义（定义7.1）→环中元素运算（定理7.1）子环→整环（定义7.7）零因子→整环（定义7.7）零因子→无零因子环元素的特征相等（定理7.3）√→→无零因子环元素的特征相等（定理7.3）√→环的特征（定义7.1）√环中元素的（加法）阶（定义7.10）→商环（定义7.15→商环（定义7.15）多项式环NTRU密码体制(NTRU密码体制(算法7.1)无零因子环的特征要么为0要么为素数（定理7.4）√域的特征（定义8.4）√第8章域域的特征（定义8.4）√整环（定义7.7）整环（定义7.7）→分式域（定义8.3）Zp是域<=>p是素数（定理8.2）√域（定义8.1）→扩域、子域（定义8.2）Zp是域<=>p是素数（定理8.2）√素域的定义（定义8.6）→每个域只包含一个素域（定理8.素域的定义（定义8.6）→每个域只包含一个素域（定理8.4）√→与素域同构的两类域（定理8.3）整除、带余除法（第1章）多项式整除、因式、倍式、最大公因式整除、带余除法（第1章）多项式整除、因式、倍式、最大公因式多项式带余除法（定理8.6）多项式带余除法（定理8.6）、多项式的扩展欧几里德算法（定理8.8）√不可约多项式不可约多项式（定义8.10）√、多项式唯一分解定理（定理8.11）pp(x)不可约则商环F[x]/(p(x))是域（定理8.12），即扩域的构造方法√域同构（定义8.5）可通过逐步添加元素获得更大的扩域（定理8.13可通过逐步添加元素获得更大的扩域（定理8.13）→单代数扩域（定义8.→单代数扩域（定义8.13）代数元（定义8.12）→n→n次代数元（定义8.14）极小多项式（定义8.14）√→扩张次数之间的关系（定理8.19）√n次代数扩域的多项式基（定理8.1→扩张次数之间的关系（定理8.19）√n次代数扩域的多项式基（定理8.17、定义8.15）√→n次代数扩域的构造（定理8.16）√极小多项式唯一（定理8.15）扩张次数（定义8.扩张次数（定义8.17）→多项式的分裂域彼此同构（定理8.→多项式的分裂域彼此同构（定理8.23*）多项式的分裂域（定义8.19）*第9章有限域有限域（定义8.1）→有限域元素的个数（定理9.1、定理9.2）√Diffie-Hellman密钥协商(算法9.1)√√q元有限域是子域上多项式xq–x的分裂域（定理9.8）元素阶整除群阶（定理6.10-11）→有限域中非零元素的（乘法）阶（定理9.3、定理9.4）→有限域中的乘法群FDiffie-Hellman密钥协商(算法9.1)√√q元有限域是子域上多项式xq–x的分裂域（定理9.8）q元有限域存在唯一性定理（定理9.9）q元有限域存在唯一性定理（定理9.9）√对于任何有限域存在任意次不可约多项式（定理9.11）→在有限域上可以构造任意次扩域（有限域扩域的构造）√√√→AES中的有限域运算（9.6节）√有限域上多项式的阶（定义9.7）→有限域上不可约多项式的阶等于其任一根的阶（定理9.19）→本原多项式（定义9.8）→本原多项式的阶（定理9.20）√第10章有限域上的椭圆曲线椭圆曲线（定义10.1）→非奇异椭圆曲线（定理10.1）不同特征有限域上椭圆曲线的简化方程（10.2节）→char(F)>3时的椭圆曲线简化方程√一般域上椭圆曲线群加法规则（算法10.1）→不同特征有限域上的椭圆曲线群加法→char(F)>3时的椭圆曲线群加法（算法10.2）√√→椭圆曲线密码体制（算法10.3）√第11章线性反馈移位寄存器线性反馈移位寄存器（LFSR）→LFSR的运行过程√LFSR的特征多项式（定义11.1）√→不可约多项式的周期与相应LFSR序列的周期相等（定理11.1）→输出m序列<=>LFSR的特征多项式是本原多项式（定理11.3）√√→输出m序列<=>LFSR的特征多项式是本原多项式（定理11.3）√√GF(2)上的n次本原多项式（定义11.5）m序列的随机性（满足Golomb随机性假设）（定理11.4）m序列的安全性（没有隐藏线性关闭）（11.4节）非线性序列生成器*（Geffe生成器、J-K触发器→Pless生成器）（11.6节）SNOW流密码算法*（11.6节）第12章计算复杂度算法的时间复杂度（定义12.2）→多项式时间算法（定义12.5）√、指数时间算法（定义12.6）确定型图灵机（定义12.7）→P类问题（定义12.8）√NP问题（定义12.9）√→几个NP问题NPC问题（定义12.10）√→几个NPC问题（典型的NPC问题）→NPC问题的限制法证明NP-hard问题（定义12.12）√→几个NP-hard问题第13章图论图、边、顶点（定义13.1）、顶点的度√→邻接矩阵、关联矩阵√√子图生→成子图图同构（定义13.1）定点度与边数关系（定理13.1）→图中奇点个数的奇偶性（推论13.1）路径、迹、路的定义、连通图（13.4节）赋权图、权→求最短路的Dijkstra算法√（13.5节）树（定义13.4）→树的性质（定理13.1、定理13.2）生成树割边（定义13.6）→割边的判断（定理13.3）、树的判断（定理13.4）连通度（定义13.8）→2-连通定理（定理13.6、推论13.3）二叉树定义→二叉树的特点→二叉树每层上的节点数（定理13.8）、总节点数（定理13.9）、节点间的关系（定理13.10）满二叉树、完全二叉树的定义→结点数与完全二叉树深度的关系一次性签名方案→Merkle树签名方案第14章信息论与编码通信系统模型√→信源、编码器（信源编码器、纠错编码器、调制器）、信道、译码器、信宿、干扰源自信息量（定义14.1）√√√→联合自信息量（定义14.2）√√互信息量（定义14.4）√√→平均互信息（定义14