大数分解问题是经典 RSA 公钥密码体系安全基石。 Shor 量子算法虽能在多项式时间内求解该问题,但其实现所需的巨量物理资源使得短期内无法对实用规模 RSA 构成实际威胁。清华大学物理系龙桂鲁研究组围绕低资源大数分解量子算法展开系列研究。一方面,团队提出“经典格基约化 + 量子优化”的量经混合分解算法(HAIFA),在国际上首次实现了在量子硬件的 48 位整数分解,刷新量子硬件设备分解整数的世界纪录。另一方面,针对 Regev 高维分解算法,团队提出基于中间去计算技术的时空复杂度可调通用计算框架 (STAIF),从理论上将空间复杂度从 O (n 3/2) 降至 O(n log n),并完成相关方案的实验验证。这些研究为大数分解提供“近期可用”和“远期优化”的两种互补的方案,为评估量子计算对经典密码体系的威胁提供了新的分析依据。
The emergence of some quantum algorithms has brought a serious threat to modern cryptography,among which Shor’s algorithm is the most important threatening algorithm for cryptanalysis currently.Shor’s algorithm can solve the integer factorization problem (IFP) and discrete logarithm problem (DLP) in polynomial-time,which makes the current widely used RSA,ElGamal and ECC public key cryptosystem unsafe any more under the quantum computing environment.Therefore,it is necessary to research the cryptanalysis in the quantum computing environment.Solving the IFP is the core idea of Shor’s algorithm for attacking RSA,but breaking RSA does not have to be solved by solving the IFP.A quantum algorithm is designed to attack the RSA cryptosystem starting from the angle of non-factorization.Focusing on the characteristics of RSA public key cryptosystem,using the quantum Fourier transform,the RSA plaintext
M can be got by calculating the
eth root modulus
n .That is,without solving the IFP,RSA is broken.Different from the previous practices that cryptanalysts try to recover the private-key,a ciphertext-only attack algorithm for RSA,directly from recovering the plaintext
M to start, is presented.Results show that the probability of success of the new algorithm is higher than that of Shor’s algorithm attacking RSA.At the same time,the new algorithm does not recover the RSA plaintext from the ciphertext without factoring the modulus
n ,and avoids the restriction that the order of ciphertext
C modules
n is even.
组合优化问题广泛存在于金融、物流与人工智能等领域,其NP难性质使得经典算法在大规模问题上面临计算瓶颈。量子计算利用叠加、纠缠和量子隧穿等特性为该类问题提供了新的求解范式,在组合优化问题中的应用引起了越来越多的研究兴趣。本文系统回顾了量子组合优化的研究进展,重点介绍了三类算法路径:变分量子算法、基于Ising模型的量子退火和伊辛机以及包括基于Grover搜索、量子漫步和高斯玻色采样的其他量子组合优化算法。随后,围绕问题映射、性能评价与物理实现方面展开了探讨。最后,总结了量子组合优化在硬件、算法和应用方面的主要挑战,并展望了未来在可拓展性、约束建模和跨领域应用的发展趋势。
Quantum machine learning is the combination of quantum computing and classical machine learning. It helps in solving the problems of one field to another field. Shor’s algorithm is used for factoring the integers in polynomial time. Since the bestknown classical algorithm requires super polynomial time to factor the product of two primes, the widely used cryptosystem, RSA, relies on factoring being impossible for large enough integers. In this paper we will focus on the quantum part of Shor’s algorithm, which actually solves the problem of period finding. In polynomial time factoring problem can be turned into a period finding problem so an efficient period finding algorithm can be used to factor integers efficiently.
КВАНТОВЫЕ КОМПЬЮТЕРЫ И КВАНТОВЫЕ АЛГОРИТМЫ Часть 2. КВАНТОВЫЕ АЛГОРИТМЫ В. М. Соловьев Соловьев Владимир Михайлович, кандидат технических наук, доцент кафедры математической кибернетики и компьютерных наук, начальник Поволжского регионального центра новых информационных технологий, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского,
One of the most well known mathematically hard problems in number theory is the integer factorization problem, roughly stated that decomposition of a composite number into its prime factors. In modern cryptography, RSA encryption algorithm whose security is based on integer factorization problem is highly practical, widespread and up to date no classical algorithm having polynomial running time for the factorization of large numbers is known. In 1994, Peter Shor proposed an efficient algorithm on quantum computer. In this paper, we mention about the fundamentals of Shor's quantum algorithm illustrating a concrete example.