第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）