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

arXiv:2307.09651

A comment on "Factoring integers with sublinear resources on a superconducting quantum processor"

Tanuj Khattar, Noureldin Yosri

Published Jul 18, 2023• 14 citations
arXivHTMLPDF

Abstract

Quantum computing has the potential to revolutionize cryptography by breaking classical public-key cryptography schemes, such as RSA and Diffie-Hellman. However, breaking the widely used 2048-bit RSA using Shor's quantum factoring algorithm is expected to require millions of noisy physical qubits and is well beyond the capabilities of present day quantum computers. A recent proposal by Yan et. al. tries to improve the widely debated Schnorr's lattice-based integer factorization algorithm using a quantum optimizer (QAOA), and further claim that one can break RSA 2048 using only 372 qubits. In this work, we present an open-source implementation of the algorithm proposed by Yan et. al. and show that, even if we had a perfect quantum optimizer (instead of a heuristic like QAOA), the proposed claims don't hold true. Specifically, our implementation shows that the claimed sublinear lattice dimension for the Hybrid quantum+classical version of Schnorr's algorithm successfully factors integers only up to 70 bits and fails to find enough factoring relations for random 80 bit integers and beyond. We further hope that our implementation serves as a playground for the community to easily test other hybrid quantum + classical integer factorization algorithm ideas using lattice based reductions.

DOI
10.48550/arxiv.2307.09651

Related papers

Factoring integers with sublinear resources on a superconducting quantum processor

Yan, Bao, Ziqi Tan, Shijie Wei +21 more

Shor's algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. Here, we report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA). The number of qubits required is O(logN/loglog N), which is sublinear in the bit length of the integer $N$, making it the most qubit-saving factorization algorithm to date. We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm. Our study shows great promise in expediting the application of current noisy quantum computers, and paves the way to factor large integers of realistic cryptographic significance.

arXiv:2212.12372•Dec 23, 2022•113 citations

Pitfalls of the Sublinear QAOA-Based Factorization Algorithm

Sergey V. Grebnev, Maxim A. Gavreev, Evgeniy O. Kiktenko +3 more

Quantum computing devices are believed to be powerful in solving the prime factorization problem, which is at the heart of widely deployed public-key cryptographic tools. However, the implementation of Shor’s quantum factorization algorithm requires significant resources scaling linearly with the number size; taking into account an overhead that is required for quantum error correction the estimation is that 20 millions of (noisy) physical qubits are required for factoring 2048-bit RSA key in 8 hours. Recent proposal by Yan et. al. claims a possibility of solving the factorization problem with sublinear quantum resources. As we demonstrate in our work, this proposal lacks systematic analysis of the computational complexity of the classical part of the algorithm, which exploits the Schnorr’s lattice-based approach. We provide several examples illustrating the need in additional resource analysis for the proposed quantum factorization algorithm.

arXiv:2303.04656•IEEE Access•Jan 1, 2023•11 citations

Practical Challenges in Executing Shor's Algorithm on Existing Quantum Platforms

Paul Bagourd, Julian Jang-Jaccard, Vincent Lenders +3 more

Quantum computers pose a fundamental threat to widely deployed public-key cryptosystems, such as RSA and ECC, by enabling efficient integer factorization using Shor's algorithm. Theoretical resource estimates suggest that 2048-bit RSA keys could be broken using Shor's algorithm with fewer than a million noisy qubits. Although such machines do not yet exist, the availability of smaller, cloud-accessible quantum processors and open-source implementations of Shor's algorithm raises the question of what key sizes can realistically be factored with today's platforms. In this work, we experimentally investigate Shor's algorithm on several cloud-based quantum computers using publicly available implementations. Our results reveal a substantial gap between the capabilities of current quantum hardware and the requirements for factoring cryptographically relevant integers. In particular, we observe that circuit constructions still need to be highly specific for each modulus, and that machine fidelities are unstable, with high and fluctuating error rates.

quant-pharXiv:2512.15330•Dec 18, 2025•2 citations

Enhanced Security Algorithm for Integer Factorization in Quantum Computing: Optimizing Shor’s Algorithm

Rashmi Kuksal, Sumit Chaudhary, Ashish Bhatt

With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.

International Conference on Innovative Mechanisms for Industry Applications•Oct 1, 2026•0 citations

The Impact of Quantum Noise on Shor's Algorithm and Its Cryptographic Applications

Wael M. F. Abdel-Rehim

Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.

•May 12, 2025•2 citations

A Novel Hybrid Quantum Circuit for Integer Factorization: End-to-End Evaluation in Simulation and Real Quantum Hardware

Jesse Van Griensven Thé, Victor Oliveira Santos, Bahram Gharabaghi

The literature indicates that the qubit requirements for factoring RSA-2048 remain on the order of 1 million, under commonly assumed architectures and error-correction models, leaving a substantial gap between current resource estimates and near-term practical feasibility. Reducing this requirement to the low-thousand-qubit regime therefore remains an important open research objective. This work proposes a hybrid classical–quantum algorithm that uses a classical modular exponentiation subroutine with a Quantum Number Theoretic Transform (QNTT) circuit to increase the speed and reduce the required quantum resources relative to Shor’s algorithm for integer factorization, which underpins cryptographic systems like RSA and ECC. We evaluate multiple coprime numbers, the result of multiplication of two primes, in both simulation and real quantum hardware, using IBM’s reference Shor implementation as the baseline. Because Shor and proposed Jesse–Victor–Gharabaghi (JVG) use different register sizes for the same coprime N, the reported gate/depth reductions should be interpreted as end-to-end quantum-resource budgets for factoring the same N, rather than a per-qubit or transform-only efficiency claim. In simulation, the JVG algorithm achieved substantial practical reductions in computational resources, decreasing runtime from 174.1 s to 5.4 s, memory usage from 12.5 GB to 0.27 GB, and quantum gate counts by approximately 99%. On quantum hardware, JVG reduced the required runtime from 67.8 s to 2 s, and the quantum gate counts by over 98%. We showed that the proposed algorithm can address the relevant RSA-1024 case scenario, establishing that this method can provide validation for large-scale situations. Furthermore, extrapolation to RSA-2048 indicates that the JVG algorithm significantly outperforms Shor’s approach, requiring a projected quantum runtime of 29 h for ten thousand runs for factorization under identical scaling assumptions. Overall, these results support JVG as a more hardware-compatible and robust noise-tolerant substitute for Shor’s framework, offering a viable research direction toward practical quantum integer factorization on near-term Noisy Intermediate-Scale Quantum (NISQ) devices.

Journal of Cybersecurity and Privacy•Apr 10, 2026•0 citations
Quantum computing has the potential to revolutionize cryptography by breaking classical public-key cryptography schemes, such as RSA and Diffie-Hellman. However, breaking the widely used 2048-bit RSA using Shor's quantum factoring algorithm is expected to require millions of noisy physical qubits and is well beyond the capabilities of present day quantum computers. A recent proposal by Yan et. al. tries to improve the widely debated Schnorr's lattice-based integer factorization algorithm using a quantum optimizer (QAOA), and further claim that one can break RSA 2048 using only 372 qubits. In this work, we present an open-source implementation of the algorithm proposed by Yan et. al. and show that, even if we had a perfect quantum optimizer (instead of a heuristic like QAOA), the proposed claims don't hold true. Specifically, our implementation shows that the claimed sublinear lattice dimension for the Hybrid quantum+classical version of Schnorr's algorithm successfully factors integers only up to 70 bits and fails to find enough factoring relations for random 80 bit integers and beyond. We further hope that our implementation serves as a playground for the community to easily test other hybrid quantum + classical integer factorization algorithm ideas using lattice based reductions.
Shor's algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. Here, we report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA). The number of qubits required is O(logN/loglog N), which is sublinear in the bit length of the integer NNN, making it the most qubit-saving factorization algorithm to date. We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm. Our study shows great promise in expediting the application of current noisy quantum computers, and paves the way to factor large integers of realistic cryptographic significance.
Quantum computing devices are believed to be powerful in solving the prime factorization problem, which is at the heart of widely deployed public-key cryptographic tools. However, the implementation of Shor’s quantum factorization algorithm requires significant resources scaling linearly with the number size; taking into account an overhead that is required for quantum error correction the estimation is that 20 millions of (noisy) physical qubits are required for factoring 2048-bit RSA key in 8 hours. Recent proposal by Yan et. al. claims a possibility of solving the factorization problem with sublinear quantum resources. As we demonstrate in our work, this proposal lacks systematic analysis of the computational complexity of the classical part of the algorithm, which exploits the Schnorr’s lattice-based approach. We provide several examples illustrating the need in additional resource analysis for the proposed quantum factorization algorithm.
Quantum computers pose a fundamental threat to widely deployed public-key cryptosystems, such as RSA and ECC, by enabling efficient integer factorization using Shor's algorithm. Theoretical resource estimates suggest that 2048-bit RSA keys could be broken using Shor's algorithm with fewer than a million noisy qubits. Although such machines do not yet exist, the availability of smaller, cloud-accessible quantum processors and open-source implementations of Shor's algorithm raises the question of what key sizes can realistically be factored with today's platforms. In this work, we experimentally investigate Shor's algorithm on several cloud-based quantum computers using publicly available implementations. Our results reveal a substantial gap between the capabilities of current quantum hardware and the requirements for factoring cryptographically relevant integers. In particular, we observe that circuit constructions still need to be highly specific for each modulus, and that machine fidelities are unstable, with high and fluctuating error rates.
With the rise of large-scale quantum computers, it becomes difficult to sustain the security principles of popular public-key encryption systems, including RSA, which is based on the classical problem of integer factorization. Shor’s algorithm suggests that a large enough quantum computer may find factors of an n-bit integer in polynomial time, thus becoming a threat to RSA and similar encryption techniques once the technology of fault-tolerant hardware reaches maturity. However, current implementation is subject to several limitations regarding the number of qubits available, circuit depth, and the vulnerability to decoherence in NISQ computing. The proposed algorithm in this work provides an improved version of Shor’s algorithm that implements classical pre-processing heuristics, adaptive choice of bases, a low-depth circuit for modular exponentiation, and a compressed approximate quantum Fourier transform (AQFT) step to minimize qubit usage and depth while preserving the accuracy of period finding. The simulation results performed for different modulus sizes from 8 to 256 bits show that the suggested approach allows for reducing the number of logical qubits by about 29% and increases the success rate of the algorithm from 41% to 63%. The security considerations of such optimizations concerning the timelines of migrating from existing cryptographic systems to post-quantum systems will be addressed, as well as the possible approaches to hybrid classical and quantum factorization pipelines.
Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.
The literature indicates that the qubit requirements for factoring RSA-2048 remain on the order of 1 million, under commonly assumed architectures and error-correction models, leaving a substantial gap between current resource estimates and near-term practical feasibility. Reducing this requirement to the low-thousand-qubit regime therefore remains an important open research objective. This work proposes a hybrid classical–quantum algorithm that uses a classical modular exponentiation subroutine with a Quantum Number Theoretic Transform (QNTT) circuit to increase the speed and reduce the required quantum resources relative to Shor’s algorithm for integer factorization, which underpins cryptographic systems like RSA and ECC. We evaluate multiple coprime numbers, the result of multiplication of two primes, in both simulation and real quantum hardware, using IBM’s reference Shor implementation as the baseline. Because Shor and proposed Jesse–Victor–Gharabaghi (JVG) use different register sizes for the same coprime N, the reported gate/depth reductions should be interpreted as end-to-end quantum-resource budgets for factoring the same N, rather than a per-qubit or transform-only efficiency claim. In simulation, the JVG algorithm achieved substantial practical reductions in computational resources, decreasing runtime from 174.1 s to 5.4 s, memory usage from 12.5 GB to 0.27 GB, and quantum gate counts by approximately 99%. On quantum hardware, JVG reduced the required runtime from 67.8 s to 2 s, and the quantum gate counts by over 98%. We showed that the proposed algorithm can address the relevant RSA-1024 case scenario, establishing that this method can provide validation for large-scale situations. Furthermore, extrapolation to RSA-2048 indicates that the JVG algorithm significantly outperforms Shor’s approach, requiring a projected quantum runtime of 29 h for ten thousand runs for factorization under identical scaling assumptions. Overall, these results support JVG as a more hardware-compatible and robust noise-tolerant substitute for Shor’s framework, offering a viable research direction toward practical quantum integer factorization on near-term Noisy Intermediate-Scale Quantum (NISQ) devices.