1、第 3章密码学的复杂性理论基础 1密码技术和算法复杂性 计算复杂性 ：研究密码分析对于计算量的需求和密码分析的困难程度 ，从而得出这些密码技术和算法在现有可行的条件下是否具有足够的安全性： 算法复杂性； 问题复杂性。 密码协议、方案和体制的安全性证明：零知识证明理论。2问题（ problem） 即需要回答的一般性提问 : 它通常含有若干个参数。 对于一个问题进行描述应该包括两方面的内容：必须对问题的所有给定参数给出一般性描述；必须描述该问题的答案（或解）应该满足的性质。 当问题的所有参数都有了确定的取值时，我们称得到了该问题的一个实例（ instance）。 3算法（ algorithm） 即
2、求解某个问题的一系列具体步骤（通常被理解为求解所需的通用计算程序）。 算法总是针对具体问题而言的，求解一个问题的算法通常不止一个。 当某个算法能够回答一个问题的任何实例时，我们称该算法能够回答这个问题。 当一个问题至少有一个能够回答该问题的算法时，我们称该问题可解（ resolvable），否则称该问题不可解（ unresolvable）。 4算 法 复 杂 性 即度量该算法所需的计算能力 ，包括： 时间复杂性 T（ time complexity）； 空间复杂性 S（ space complexity）； 随机位数目； 信道带宽； 数据总量； 5算 法 复 杂 性 计算复杂性的表示符号为 “
3、 O ”（称为 “大 O ”），表示计算复杂性的数量级 好处： 使算法复杂性度量与处理器的运行速度和指令运行时间无关； 明确地揭示了输入的数据长度对算法复杂性的影响。 6算 法 复 杂 性 算法的分类及其运行时间 运算次数宇宙年 龄 的类别 复 杂 性 时间多项式常数 1 1微妙线 性 1秒二次 11.6天三次 32,000年指数7问 题 复 杂 性 研究问题的内在复杂性，即在图灵机上解决最难的问题实例所需的最小时间和空间条件。 8图灵机 图灵机是一种具有无限读 写存储带的有限状态机，可以被当作一个实际可用的计算模型 。 确定性图灵机。 非确定性图灵机 ：能够进行猜测。求解一个问题分两个阶段：猜测阶段和验证阶段。 9问题分类 易处理的（ tractable） ：确定性图灵机上能够在多项式时间内得到处理的问题。称易处理问题的全体为 “多项式时间可解类 ”，记为 P。 非确定性图灵机上能够在多项式时间内得到处理的问题被称为 “非确定性多项式时间可解问题 ”，简称 NP问题。 NP问题的全体被称为 “非确定性多项式时间可解类”，记为 NP。10
