第4章-密码学的计算复杂性理论基础ppt课件

1、第4章 密码学的计算复杂性理论基础,4.1 问题与算法的复杂性,4.1.1 问题与语言 例4.1 . 整数的因子分解问题。 例4.2 . 背包问题。 实际应用中的绝大多数问题都可直接或间接地转化为判定问题,定义4.1 的任一子集L称为一个B语言（或简称语言）。语言L中的字称为语言L的成员。 定义4.2 设一个语言 已给定。语言L成员的识别问题可描述为：任给 （参数），问是否x是L语言的成员（是否 ）？ 定义4.3 设 为一个问题，B为一个字符集。从I到 中的一个映射c，满足条件 （空集），称为问题D的一个B编码。若c为D的一个编码，集 称为D的一个c语言,引理4.1 若c为D的一个编码，则求解

2、问题D和求解语言 的成员识别问题是等价的，即问题D的任一例子 ，其答案与语言 的成员识别问题的例子的答案 是相同的。 一个合理编码还应满足下列两个基本要求： 1） 编码是容易实现的； 2） 求解问题的任一例子的计算复杂性（通常用计算时间来表示）与的长有某种正比关系,4.1.2 算法与图灵机,定义 4.4 一个确定性单带图灵机由下列集和函数构成。 1.1）带中所用字符集B，通常可设 ，其中 表示空。 2）读写头所处的可能状态集S，其中包含一个初始状态 和若干个停机状态 。 3）读写头所处状态的转移函数 ，它是读写头现在所处状态s和所读字符b的函数，表示为 。 4）读写头动作的指令函数 ，它也是读

3、写头现在所处状态s和所读字符b的函数，表示为 ，其中 且都不属于B。若 ，则读写头写字符 代替b，且保持原位不动。若 ，则原字符b保持不变，读写头向左（或向右）移动一个小方格。 2.磁带上的每个小方格用一个整数坐标i表示。小方格i中的字符记作t(i)，磁带表示为函数,3.图灵机在某一时刻的形是指一个三元组 ，它们分别表示该时刻读写头所处状态，磁带和读写头所扫描的小方格坐标，t(i)为读写头在该时刻所读字符。 一个图灵机的计算程序（算法）是一个形的有限或无限序列 ，其中 为图灵机在初始时刻的形，即 为初始状态，为初始磁带，它由输入数据（字） 给出，通常存放在 小方格中，其它小方格中为空字符 ，通

4、常 。图灵机在k时刻的形 由下面的递推式给出。 若存在形 使 ，则计算在时刻 终止，同时停机，称 或 为计算的输出结果，K称为图灵机（算法）的运行（计算）时间。否则计算将不终止，不停机，直到无限,定义 4.5 称一个图灵机M可解一个语言L的成员识别问题,若对任一输入数据 ，M在有限时刻 停机，且M的输出 ，若 。否则 。图灵机的计算复杂性定义为 定义 4.6 设f(n)和g(n)为两个正整数函数，若存在正整数 和常数c使当 时有 ，则记作 ；若 ， ，则记作,定义4.7 设 和 为图灵机M和 的计算复杂性，若 ，则称算法 不比算法M有效；若 ，则称算法M和 是等效的；若存在正整数d， ，则称M

5、为多项式时间算法，按密码学中的传统观念，认为多项式时间算法为有效算法；若 ，则称M为亚指数时间算法；若 ，则称M为指数时间算法。亚指数和指数时间算法也被称为超多项式时间算法，被认为不是有效算法,42 问题的计算复杂性分类,4.2.1 P，NP，NP完全类问题 定义4.8 一个语言L的成员识别问题属于P类，若存在一个可解该问题的图灵机M和一个正多项式 ，使M的计算复杂性 ，所有P类问题构成的集记作P。 定义4.9 一个语言L的成员识别问题属于NP类，若存在一个 的子集 （称为一个布尔关系）及一个正多项式p(n)满足下列两个条件： 1） 的成员识别问题属于P类； 2） 当且仅当存在一个y，其长 ，

6、且 。这样的y称为是 的证据。所有NP类问题构成的集记作NP,定义4.9 一个语言的成员识别问题属于NP类，若存在一个的子集（称为一个布尔关系）及一个正多项式(n)满足下列两个条件： 1）的成员识别问题属于P类； 2）当且仅当存在一个，其长，且。这样的称为是的证据。所有NP类问题构成的集记作NP,定义 4.10 称一个图灵机M可计算一个函数 ，若对任一输入数据 ，M在有限时刻 停机，且M的输出磁带 上的二进数序列（不包含空 ） 。若M是多项式时间算法，则称f(x)是多项式时间可计算的。 定义4.11 一个语言L称为可多项式时间化为另一语言 ，若存在一个多项式时间可计算函数f(x)，使 当且仅当

7、 ，这时也称语言L的成员识别问题可多项式时间化为语言 的成员识别问题。 定义 4.12 一个语言L的成员识别问题属于NP完全(NPC)类，若它属于NP类，且每个NP类语言成员识别问题都可多项式时间化为语言L的成员识别问题。所有NP完全类问题构成的集记作NPC,4.2.2 概率算法与BPP类问题,概率算法就是在执行计算的过程中允许用随机数。 定义 4.13 一个概率算法（图灵机）称为多项式时间概率算法。若存在一个多项式p(n)，对任一 ，有 。换句话说，对所有扔硬币结果r（可设 ）都有,定义 4.14 称一个多项式时间概率算法M可解一个语言L的成员识别问题，若对任一输入数据 ，有 （1）若 ，则 （2）若 ，则 称一个语言L的成员识别问题属于BPP类，若存在一个可解该问题的多项式时间概率算法。所有BPP类问题构成的集记作BPP,小结,计算复杂性理论是现代密码学的理论基础。 关于算法的时间复杂性有两种定义方法：一