Shor量子算法的优化及模拟实现 ——Shor大数分解算法改进和模拟实现及在量子密码学中的应用研究

论文摘要

经典的大数因子分解对所有的现行计算机而言是难解的,现在通用的公共加密系统正式利用这一困难作为加密的基础,但是量子计算机上进行的Shor量子算法使大数因子分解不再是难解的而是有效的,因而可能对现有通用的公共加密系统形成挑战。量子计算是以量子物理和数学的基本理论为基础的,它要求代表量子位的二态量子体系之间存在相互作用,并可以用于计算。而且可以通过某种特别的外界作用,从外部来操作和控制他们的态的变化以实现所需的计算过程。量子计算机是量子力学在信息领域中的直接应用,量子计算机的研究是当前信息科学领域的一个很活跃的课题。量子计算机是相对于经典计算机而言的,它采用的算法就是量子算法。本文结合量子力学的性质,介绍了Shor量子算法相关知识。本文主要讨论内容是怎么提高Shor量子算法分解的成功率率以及怎么去模拟实现。同时文章还介绍了量子算法目前的模拟实现方法,着重介绍C++的模拟。第一章介绍了本课题研究的意义、背景以及国内外研究的现状,并且对量子计算的最新研究方向和进展进行了介绍。第二章对量子计算的基本概念进行了概述,从量子比特、量子寄存器、量子逻辑门以及量子并行性和量子复杂度等方面介绍了量子计算。第三章针对密码体制进行了量子算法分析,以便对Shor量子算法有更深入的了解。第四章详细介绍了Shor量子算法并指出了Shor量子算法分解成功率的一些问题,然后对量子方面进行了理论改进,最后进行理论上的证明。第五章以C++为模拟工具对Shor量子算法进行模拟实验。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 本课题研究的意义以及研究方法
• 1.3 本课题研究的主要内容
• 1.4 国内外研究现状
• 1.5 本章小节
• 第二章 量子算法的基本概念
• 2.1 量子位（QUBIT）
• 2.2 多量子位
• 2.3 量子寄存器
• 2.4 量子逻辑门（QUANTUM LOGIC GATE）
• 2.4.1 经典逻辑门与量子逻辑门
• 2.5 量子并行计算（quantum parallel computing）
• 2.5.1 以Deutsch 量子算法举例来说明量子的并行性
• 2.6 算法复杂性理论
• 2.7 量子算法模拟技术现状
• 2.8 本章小结
• 第三章 密码体制的量子算法分析
• 3.1 现有的数据加密算法的介绍
• 3.2 子群上的量子算法
• 3.2.1 函数求周期
• 3.3 群元素求阶
• 3.4 隐子群问题
• 3.4.1 可归结为隐子群问题的密码体制
• 3.4.2 可以归结为整数分解问题的密码体制
• 3.5 离散对数问题
• 3.5.1 离散对数问题量子算法
• 3.5.2 可以归结为离散对数问题的密码体制
• 3.6 对RSA 公钥体制的分析
• 3.7 EIGamal 体制、ECC 体制的分析
• 3.8 量子加密技术探讨
• 3.9 本章小节
• 第四章 Shor 算法及其改进
• 4.1 有效算法和概率有效算法
• 4.2 Shor 算法
• 4.2.1 Shor 算法的主要步骤
• 4.2.2 求f（x）的周期
• 4.3 Shor 算法的改进及理论证明
• 4.3.1 Shor 算法分解时的一些不足
• 4.3.2 优化思想及理论证明
• 4.4 本章小节
• 第五章 Shor 算法的模拟实现
• 5.1 以C++为模拟工具的模拟实现
• 5.1.1 模拟程序的结构以及代码
• 5.1.2 模拟程序模拟实现
• 5.2 本章小节
• 第六章 总结与展望
• 6.1 总结
• 6.2 展望
• 致谢
• 参考文献
• 附录：作者在攻读硕士学位期间发表的论文