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

摘要

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

目录

文摘

英文文摘

声明

第一章绪论

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.5算法复杂性理论

2.6量子算法模拟技术现状

2.7本章小结

第三章密码体制的量子算法分析

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展望

致谢

参考文献

附录： 作者在攻读硕士学位期间发表的论文