现代密码学第三讲：复杂性理论

1复杂性理论《现代密码学》第三讲上讲内容回忆Shannon通信保密系统熵和无条件保密分组密码的设计思想本章主要内容问题的定义及分类算法复杂度定义及分类P问题和NP问题规约思想与NPC类密码算法的计算平安性问题的定义及分类1设A=(a1,a2,…,an)是由n个不同的正整数构成的n元组，S是另一的正整数.A称为背包向量，S称为背包容积.求A中元素集合A’，使.2设背包向量A=(1,2,5,10,20,50,100),背包容积为177，求向量，使得.问题的定义及分类3整数N，问N是否是一个素数？4试问77是否是素数？5试问79是否是素数？6整数N，求N的素分解式.7整数177，求其素分解式.问题的定义及分类问题：描述参量陈述解容许当满足的性质〔称为询问〕.参量为具体数值时，称为问题的一个实例.判定问题：答复只有Yes或No.计算问题：从其可行解集合中搜索出最优解.7算法复杂度的定义例设x是小于100的某个整数，问x是否是素数？解答一：取2～的所有整数，依次试除x，假设存在某个整数可以整除x，那么程序停止，输出x为合数，否那么输出x为素数.最坏试除次数：存储空间：0解答二：预先将所有小于100的素数存储在存放器中；然后将X与存储器中的元素比较，假设存在某个素数等于x，那么程序停止，输出x为素数，否那么输出x为合数.最坏比较次数:100/ln100,存储空间:100/ln1008算法复杂度的定义时间〔计算〕复杂性：考虑算法的主要操作步骤，计算执行中所需的总操作次数.空间复杂性：执行过程中所需存储器的单元数目.数据复杂性：信息资源.计算模型----确定性图灵机〔有限带符号集合，有限状态集，转换函数〕〔读写头，读写带〕.算法复杂度的定义不同的编程语言，不同的编译器导致执行一次操作的时间各不相同，为了方便不同算法比较，通常假定所有计算机执行相同的一次根本操作所需时间相同，而把算法中根本操作执行的最大次数作为执行时间.根本操作数量运行时间=机器速度10算法复杂度的定义定义假设一个算法的计算复杂度为O(nt)，其中t为常数，n为输入问题的长度，那么称这算法的复杂度是多项式的。具有多项式时间复杂度的算法为多项式时间算法.函数g(n)=O(nt)表示存在常数c>0和n0>=0，对一切n>n0均有|g(n)|<=c|nt|成立，也就是说，当n足够大时，g(n)存在上界.定义非多项式时间算法：算法的计算复杂性写不成O(P(n))形式，其中P(n)表示n的多项式函数.算法复杂度的定义例

设x是小于100的某个整数，问x是否是素数？

解法1是否是多项式时间算法？

解法2是否是多项式时间算法？12P问题和NP问题定义(P问题)如果一个判定问题存在解它的多项式时间的算法，那么称该问题属于P类.定义(NP问题)如果一个判定问题不存在解它的多项式时间的算法，且对于一个解答可以在多项式时间验证其是否正确，那么称该问题属于NP类.公开问题：P≠NP？它是Clay研究所的七个百万美元大奖问题之一密码算法的计算平安性二次函数、三次函数、2x函数的示意图

14密码算法的计算平安性例.设问题输入长度为n，在一个每秒钟运行百万次的计算机上的运行时间如下:10305060T(n)=n20.0001s0.0009s0.0025s0.0036sT(n)=2n0.001s17.9月35.7年366世纪密码算法的计算平安性当问题输入长度足够大，分析密码体制的算法的复杂度较大，可能的计算能力下，在保密的期间内可以保证算法不被攻破，这就是密码体制的计算平安性思想。注：分析方法是无穷无尽的，类似于解决问题的算法，目前不存在非多项式时间的分析方法，将来可能存在，即算法将来可能不堪一击.如差分分析出现。。。16密码算法的计算平安性密码系统设计：合法用户——易〔多项式〕攻击者——难〔非多项式〕注：计算模型----图灵机量子计算机出现导致分解因子问题容易，从而RSA等密码系统不再平安，缘由是计算模型不同.非多项式时间问题多项式问题17规约思想与NPC类定义判定问题，.假设存在的解法S1，那么通过调用S1〔作为子程序〕，可以在多项式时间内解问题，那么称可多项式规约至“∝〞定义假设判定问题∈NP，对每个判定问题∈NP，都有∝，那么称属于NPC类，或称为NP完全的.规约思想与NPC类主要知识点小结算法的复杂度定义及分类密码算法的计算复杂度20作业1求冒泡排序法的计算复杂度,该算法是否为多项式的？2超递增背包问题：设A=(a1,a2,…,an)是由n个不同的正整数构成的n元组，且