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

摘要

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