现代密码学第三讲：复杂性理论.ppt
约21页PPT格式手机打开展开
现代密码学第三讲：复杂性理论,本章主要内容问题的定义及分类算法复杂度定义及分类p问题和np问题规约思想与npc类密码算法的计算安全性问题的定义及分类1 设a=(a1,a2,,an)是由n个不同的正整数构成的n元组，s是另一已知的正整数. a称为背包向量，s称为背包容积. 求a中元素集合a’，使 .2设背包向量a=(1,2,5,10,20,50,10...
内容介绍
此文档由会员 1406978338 发布
本章主要内容
问题的定义及分类
算法复杂度定义及分类
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，求其素分解式.
问题的定义及分类
算法复杂度定义及分类
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，求其素分解式.
