第4章 密码学的计算复杂性理论基础.

Presentation on theme: "第4章 密码学的计算复杂性理论基础."— Presentation transcript:

1 第4章 密码学的计算复杂性理论基础

2 4.1 问题与算法的复杂性 4.1.1 问题与语言 实际应用中的绝大多数问题都可直接或间接地转化为判定问题。
问题与语言 例4.1 . 整数的因子分解问题。 例4.2 . 背包问题。 实际应用中的绝大多数问题都可直接或间接地转化为判定问题。

3 定义4.1 的任一子集L称为一个B－语言（或简称语言）。语言L中的字称为语言L的成员。
定义4.2 设一个语言 已给定。语言L成员的识别问题可描述为：任给 （参数），问是否x是L语言的成员（是否 ）？ 定义4.3 设 为一个问题，B为一个字符集。从I到 中的一个映射c，满足条件 （空集），称为问题D的一个B－编码。若c为D的一个编码，集 称为D的一个c－语言。

4 引理4.1 若c为D的一个编码，则求解问题D和求解语言 的成员识别问题是等价的，即问题D的任一例子 ，其答案与语言 的成员识别问题的例子的答案 是相同的。
一个合理编码还应满足下列两个基本要求： 1） 编码是容易实现的； 2） 求解问题的任一例子的计算复杂性（通常用计算时间来表示）与的长有某种正比关系。

5 4.1.2 算法与图灵机 有限状态控制器 读写头 图4.1 确定性单带图灵机示意图 …. -5 -4 -3 -2 -1 1 2 3 4 5
1 2 3 4 5 6 7 8 …无限长磁带

6 定义 4.4 一个确定性单带图灵机由下列集和函数构成。
1. 1）带中所用字符集B，通常可设 ，其中 表示空。 2）读写头所处的可能状态集S，其中包含一个初始状态 和若干个停机状态 。 3）读写头所处状态的转移函数 ，它是读写头现在所处状态s和所读字符b的函数，表示为 。 4）读写头动作的指令函数 ，它也是读写头现在所处状态s和所读字符b的函数，表示为 ，其中 且都不属于B。若 ，则读写头写字符 代替b，且保持原位不动。若 ，则原字符b保持不变，读写头向左（或向右）移动一个小方格。 2. 磁带上的每个小方格用一个整数坐标i表示。小方格i中的字符记作t(i)，磁带表示为函数 。

7 3. 图灵机在某一时刻的形是指一个三元组 ，它们分别表示该时刻读写头所处状态，磁带和读写头所扫描的小方格坐标，t(i)为读写头在该时刻所读字符。
一个图灵机的计算程序（算法）是一个形的有限或无限序列 ，其中 为图灵机在初始时刻的形，即 为初始状态，为初始磁带，它由输入数据（字） 给出，通常存放在 小方格中，其它小方格中为空字符 ，通常 。图灵机在k时刻的形 由下面的递推式给出。 若存在形 使 ，则计算在时刻 终止，同时停机，称 或 为计算的输出结果，K称为图灵机（算法）的运行（计算）时间。否则计算将不终止，不停机，直到无限。

8 定义 4.5 称一个图灵机 M可解一个语言L 的成员识别问题,若对任一输入数据 ，M在有限时刻 停机，且M的输出 ，若 。否则 。图灵机的计算复杂性定义为
定义 4.6 设f(n)和g(n)为两个正整数函数，若存在正整数 和常数c使当 时有 ，则记作 ；若 ， ，则记作

9 定义4. 7 设 和 为图灵机M和 的计算复杂性，若 ，则称算法 不比算法M有效；若 ，则称算法M和 是等效的；若存在正整数d，
定义4.7 设 和 为图灵机M和 的计算复杂性，若 ，则称算法 不比算法M有效；若 ，则称算法M和 是等效的；若存在正整数d， ，则称M为多项式时间算法，按密码学中的传统观念，认为多项式时间算法为有效算法；若 ，则称M为亚指数时间算法；若 ，则称M为指数时间算法。亚指数和指数时间算法也被称为超多项式时间算法，被认为不是有效算法。

10 4．2 问题的计算复杂性分类 4.2.1 P，NP，NP完全类问题
定义4.8 一个语言L的成员识别问题属于P类，若存在一个可解该问题的图灵机M和一个正多项式 ，使M的计算复杂性 ，所有P类问题构成的集记作P。 定义4.9 一个语言L的成员识别问题属于NP类，若存在一个 的子集 （称为一个布尔关系）及一个正多项式p(n)满足下列两个条件： 1） 的成员识别问题属于P类； 2） 当且仅当存在一个y，其长 ，且 。这样的y称为是 的证据。所有NP类问题构成的集记作NP。

11 定义4.9 一个语言的成员识别问题属于NP类，若存在一个的子集（称为一个布尔关系）及一个正多项式(n)满足下列两个条件：
2）当且仅当存在一个，其长，且。这样的称为是的证据。所有NP类问题构成的集记作NP。

12 定义 4.10 称一个图灵机M可计算一个函数 ，若对任一输入数据 ，M在有限时刻 停机，且M的输出磁带 上的二进数序列（不包含空 ） 。若M是多项式时间算法，则称f(x)是多项式时间可计算的。
定义4.11 一个语言L称为可多项式时间化为另一语言 ，若存在一个多项式时间可计算函数f(x)，使 当且仅当 ，这时也称语言L的成员识别问题可多项式时间化为语言 的成员识别问题。 定义 4.12 一个语言L的成员识别问题属于NP完全(NPC)类，若它属于NP类，且每个NP类语言成员识别问题都可多项式时间化为语言L的成员识别问题。所有NP完全类问题构成的集记作NPC。

13 概率算法与BPP类问题 概率算法就是在执行计算的过程中允许用随机数。 定义 4.13 一个概率算法（图灵机）称为多项式时间概率算法。若存在一个多项式p(n)，对任一 ，有 。换句话说，对所有扔硬币结果r（可设 ）都有 。

14 定义 4.14 称一个多项式时间概率算法M可解一个语言L的成员识别问题，若对任一输入数据 ，有
（1）若 ，则 （2）若 ，则 称一个语言L的成员识别问题属于BPP类，若存在一个可解该问题的多项式时间概率算法。所有BPP类问题构成的集记作BPP。

15 小结 计算复杂性理论是现代密码学的理论基础。
关于算法的时间复杂性有两种定义方法：一是用一个图灵机表示一个算法，该算法的时间复杂性定义为该图灵机运行的步数；二是定义一个算法的时间复杂性为该算法的比特运算次数。本章使用前者。 关于判定问题到语言成员识别问题的合理编码，关于估计算法的比特运算次数的方法，关于NP完全问题。