密码学与非确定型图灵机

• 作者: 杨正瓴
• 来源期刊: 中国电子科学研究院学报
• 学科: 工学
• 关键词: 信息和网络安全 密码学 计算机科学 非确定型图灵机 P对NP
• 年，卷（期）: 2008,（6）
• 所属期刊栏目: "信息和网络安全"专题
• 页码范围: 558-562
• 页数: 5页
• 分类号: TN918|TP301.5
• 字数: 4149字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-5692.2008.06.002

摘要

密码学是信息和网络安全的主要基础,计算机科学是密码学的主要基础,"P对NP"问题又是理论计算机科学的基础问题.首先介绍确定型图灵机DTM、非确定型图灵机NDTM的基本概念,接着介绍"P对NP"问题的基本含义.然后介绍计算机科学家Stephen Cook在2003年的观点:如果证明了P等于NP,那么依据计算复杂性的密码术就是没有用途的;如果证明了P不等于NP,那么证明RSA、DES等密码术的安全性比解决"P对NP"问题还困难.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨正瓴	天津大学电气与自动化工程学院	56	660	15.0	23.0