P vs. NP问题研究状态及其对密码学的意义

• 作者: 姜新文 彭立宏 王琪
• 来源期刊: 计算技术与自动化
• 关键词: P vs.NP 密码学 NP完全 计算复杂性 MSP
• 年，卷（期）: 2010,（3）
• 页码范围: 66-72
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1003-6199.2010.03.014

摘要

介绍P vs. NP问题的研究状态以及P vs. NP问题的研究对于密码学的意义.主要内容包括关于证明P≠NP的主要研究方法和相关工作,关于证明P=NP的主要研究方法和相关工作,关于求解NP完全问题的相关方法,以及P vs. NP问题研究与密码学的关系.由于现代密码学建立在未知密钥情况下不存在有效的算法将明文消息从密文中提取出来的假定之上,因此安全加密算法存在的一个必要条件是P≠NP.如果P=NP,根据Cook的观点,现代密码体制将崩溃.依据P=NP的假定,给出一个可能的密码分析模型.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姜新文	国防科技大学计算机学院	18	101	6.0	8.0
2	王琪	国防科技大学计算机学院	2	8	2.0	2.0
3	彭立宏	国防科技大学计算机学院	10	42	3.0	6.0