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

第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－语言。*B*BL*BxLx),(IID*B)()(IcIc)();(),(IcIccDL•引理4.1若c为D的一个编码，则求解问题D和求解语言的成员识别问题是等价的，即问题D的任一例子，其答案与语言的成员识别问题的例子的答案是相同的。•一个合理编码还应满足下列两个基本要求：1）编码是容易实现的；2）求解问题的任一例子的计算复杂性（通常用计算时间来表示）与的长有某种正比关系。),(cDLI),(cDL)(c4.1.2算法与图灵机….-5-4-3-2-1012345678…无限长磁带有限状态控制器读写头图4.1确定性单带图灵机示意图•定义4.4一个确定性单带图灵机由下列集和函数构成。1.1）带中所用字符集B，通常可设，其中表示空。2）读写头所处的可能状态集S，其中包含一个初始状态和若干个停机状态。3）读写头所处状态的转移函数，它是读写头现在所处状态s和所读字符b的函数，表示为。4）读写头动作的指令函数，它也是读写头现在所处状态s和所读字符b的函数，表示为，其中且都不属于B。若，则读写头写字符代替b，且保持原位不动。若，则原字符b保持不变，读写头向左（或向右）移动一个小方格。2.磁带上的每个小方格用一个整数坐标i表示。小方格i中的字符记作t(i)，磁带表示为函数。,1,0B0sSTSBS:rlBBS,:rlBbbs'),('b)(),(rlbs或BZt整数集）(:3.图灵机在某一时刻的形是指一个三元组，它们分别表示该时刻读写头所处状态，磁带和读写头所扫描的小方格坐标，t(i)为读写头在该时刻所读字符。4.一个图灵机的计算程序（算法）是一个形的有限或无限序列，其中为图灵机在初始时刻的形，即为初始状态，为初始磁带，它由输入数据（字）给出，通常存放在小方格中，其它小方格中为空字符，通常。图灵机在k时刻的形由下面的递推式给出。若存在形使，则计算在时刻终止，同时停机，称或为计算的输出结果，K称为图灵机（算法）的运行（计算）时间。否则计算将不终止，不停机，直到无限。),,(its),,,(),,,(),,,(222111000itsitsits),,(000its0s0t*Bxx110i,2,1),,,(kitskkk))(,(111kkkkitss1,))(,(1,))(,()3.4()()())(,(11111111111111111kkkkkkkkkkkkkkkkkkkkkkkiittritsiittlitsiiitiibitiiBbits则若则若则若),,(kkkitsTsk);min(TskKk),(kkit)(kkit•定义4.5称一个图灵机M可解一个语言L的成员识别问题,若对任一输入数据，M在有限时刻停机，且M的输出，若。否则。图灵机的计算复杂性定义为•定义4.6设f(n)和g(n)为两个正整数函数，若存在正整数和常数c使当时有，则记作；若，，则记作*1,0x)(xK1)()()(xKxKitLx0)()()(xKxKit)(max)(;xKnfnxxM0n0nn)()(ncgnf))(()(ngnf))(()(ngnf))(()(nfng))()(ngnfΘ（•定义4.7设和为图灵机M和的计算复杂性，若，则称算法不比算法M有效；若，则称算法M和是等效的；若存在正整数d，，则称M为多项式时间算法，按密码学中的传统观念，认为多项式时间算法为有效算法；若，则称M为亚指数时间算法；若，则称M为指数时间算法。亚指数和指数时间算法也被称为超多项式时间算法，被认为不是有效算法。)(nfM)('nfM'M))(()('nfnfMM'M))(()('nfnfMM'M)()(dMnnf)2()(lognMnf)10)2()(nnMnf（或4．2问题的计算复杂性分类•4.2.1P，NP，NP完全类问题•定义4.8一个语言L的成员识别问题属于P类，若存在一个可解该问题的图灵机M和一个正多项式，使M的计算复杂性，所有P类问题构成的集记作P。•定义4.9一个语言L的成员识别问题属于NP类，若存在一个的子集（称为一个布尔关系）及一个正多项式p(n)满足下列两个条件：1）的成员识别问题属于P类；2）当且仅当存在一个y，其长，且。这样的y称为是的证据。所有NP类问题构成的集记作NP。)(np))(()(npnfM**1,01,0),(yxRLLRLx)(xpyLRyx),(Lx•定义4.9一个语言的成员识别问题属于NP类，若存在一个的子集（称为一个布尔关系）及一个正多项式(n)满足下列两个条件：1）的成员识别问题属于P类；2）当且仅当存在一个，其长，且。这样的称为是的证据。所有NP类问题构成的集记作NP。•定义4.10称一个图灵机M可计算一个函数，若对任一输入数据，M在有限时刻停机，且M的输出磁带上的二进数序列（不包含空）。若M是多项式时间算法，则称f(x)是多项式时间可计算的。•定义4.11一个语言L称为可多项式时间化为另一语言，若存在一个多项式时间可计算函数f(x)，使当且仅当，这时也称语言L的成员识别问题可多项式时间化为语言的成员识别问题。•定义4.12一个语言L的成员识别问题属于NP完全(NPC)类，若它属于NP类，且每个NP类语言成员识别问题都可多项式时间化为语言L的成员识别问题。所有NP完全类问题构成的集记作NPC。**1,01,0:)(xf*1,0x)(xK)(xKt)()(xfxM'LLx')(Lxf'L4.2.2概率算法与BPP类问题•概率算法就是在执行计算的过程中允许用随机数。•定义4.13一个概率算法（图灵机）称为多项式时间概率算法。若存在一个多项式p(n)，对任一，有。换句话说，对所有扔硬币结果r（可设）都有。*1,0x1)()(PrxpxK)(xpr)()(xpxKr•定义4.14称一个多项式时间概率算法M可解一个语言L的成员识别问题，若对任一输入数据，有（1）若，则（2）若，则称一个语言L的成员识别问题属于BPP类，若存在一个可解该问题的多项式时间概率算法。所有BPP类问题构成的集记作BPP。*1,0xLxLx3/21)(Prxb3/20)(Prxb小结•计算复杂性理论是现代密码学的理论基础。•关于算法的时间复杂性有两种定义方法：一是用一个图灵机表示一个算法，该算法的时间复杂性定义为该图灵机运行的步数；二是定义一个算法的时间复杂性为该算法的比特运算次数。本章使用前者。•关于判定问题到语言成员识别问题的合理编码，关于估计算法的比特运算次数的方法，关于NP完全问题。