数学理论复杂性省公开课一等奖全国示范课微课金奖课件

北京师范大学数学学院杨进goodskyfly@163.com网络与信息安全

2025/2/21第1页问题复杂性第2章信息安全数学基础（计算复杂性）算法复杂性2025/2/21第2页问题复杂性第2章信息安全数学基础（计算复杂性）算法复杂性2025/2/21第3页为何要学习计算复杂性？计算复杂性是研究密码分析对于计算量需求和密码分析困难程度，从而得出这些密码技术和算法在现有可行条件下是否含有足够安全性。学习计算复杂性，需要掌握两个概念：问题算法计算复杂性2025/2/21第4页问题（problem）

（问题）定义：即需要回答普通性提问:它通常含有若干个参数。对于一个问题进行描述应该包含两方面内容：必须对问题全部给定参数给出普通性描述；必须描述该问题答案（或解）应该满足性质。当问题全部参数都有了确定取值时，我们称得到了该问题一个实例（instance）。2025/2/21第5页算法（algorithm）

定义（算法）：即求解某个问题一系列详细步骤（通常被了解为求解所需通用计算程序）。算法总是针对详细问题而言，求解一个问题算法通常不止一个。当某个算法能够回答一个问题任何实例时，我们称该算法能够回答这个问题。当一个问题最少有一个能够回答该问题算法时，我们称该问题可解（resolvable），不然称该问题不可解（unresolvable）。2025/2/21第6页算法（algorithm）（续）

相关算法几点注释：算法总有输入和输出算法输入大小普通用输入变量长度（单位为位）来表示普通来说，算法用某种编程语言来实现计算机程序普通来说，我们仅仅关注处理问题最有效算法2025/2/21第7页问题与算法问题：怎样求解两个整数a和b最大条约数？参数：a和b问题实例：a＝20，b＝30算法：利用因子分解求a＝20和b＝30最大条约数a＝2×2×5b＝2×3×5所以a和b最大条约数是2×5＝102025/2/21第8页算法复杂性

（算法复杂度）定义：即度量该算法所需计算能力，包含：时间复杂性T（timecomplexity）；空间复杂性S（spacecomplexity）；信道带宽；数据总量；……2025/2/21第9页算法复杂性（续）计算复杂性表示符号为“O”（称为“大O”，即算法阶号），表示计算复杂性数量级

好处：使算法复杂性度量与处理器运行速度和指令运行时间无关；明确地揭示了输入数据长度对算法复杂性影响。

2025/2/21第10页算法复杂性（续）算法常见复杂性分类（1）常数算法（constantAlgorithm）：假如运行时间是O(1)，即该算法复杂性不依赖于n。（2）线性算法（linearAlgorithm）：假如运行时间是O(n)。（3）多项式算法（polynomialAlgorithm）：假如运行时间是O(nm)，其中m是一个常数。含有多项式复杂性算法族被称为多项式时间算法。（4）超多项式算法（superpolynomialAlgorithm）：假如运行时间是，其中c是一个常数，而s(n)是关于n大于常数而小于线性函数。（5）指数算法（exponentialAlgorithm）：假如运行时间是，其中t是大于1常数，f(n)是关于n多项式函数。2025/2/21第11页算法复杂性（续）算法常见复杂性分类普通而言，常数算法、线性算法、多项式算法和超多项式算法统称为多项式算法。所谓多项式，就是含有以下形式一个函数：其中，k和ck是常数，且ci称≠0为。当k>0时，k称为多项式次数，ci称为多项式系数。

2025/2/21第12页算法复杂性算法分类及其运行时间

算法类型复杂性运算次数n＝106时间多项式算法常数算法O(1)11微秒线性算法O(n)1061秒二次多项式算法O(n2)101211.6天三次多项式算法O(n3)101832,0指数算法O(2n)10301030103010算法复杂性（续）2025/2/21第13页算法复杂性算法复杂度增加速度算法复杂性（续）亚指数指数多项式2025/2/21第14页算法复杂性（续）研究问题内在复杂性，即在图灵机上处理最难问题实例所需最小时间和空间条件。图灵机是一个含有没有限读、写存放带有限状态机，能够被看成一个实际可用计算模型。2025/2/21第15页问题复杂性第2章信息安全数学基础（计算复杂性）算法复杂性2025/2/21第16页问题复杂性

图灵机分为两类：确定性图灵机。非确定性图灵机2025/2/21第17页问题复杂性（续）确定性图灵机。确定性图灵机输出结果只取决于输入和初始状态。所以，对于含有相同输入和初始状态，运行一个确定性图灵机所得到结果是完全相同。非确定性图灵机：能够进行猜测。求解一个问题分两个阶段：猜测阶段和验证阶段。2025/2/21第18页图灵机图灵机包含一个有限状态控制单元、k（≥1）条纸带（Tape）和k个读写头（Tapehead）。有限状态控制单元控制每个读写头访问一条纸带，并沿着纸带左右移动图灵机求解问题输入是一个有限长度字符串，该输入占据每条纸带无限个单元最左边有限个单元。读写头对纸带一次访问称之为一个正当移动（Move）。2025/2/21第19页图灵机（续）图灵机求解问题时，被赋予一个初始状态（InitialState），且一步一步地移动，从而完成对输入扫描。假如图灵机最终扫描了整个输入串，且满足了中止条件而停顿下来，则称图灵机识别了该输入。不然，图灵机在某一点没有正当移动，所以会没有识别输入串而停顿下来，此时称图灵机无法识别该输入。图灵机所识别一个输入，称为一个可识别语言一个实例。2025/2/21第20页图灵机（续）比如：请设计一个图灵机，用于证实某个非负整数是否能被3整除。2025/2/21第21页图灵机（续）比如：请设计一个图灵机，用于证实某个非负整数是否能被3整除。2025/2/21第22页图灵机（续）比如：请设计一个图灵机，用于证实某个非负整数是否能被3整除。2025/2/21第23页图灵机（续）比如：请设计一个图灵机，用于证实某个非负整数是否能被3整除。2025/2/21第24页图灵机（续）比如：请设计一个图灵机，用于证实某个非负整数是否能被3整除。2025/2/21第25页图灵机（续）比如：请设计一个图灵机，用于证实某个非负整数是否能被3整除。2025/2/21第26页图灵机（续）比如：请设计一个图灵机，用于证实某个非负整数是否能被3整除。2025/2/21第27页图灵机（续）比如：请设计一个图灵机，用于证实某个非负整数是否能被3整除。2025/2/21第28页图灵机（续）比如：请设计一个图灵机，用于证实某个非负整数是否能被3整除。2025/2/21第29页图灵机（续）比如：请用DIV3图灵机证实a＝12(二进制1100)能被3整除。2025/2/21第30页图灵机（续）比如：请用DIV3图灵机证实a＝12(二进制1011)能被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第31页图灵机（续）比如：请用DIV3图灵机证实a＝12(二进制1011)能被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第32页图灵机（续）比如：请用DIV3图灵机证实a＝12(二进制1011)能被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第33页图灵机（续）比如：请用DIV3图灵机证实a＝12(二进制1011)能被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第34页图灵机（续）比如：请用DIV3图灵机证实a＝12(二进制1011)能被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第35页图灵机（续）比如：请用DIV3图灵机证实a＝12(二进制1011)能被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第36页图灵机（续）比如：请用DIV3图灵机证实a＝13(二进制1101)不能被3整除。2025/2/21第37页图灵机（续）比如：请用DIV3图灵机证实a＝13(二进制1101)被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第38页图灵机（续）比如：请用DIV3图灵机证实a＝13(二进制1101)被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第39页图灵机（续）比如：请用DIV3图灵机证实a＝13(二进制1101)被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第40页图灵机（续）比如：请用DIV3图灵机证实a＝13(二进制1101)被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第41页图灵机（续）比如：请用DIV3图灵机证实a＝13(二进制1101)被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第42页图灵机（续）比如：请用DIV3图灵机证实a＝13(二进制1101)被3整除。当前状态纸带上符号下一步移动下一个状态q0（初态）01空右右响铃或终止q0q1q101空右右输出非整除信息q2q0q201空右右输出非整除信息q1q22025/2/21第43页问题复杂性

借助于图灵机理论，问题复杂型实际上就是在图灵机上处理最难问题实例所需要最小时间最小空间2025/2/21第44页图灵机（续）图灵机M识别一个长度为n输入串而移动步数称为图灵机时间复杂性，记为：当图灵机M识别一个长度为n输入串，其写操作中读写头所访问纸带单元数称为图灵机空间复杂性，记为：2025/2/21第45页图灵机（续）2025/2/21第46页问题分类假如一个问题在确定性图灵机上能够在多项式时间内得处处理，则称该问题时易处理（tractable）。也既是说，能够用多项式时间处理问题称之为易处理。不能够在多项式时间内处理问题是难处理。因为伴随输入尺寸增加，求解这类问题需要时间快速变得很长，以至于不可能有效求解。难处理问题也被称为是难解。2025/2/21第47页P类问题易处理问题全体称为“多项式时间可解类”，记为P类。复杂度类P包含全部能用多项式时间处理问题。上述定义表明，假如L是多项式时间内可识别语言，则确定性图灵机能够在多项式时间内，判定一个字符串是否属于语言L。2025/2/21第48页NP类问题有这么一类问题，即使不能够用确定性图灵机来有效求解，不过却能够用非确定性图灵机在多项式时间内得处处理这类问题称为“非确定性多项式时间可解问题”，简称NP问题。定义（NP类）NP类表示用非确定性图灵机在多项式时间内能够识别语言类。2025/2/21第49页NP类问题（续）意义：能够经过非确定性多项式时间算法对许多对称密钥算法和全部公钥算法进行攻击。NP完全问题：指NP中任何一个问题都能够经过多项式时间转化为该问题。NP完全问题全体被记为NPC。NP完全问题是NP问题中最难问题。

定义2.3.3（NP完全类）假如任意:

是非确定性多项式时间完全（NP完全）都能够多项式规约到语言，则称:2025/2/21第50页NP类问题（续）NP中任何一个问题都能够经过多项式时间转化为该问题。NP完全问题全体被记为NPC。NP完全问题是NP问题中最难问题。2025/2/21第51页算法复杂性算法时间复杂度度量方法图灵机处理问题所移动步数（该时间称之为算法运行时间）该度量方法缺点：没有考虑每一步详细操作比如：加法和乘法计算开销是不一样为此，引入算法“按位”计算复杂度度量方法：考虑操作假如按位进行所需要执行“步数”2025/2/21第52页算法复杂性（续）2025/2/21第53页算法复杂性（续）2025/2/21第54页算法复杂性（续）2025/2/21第55页算法复杂性-普通代数运算2025/2/21第56页算法复杂性-模运算2025/2/21第57页算法复杂性-有限域2025/2/21第58页算法复杂性（续）2025/2/21第59页算法复杂性（续）2025/2/21第60页算法复杂性（续）2025/2/21第61页算法复杂性（续）2025/2/21第62页算法复杂性（续）2025/2/21第63页算法复杂性（续）2025/2/21第64页算法复杂性（续）2025/2/21第65页算法复杂性（续）2025/2/21第66页算法复杂性（续）假如将模运算视为基本运算单位（即一次模运算花费一个时间单位），则算法时间复杂度为2max(|a|,|b|)。

2025/2/21第67页算法复杂性（续）2025/2/21第68页算法复杂性（续）2025/2/21第69页计算复杂性在信息安全中应用

在信息安全中，极难界定一个密码体制是否是安全。在经典密码学中，安全性判定是基于信息论。信息论关注是密文当中到底包含多少关于明文信息。密文中关于明文信息量越大，密码体制就越不安全。而只有当密文中不包含关于明文信息时，密码体制才是绝对安全。香农证实过这种完美安全性只有当密钥跟明文长度相等时，才能到达。这种安全性限制下密码体制，其应用是非常困难。2025/2/21第70页计算复杂性在信息安全中应用（续）

在当代密码学当中，对安全性判定是基于计算复杂性。密文中是否包含明文信息，这个问题对安全性来说并不主要。关键是有没有有效方法将密文中关于明文信息提取出来。换句话说，基于计算复杂性密码学所关心不是密码分析者是否有可能破译算法（实际上，除了一次一密外，全部密码体制都是有可能被破译），而是关心密码分析者是否含有对应资源和时间来破译算法。2025/2/21第71页计算复杂性在信息安全中应用（续）比如:假如一个密码算法破译只是一个P类问题，这个算法当然会被认为是不安全。一个需要宇宙年纪那么长时间才能破译算法，当然有理由认为是安全。2025/2/21第72页计算复杂性在信息安全中应用（续）基于复杂性理论当代密码学将NP≠P作为一个必要条件，加密算法中，拥有正确加密/解密密钥用户进行加密/解密是易处理问题，而对于密码攻击者或分析者，从密文中提取明文或不用正确密钥结构正当密文应该是一个难解问题。而很多加密算法是基于NP完全问题，即这类型算法中，分析和破译是一个NP完全问题。我们称之为NP≠P猜测。2025/2/21第73页计算复杂性在信息安全中应用（续）假如NP＝P，则分析和破译加密算法是一个多项式时间问题，即易处理问题。那么这些加密算法将失去其安全性。所以，假如这个猜测不正确，现在密码学将失去其一个至关主要理论基础。2025/2/21第74页计算复杂性在信息安全中应用（续）另首先，即使NP≠P猜测成立，基于NP完全问题难解性密码算法也不一定是安全。比如：基于NP完全著名背包问题破解就是一个反例。这是因为即使一个问题只有能够忽略少数