SHOR量子算法的原理与程序模拟

本文首先介绍大数质因子分解的Shor量子算法的原理、实现步骤和实现方法，然后用现存的模拟器在常规计算机上加以模拟。最后讨论了Shor算法模拟的意义，并对量子计算提出了看法。     

整数质因子分解算法新进展与传统密码学面临的挑战

大整数的质因子分解研究是现代数论领域的一个重要课题,其中涉及很多开问题.随着信息时代的来临,大整数质因子分解的复杂性更成为现代密码学的重要理论基础.著名的RSA公钥密码系统的安全性即建立在解决此问题的困难性之上.本文系统地综述了现代理论计算机科学研究中提出的几种解决该问题的新算法,并介绍了量子计算机高效解决此问题的原理和实现方式.最后,本文讨论了在未来量子计算时代传统密码学所面临的挑战并展望了量子密码学的前景.     

量子理论在信息安全领域的应用前景

由于量子的特性，许多问题采用经典计算机只能进行指数算法，而量子计算机能用多项式算法来完成，如采用量子计算机可以在多项式时间内进行大数因子分解，因而对于现有的密码体制构成威胁。量子密码学以及量子隐形传态可以进行保密通信，窃听者不可能得到信息，并且合法用户会发现窃听的存在，这些是现在的密码体制所不可以比拟的。     

基于Grover搜索算法的整数分解

非结构化搜索是计算机科学中最基本的问题之一,而Grover量子搜索算法就是针对非结构化搜索问题设计的。Grover量子搜索算法可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。文中提出基于Grover搜索算法并结合经典预处理实现整数分解。首先基于IBMQ云平台对不同量子比特的Grover算法量子电路进行了仿真,以及模拟使用Grover算法求解N的素因子P和Q;然后将化简后的方程转化为布尔逻辑关系,以此来构建Grover算法中的Oracle;最后通过改变迭代次数来改变搜索到解的概率。仿真结果验证了使用Grover算法求解素因子P和Q的可行性。文中实现了在搜索空间为16且一次G迭代条件下以近78%的成功概率搜索到目标项。文中还比较了Grover算法与Shor算法在求解一些数字时所耗费的量子比特数和时间渐近复杂度的差异。通过Grover量子搜索算法分解整数的实验拓展了该算法的应用领域,Grover算法的加速效果在大型搜索问题中尤为明显。     

一种强素数因子分解的量子算法

深入分析了RSA模数N的强素数因子的特殊结构,进一步确定了2对N的阶δN（2）与Euler函数?准（N）之间的关系,提出了新的分解由强素数因子乘积构成的RSA模N的量子算法,简化了因子分解的过程,提高了运算效率。     

一种新的攻击RSA的量子算法

整数分解是数论中一个非常古老的难解性问题,而对于当今世界上最有名且广泛使用的RSA公钥密码体制,其安全性是基于整数分解的难解性的。迄今为止,最有希望破解RSA的方法就是Shor的量子算法。利用RSA不动点性质,基于量子Fourier变换和变量代换,提出了一种新的攻击RSA的量子算法。该算法不需要分解n,而是从RSA密文C中直接恢复其明文M。该算法与Shor算法相比,需要的量子位更少,且成功概率大于1/2。最后将新算法的资源消耗情况与Shor算法的进行了对比。     

量子计算机进入实验阶段

首先简要介绍分层计算的制约;其次介绍最近量子信息的开发,在理论和实践两方面的通信和计算,诸如量子逻辑门、量子密码学、量子交缠性、超距传输的实验性实现、量子算法的首次实验性实现、量子因子分解、量子纪错码以及基于硅片的原子自旋量子计算机;最后讨论克服非相干性困难的方法。     

第一寄存器小Qubit量子计算攻击RSA研究

提出了针对RSA的小Qubit量子攻击算法设计,量子攻击的第一量子寄存器所需的Qubit数目由原先至少2L降低到L1,总体空间复杂度记为(L1,L),其中2L1≥r,r为分解所得周期。由于第一寄存器量子比特数的减少,降低了算法复杂度和成功率,且改进原算法中模幂计算,提升运算速率。改进攻击算法的量子电路的时间复杂度为T=O(2L2)。在时间复杂度和空间复杂度上都有明显的进步。改进算法的成功率降低了,但实际成功求解时间,即每次分解时间/成功率,依然低于 Shor 算法目前的主要改进算法。完成了仿真模拟实验,分别用11、10、9 Qubit成功分解119的量子电路。     

基于IBM量子计算云服务的量子傅里叶变换实现

Shor算法能够相对经典大整数分解算法实现指数加速,从而直接威胁到了RSA密码体制,而量子傅里叶变换是Shor算法中的一个关键变换,也能够相对经典离散傅里叶变换实现指数加速,从而引起了广泛关注。主要针对量子傅里叶变换的实现方案进行研究。首先介绍了IBM公司量子计算云服务的编程基础,随后设计了3比特量子傅里叶变换的量子线路,最后在IBM公司5超导量子比特的量子计算芯片上进行了实验验证。     

Grover量子搜索算法的线路优化

Grover算法是能够高效查找到目标态的量子搜索算法，但随着搜索数据量的增大，它的量子线路面临着复杂的门分解问题。在如今的NISQ时代资源非常有限，因此线路的深度成为一种重要的度量标准。介绍了一种基于分治思想的二阶段量子搜索算法，能够在量子计算机上快速地并行运行。提出一种线路优化方法，应用块级的Oracle线路来减少迭代次数。将该方法与分治思想相结合，提出2P-Grover算法。在量子计算框架Cirq上进行模拟实验，与Grover算法进行对比。实验结果表明，2P-Grover算法能够使线路的深度至少减少60%,并且保持了较高的搜索成功率。     

Factoring a Homogeneous Transformation for a more Efficient Graphics Pipeline

We identify an intermediate coordinate system situated between world coordinates and display coordinates, which exhibits unique features for lighting calculations and for clipping in homogeneous coordinates. Our key contribution is an algorithm for extracting such a coordinate system from a homogeneous viewing transformation that relates WC to DC. The algorithm is based on factoring the transformation into a product of a Euclidean factor and a sparse (computationally cheap) but non-Euclidean factor.
A particularly strong application of the proposed technique is the graphical processing of curved surface primitives, such as what is needed in the PHIGS PLUS viewing pipeline. Furthermore, in PHIGS PLUS the graphical data is retained by the graphics system, therefore, it is possible to perform the factoring of the viewing transformation at creation time, and to take advantage of this factored form at traversal time.     

On computing ordN(2) and its application

P. Shor proposed a polynomial time algorithm for prime factorization on quantum computers. For a given number N, he gave an algorithm for finding the order r of an element x in the multiplicative group (mod N). The method succeeds because factorization can be reduced to finding the order of an element using randomization. But the algorithm has two shortcomings, the order of the number must be even and the output might be a trivial factor. Actually, these drawbacks can be overcome in a particular case, i.e., N is an RSA modulus. In this paper, we propose a new quantum algorithm for factoring RSA modulus without the two drawbacks. Moreover, we show that the cost of the algorithm mainly depends on the calculation of ord_N(2).     

隐含子群问题的研究现状

在Shor发现大整数因子分解问题的有效量子算法之后,量子计算迫使我们重新审视现有的密码系统。隐含子群问题是量子计算在群结构上的推广,它暗示通过考虑不同的群和函数来解决更困难的问题,以期找到新的指数倍快于其经典对应物的量子算法。有限交换群隐含子群问题的研究已有相对固定的研究框架和方法,而非交换群隐含子群问题的研究一直很活跃。研究表明,二面体群隐含子群问题的有效解决可能攻破基于格的唯一最短向量问题的密码体制,图同构问题可以转化为对称群隐含子群问题。文中对隐含子群问题的研究现状进行综述,希望能够吸引更多研究者对隐含子群问题的注意。最后为隐含子群问题未来的研究方向提出参考意见。     

Parallel implementation of the quadratic sieve

A new version of the Quadratic Sieve algorithm, used for factoring large integers, has recently emerged. The new algorithm, called the Multiple Polynomial Quadratic Sieve, not only considerably improves the original Quadratic Sieve but also adds features that ideally suit a parallel implementation. The parallel implementation used for the new algorithm, a novel remote batching system, is also described.     

Efficient algorithms for NMR quantum computers with small qubits

The security of the RSA cryptosystems is based on the difficulty of factoring a large composite integer. In 1994, Shor showed that factoring a large composite is executable in polynomial time if we use a quantum Turing machine. Since this algorithm is complicated, straightforward implementations seem impractical judging from current technologies. In this paper, we propose simple and efficient algorithms for factoring and discrete logarithm problem based on NMR quantum computers. Our algorithms are easier to implement if we consider NMR quantum computers with small qubits. A part of this work was done while both authors were with NTT Communication Science Laboratories. Noboru Kunihiro, Ph.D.: He is Assistant Professor of the University of Electro-Communications. He received his B.E., M.E. and Ph.D. in mathematical engineering and information physics from the University of Tokyo in 1994, 1996 and 2001, respectively. He had been engaged in the research on cryptography and information security at NTT Communication Science Laboratories from 1996 to 2002. Since 2002, he has been working for Department of Information and Communication Engineering of the University of Elector-Communications. His research interest includes cryptography, information security and quantum computations. He was awarded the SCIS’97 paper prize. Shigeru Yamashita, Ph.D.: Associate Professor of Graduate School of Information Science, Nara Institute of Science and Technology, Nara 630-0192, Japan. He received his B.E., M.E. and Ph.D. degrees in information science from Kyoto University, Kyoto, Japan, in 1993, 1995 and 2001, respectively. His research interests include new type of computer architectures and quantum computation. He received the 2000 IEEE Circuits and Systems Society Transactions on Computer-Aided Design of Integrated Circuits and Systems Best Paper Award.     

Primality testing and factoring

We show that any efficient deterministic algorithm for finding square roots modulo a prime can be turned into an efficient Monte Carlo primality test which has a very small error probability if factoring is hard.We apply our general construction to a well-known square root algorithm and give explicit bounds for the error probability of the resulting primality test (or the running of the corresponding factoring algorithm.     

Fraction-free matrix factors: new forms for LU and QR factors

Gaussian elimination and LU factoring have been greatly studied from the algorithmic point of view, but much less from the point view of the best output format. In this paper, we give new output formats for fraction free LU factoring and for QR factoring. The formats and the algorithms used to obtain them are valid for any matrix system in which the entries are taken from an integral domain, not just for integer matrix systems. After discussing the new output format of LU factoring, the complexity analysis for the fraction free algorithm and fraction free output is given. Our new output format contains smaller entries than previously suggested forms, and it avoids the gcd computations required by some other partially fraction free computations. As applications of our fraction free algorithm and format, we demonstrate how to construct a fraction free QR factorization and how to solve linear systems within a given domain.     

Fraction-free matrix factors: new forms for LU and QR factors

Gaussian elimination and LU factoring have been greatly studied from the algorithmic point of view, but much less from the point view of the best output format. In this paper, we give new output formats for fraction free LU factoring and for QR factoring. The formats and the algorithms used to obtain them are valid for any matrix system in which the entries are taken from an integral domain, not just for integer matrix systems. After discussing the new output format of LU factoring, the complexity analysis for the fraction free algorithm and fraction free output is given. Our new output format contains smaller entries than previously suggested forms, and it avoids the gcd computations required by some other partially fraction free computations. As applications of our fraction free algorithm and format, we demonstrate how to construct a fraction free QR factorization and how to solve linear systems within a given domain.     

A New Polynomial Factorization Algorithm and its Implementation

We consider the problem of factoring univariate polynomials over a finite field. We demonstrate that the new baby step/giant step factoring method, recently developed by Kaltofen and Shoup, can be made into a very practical algorithm. We describe an implementation of this algorithm, and present the results of empirical tests comparing this new algorithm with others. When factoring polynomials modulo large primes, the algorithm allows much larger polynomials to be factored using a reasonable amount of time and space than was previously possible. For example, this new software has been used to factor a "generic" polynomial of degree 2048 modulo a 2048-bit prime in under 12 days on a Sun SPARC-station 10, using 68 MB of main memory.     

旅行售货员问题的量子算法

利用波的特性在量子环境下对货郎担问题(TSP)进行了求解，介绍了这种量子算法的基本思想及相关概念，然后分析并给出了求解货郎担问题的量子算法，最后对量子算法的发展进行了展望。