Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Scientia Sinica Informationis

The status and prospect of quantum-classical combination integer factorization algorithm

Bao YAN, Shijie Wei, Guilu LONG

Published May 26, 2025• 3 citations
Publisher

Abstract

整数分解问题不仅是经典的数学难题,更是广泛应用的 RSA 公钥密码体制的安全基石。自上世纪八十年代 RSA 密码问世以来,它受到了前所未有的关注,并得到了广泛而深入的研究。对该问题的研究推动了多个领域的发展,尤其是 Shor 量子大数分解算法提出后,更是直接推动了量子计算领域的发展。本文简要回顾了该问题的研究历史及重要进展,以及随着量子计算技术的发展,该问题研究的技术路线与研究角度所发生的变化,特别是2022年中国学者提出的可以利用现在一代的量子计算机运行的量子经典融合大数分解算法的原理,及其加速机制。国际最新进展表明,该技术路线的分解能力已从算法初期的48比特(2022年)提升至100比特(2024年),意大利与德国联合团队基于格基约化理论与张量网络的复杂性分析,进一步验证了其比特资源与时间复杂度均满足多项式约束。本文系统梳理该领域的技术演进脉络,并基于算法扩展性实验与抗量子密码迁移进程,探讨其对未来信息安全体系的潜在影响。

DOI
10.1360/ssi-2025-0105

Related papers

Research progress on low-resource quantum algorithms for integer factorization

YAN Bao, Wentao Yang, shijie wei +1 more

大数分解问题是经典 RSA 公钥密码体系安全基石。 Shor 量子算法虽能在多项式时间内求解该问题,但其实现所需的巨量物理资源使得短期内无法对实用规模 RSA 构成实际威胁。清华大学物理系龙桂鲁研究组围绕低资源大数分解量子算法展开系列研究。一方面,团队提出“经典格基约化 + 量子优化”的量经混合分解算法(HAIFA),在国际上首次实现了在量子硬件的 48 位整数分解,刷新量子硬件设备分解整数的世界纪录。另一方面,针对 Regev 高维分解算法,团队提出基于中间去计算技术的时空复杂度可调通用计算框架 (STAIF),从理论上将空间复杂度从 O (n 3/2) 降至 O(n log n),并完成相关方案的实验验证。这些研究为大数分解提供“近期可用”和“远期优化”的两种互补的方案,为评估量子计算对经典密码体系的威胁提供了新的分析依据。

Zhongguo kexue. Wulixue Lixue Tianwenxue•Apr 23, 2026•0 citations

Quantum Algorithm for Attacking RSA Based on the eth Root

Yahui WANG, Huanguo Zhang, Houzhen Wang

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 ${e^{{th}}}$ 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.

•Jan 1, 2018•0 citations

Studies of quantum combinatorial optimization algorithms: a review

Zhan Li, Yusen Wu, Runqing Zhang +3 more

组合优化问题广泛存在于金融、物流与人工智能等领域,其NP难性质使得经典算法在大规模问题上面临计算瓶颈。量子计算利用叠加、纠缠和量子隧穿等特性为该类问题提供了新的求解范式,在组合优化问题中的应用引起了越来越多的研究兴趣。本文系统回顾了量子组合优化的研究进展,重点介绍了三类算法路径:变分量子算法、基于Ising模型的量子退火和伊辛机以及包括基于Grover搜索、量子漫步和高斯玻色采样的其他量子组合优化算法。随后,围绕问题映射、性能评价与物理实现方面展开了探讨。最后,总结了量子组合优化在硬件、算法和应用方面的主要挑战,并展望了未来在可拓展性、约束建模和跨领域应用的发展趋势。

Chinese Science Bulletin (Chinese Version)•Oct 30, 2025•0 citations

Implementation of Shor’s Algorithm in QISKIT by Quantum Computing using IBMQ

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.

International Journal of Advanced Trends in Computer Science and Engineering•Apr 5, 2021•0 citations

Quantum Computers and Quantum Algorithms. Part 2. Quantum Algorithms

V. M. Solovyev

КВАНТОВЫЕ КОМПЬЮТЕРЫ И КВАНТОВЫЕ АЛГОРИТМЫ Часть 2. КВАНТОВЫЕ АЛГОРИТМЫ В. М. Соловьев Соловьев Владимир Михайлович, кандидат технических наук, доцент кафедры математической кибернетики и компьютерных наук, начальник Поволжского регионального центра новых информационных технологий, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского,

Izvestiya of Saratov University Mathematics Mechanics Informatics•Jan 1, 2016•4 citations

Fundamental Structure of Shor’s Quantum Algorithm for Factoring Integers

Turgut Hanoymak, Akram Chehrazi

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.

Turkish Journal of Mathematics and Computer Science•Dec 31, 2019•0 citations
整数分解问题不仅是经典的数学难题,更是广泛应用的 RSA 公钥密码体制的安全基石。自上世纪八十年代 RSA 密码问世以来,它受到了前所未有的关注,并得到了广泛而深入的研究。对该问题的研究推动了多个领域的发展,尤其是 Shor 量子大数分解算法提出后,更是直接推动了量子计算领域的发展。本文简要回顾了该问题的研究历史及重要进展,以及随着量子计算技术的发展,该问题研究的技术路线与研究角度所发生的变化,特别是2022年中国学者提出的可以利用现在一代的量子计算机运行的量子经典融合大数分解算法的原理,及其加速机制。国际最新进展表明,该技术路线的分解能力已从算法初期的48比特(2022年)提升至100比特(2024年),意大利与德国联合团队基于格基约化理论与张量网络的复杂性分析,进一步验证了其比特资源与时间复杂度均满足多项式约束。本文系统梳理该领域的技术演进脉络,并基于算法扩展性实验与抗量子密码迁移进程,探讨其对未来信息安全体系的潜在影响。
大数分解问题是经典 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 MMM can be got by calculating the eth{e^{{th}}}eth root modulus nnn .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 MMM 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 nnn ,and avoids the restriction that the order of ciphertext CCC modules nnn 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.