第2章信息安全数学基础(计算复杂性): ●●●● ①算法复杂性 ◎问题复杂性 2021/2/10
2021/2/10 问题复杂性 第2章 信息安全数学基础（计算复杂性） 算法复杂性
计算复杂性基础 ●●●●● ●●●● ●●0 ●●●● 古书《孟子离娄上》有这样的记载: 淳于髡曰:男女授受不亲,礼與? 孟子曰:礼也。 曰:嫂溺则授之以手乎? 曰:嫂溺不授,是豺狼也。男女授受不亲,礼 也;嫂溺授之以手,权也 虽然有“男女授受不亲”的原则存在,但嫂子落 永淹死时,必须拉她、救她,这是“板”(变通) 否则,见死不救,就是豺狼。 曰:「今天下溺矣,夫子之不援何也?」 曰:「天下溺援之以道;嫂溺援之以手。子欲手 援天下乎? 2021/2/10
2021/2/10 －古书《孟子·离娄上》有这样的记载： 淳于髡曰：男女授受不亲，礼與？ 孟子曰：礼也。 曰：嫂溺则授之以手乎？ 曰：嫂溺不授，是豺狼也。男女授受不亲，礼 也；嫂溺授之以手，权也。 －虽然有“男女授受不亲”的原则存在，但嫂子落 水快淹死时，必须拉她、救她，这是“权”(变通)， 否则，见死不救，就是豺狼。 －曰：「今天下溺矣，夫子之不援何也？」 曰：「天下溺援之以道；嫂溺援之以手。子欲手 援天下乎？」 计算复杂性基础
计算复杂性 ●●●●● ●●●● ●●0 ●●●● ●为什么要学习计算复杂性? ●计算复杂性是研究密码分析对于计算量的需求和密码分 析的困难程度,从而得出这些密码技术和算法在现有 可行的条件下是否具有足够的安全性。 ●学习计算复杂性,需要掌握两个概念: ●问题 算法 2021/2/10
2021/2/10 ⚫ 为什么要学习计算复杂性？ ⚫ 计算复杂性是研究密码分析对于计算量的需求和密码分 析的困难程度 ，从而得出这些密码技术和算法在现有 可行的条件下是否具有足够的安全性。 ⚫ 学习计算复杂性，需要掌握两个概念： ⚫ 问题 ⚫ 算法 计算复杂性
问题( problen) ●●●●● ●●●● ●●0 (问题)定义:即需要回答的一般性提问: ●它通常含有若干个参数。 ●对于一个问题进行描述应该包括两方面的内容: 必须对问题的所有给定参数给出一般性描述; 必须描述该问题的答案(或解)应该满足的性质。 ●当问题的所有参数都有了确定的取值时,我们称得到了 该问题的一个实例( instance)。 2021/2/10
2021/2/10 问题（problem） ⚫ （问题）定义：即需要回答的一般性提问: ⚫ 它通常含有若干个参数。 ⚫ 对于一个问题进行描述应该包括两方面的内容： ⚫ 必须对问题的所有给定参数给出一般性描述； ⚫ 必须描述该问题的答案（或解）应该满足的性质。 ⚫ 当问题的所有参数都有了确定的取值时，我们称得到了 该问题的一个实例（instance）
算法( algorithm) ●●●●● ●●●● ●●0 定义(算法):即求解某个问题的一系列具体步 骤(通常被理解为求解所需的通用计算程序)。 ●算法总是针对具体问题而言的,求解一个问题的算法通 常不止一个。 当某个算法能够回答一个问题的任何实例时,我们称该 算法能够回答这个问题。 ●当一个问题至少有一个能够回答该问题的算法时,我们 称该问题可解( resolvable),否则称该问题不可解 (unresolvable) 2021/2/10
2021/2/10 算法（algorithm） ⚫ 定义（算法） ：即求解某个问题的一系列具体步 骤（通常被理解为求解所需的通用计算程序）。 ⚫ 算法总是针对具体问题而言的，求解一个问题的算法通 常不止一个。 ⚫ 当某个算法能够回答一个问题的任何实例时，我们称该 算法能够回答这个问题。 ⚫ 当一个问题至少有一个能够回答该问题的算法时，我们 称该问题可解（resolvable），否则称该问题不可解 （unresolvable）
算法( algorithm)(续) ●●●●● ●●●● ●●0 ●●●● 有关算法的几点注释: ●算法总有输入和输出 算法输入大小一般用输入变量的长度(单位为位) 来表示 般来说,算法用某种编程语言来实现的计算机程序 ●一般来说,我们仅仅关注解决问题最有效的算法 当一个变量n用二进制来表示时,其长度=log2 2021/2/10
2021/2/10 算法（algorithm）（续） ⚫ 有关算法的几点注释： ⚫ 算法总有输入和输出 ⚫ 算法输入大小一般用输入变量的长度（单位为位） 来表示 ⚫ 一般来说，算法用某种编程语言来实现的计算机程序 ⚫ 一般来说，我们仅仅关注解决问题最有效的算法 n logn 当一个变量 用二进制来表示时，其长度＝ 2
问题与算法 ●●●●● ●●●● ●●0 问题:如何求解两个整数a和b的最大公约数? 参数:a和b 问题实例:a=20,b=30 ●算法:利用因子分解求a=20和b=30的最大公约 数 a=22×5 b=2×3×5 ●因此a和b的最大公约数是2×5=10 2021/2/10
2021/2/10 问题与算法 ⚫ 问题：如何求解两个整数a和b的最大公约数？ ⚫ 参数：a和b ⚫ 问题实例：a＝20，b＝30 ⚫ 算法：利用因子分解求a＝20和b＝30的最大公约 数 ⚫ a＝22×5 ⚫ b＝2×3×5 ⚫ 因此a和b 的最大公约数是2×5＝10
算法复杂性 ●●●●● ●●●● ●●0 (算法复杂度)定义:即度量该算法所需的计算 能力,包括: ●时间复杂性T( time complexity); ●空间复杂性S( space complexity); ●信道带宽; ●数据总量; ●●●。● 2021/2/10
2021/2/10 算法复杂性 ⚫ （算法复杂度）定义：即度量该算法所需的计算 能力 ，包括： ⚫ 时间复杂性T（time complexity）； ⚫ 空间复杂性S（space complexity）； ⚫ 信道带宽； ⚫ 数据总量； ⚫ ……
算法复杂性(续) ●●●●● ●●●● ●●0 计算复杂性的表示符号为“O”(称为“大O”,即算法 的阶号),表示计算复杂性的数量级 例如:一个给定算法的时间复杂性为2n2+2n+5 (1)首先,随着n的增大,2n的增长比较大,而低阶部分增长相对较小。所以, 较低阶函数部分均可忽略不计 (2)最高项n2的系数2也可忽略不计。这是因为如果T=O(n2),那么输入尺寸 增加一位,算法的运行时间变为4倍:如果T=O(2n2)那么输入尺寸增加一位算 法的运行时间也增加为四倍 (3)最后,这个给定算法的时间复杂性可以表示为O(n2)。 好处: 使算法复杂性度量与处理器的运行速度和指令运行时间无关 2212明确地揭示了输入的数据长度对算法复杂性的影响
2021/2/10 算法复杂性（续） ⚫ 计算复杂性的表示符号为“O ”（称为“大O”，即算法 的阶号），表示计算复杂性的数量级 好处： ⚫ 使算法复杂性度量与处理器的运行速度和指令运行时间无关； ⚫ 明确地揭示了输入的数据长度对算法复杂性的影响。 例如：一个给定算法的时间复杂性为 2 2 +2 +5 n n 。 （1）首先，随着 n 的增大，2 2 n 的增长比较大，而低阶部分增长相对较小。所以， 较低阶函数部分均可忽略不计。 （2）最高项 2 n 的系数 2 也可忽略不计。这是因为如果 T=O( 2 n )，那么输入尺寸 增加一位，算法的运行时间变为 4 倍；如果 T=O(2 2 n )那么输入尺寸增加一位算 法的运行时间也增加为四倍。 （3）最后，这个给定算法的时间复杂性可以表示为 O(n 2 )
算法复杂性(续) ●●●●● ●●●● ●●0 ●●●● ●算法常见复杂性分类 (1)常数算法( constant algorithm) 如果运行时间是O(1),即该算法的复杂性不依赖于n。 (2)线性算法( linear algorithm) 如果运行时间是O(mn) (3)多项式算法( polynomial algorithm): 如果运行时间是O(mm),其中m是一个常数。具有多项式复杂性的算法 族被称为多项式时间算法。 (4)超多项式算法( superpolynomialalgorithm) 如果运行时间是,其中c是一个常数,而s(m)是关于n的大于常数而小于 线性的函数。 (5)指数算法( exponentialalgorithm) 202如果运行时间是,其中t是大于1的常数,fn)是关于n的多项式函数
2021/2/10 算法复杂性（续） ⚫ 算法常见复杂性分类 ⚫ （1）常数算法（constant Algorithm）： ⚫ 如果运行时间是O(1)，即该算法的复杂性不依赖于n。 ⚫ （2）线性算法（linear Algorithm）： ⚫ 如果运行时间是O(n)。 ⚫ （3）多项式算法（polynomial Algorithm）： ⚫ 如果运行时间是O(nm)，其中m是一个常数。具有多项式复杂性的算法 族被称为多项式时间算法。 ⚫ （4）超多项式算法（superpolynomial Algorithm）： ⚫ 如果运行时间是，其中c是一个常数，而s(n)是关于n的大于常数而小于 线性的函数。 ⚫ （5）指数算法（exponential Algorithm）： ⚫ 如果运行时间是，其中t是大于1的常数，f(n)是关于n的多项式函数