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:2410.04956 · International Journal of Electronics and Telecommunications

Maximizing the practical achievability of quantum annealing attacks on factorization-based cryptography

Olgierd Żołnierczyk

Published Apr 7, 2025• 2 citations
arXivHTMLPDF

Abstract

This work focuses on quantum methods for cryptanalysis of schemes based on the integer factorization problem and the discrete logarithm problem. We demonstrate how to practically solve the largest instances of the factorization problem by improving an approach that combines quantum and classical computations, assuming the use of the best publicly available special-class quantum computer: the quantum annealer. We achieve new computational experiment results by solving the largest instance of the factorization problem ever announced as solved using quantum annealing, with a size of 29 bits. The core idea of the improved approach is to leverage known subexponential classical method to break the problem down into many smaller computations and perform the most critical ones on a quantum computer. This approach does not reduce the complexity class, but it assesses the pragmatic capabilities of an attacker. It also marks a step forward in the development of hybrid methods, which in practice may surpass classical methods in terms of efficiency sooner than purely quantum computations will.

DOI
10.24425/ijet.2025.153542

Related papers

Applications of Quantum Annealing in Cryptography

Anpeng Zhang, Xiutao Feng

This paper presents a new method to reduce the optimization of a pseudo-Boolean function to QUBO problem which can be solved by quantum annealer. The new method has two aspects, one is coefficient optimization and the other is variable optimization. The former is an improvement on the existing algorithm in a special case. The latter is realized by means of the maximal independent point set in graph theory. We apply this new method in integer factorization on quantum annealers and achieve the largest integer factorization (4137131) with 93 variables, the range of coefficients is [-1024,1024] which is much smaller than the previous results. We also focus on the quantum attacks on block ciphers and present an efficient method with smaller coefficients to transform Boolean equation systems into QUBO problems.

arXiv:2211.10076•Nov 18, 2022•0 citations

An initial step toward a quantum annealing approach to the discrete logarithm problem

Anuradha Mahasinghe, Youvin Jayasinghe

Abstract The discrete logarithm problem over a multiplicative group of integer modulo n is the key ingredient in the ElGamal encryption system. This problem has been proven to be tractable in polynomial time on a quantum computer by Shor's algorithm. This algorithm makes use of basic quantum gates, circuits, measurements and it has been experimented in the circuit‐gate framework of quantum computing. On the other hand, the adiabatic framework of quantum computing with the quantum annealers such as the D‐Wave machine that simulates the adiabatic process has become very popular, showing its potential for making a practical pathway to achieve quantum speedup. Furthermore, much progress has been reported recently on the tractability of the integer factoring problem, which is the other widely‐used encryption method, on quantum annealers. In this context, it is important to explore the tractability of the discrete logarithm problem too using quantum annealers. In this work we present a first step made in this direction, by converting the discrete logarithm problem over a multiplicative group into the problem of minimizing a binary quadratic form, a standard problem format acceptable to a quantum annealer. Our formulation was tested for small‐scale problem instances using the quantum‐classical hybrid platform PyQUBO and we discuss the computational challenges and propose several potential improvements to the formulation.

Security and Privacy•Apr 8, 2022•3 citations

A First Successful Factorization of RSA-2048 Integer by D-Wave Quantum Computer

Chao Wang, Jingjing Yu, Zhi Pei +2 more

Integer factorization, the core of the Rivest-Shamir-Adleman (RSA) attack, is an exciting but formidable challenge. As of this year, a group of researchers' latest quantum supremacy chip remains unavailable for cryptanalysis. Quantum annealing (QA) has a unique quantum tunneling advantage, which can escape local extremum in the exponential solution space, finding the global optimal solution with a higher probability. Consequently, we consider it an effective method for attacking cryptography. According to Origin Quantum Computing, QA computers are able to factor numbers several orders of magnitude larger than universal quantum computers. We try to transform the integer factorization problem in RSA attacks into a combinatorial optimization problem by using the QA algorithm of D-Wave quantum computer, and attack RSA-2048 which is composed of a class of special integers. The experiment factored this class of integers of size 22048,$N=p\times q$As an example, the article gives the results of 10 RSA-2048 attacks in the appendix. This marks the first successful factorization of RSA-2048 by D-Wave quantum computer, regardless of employing mathematical or quantum techniques, despite dealing with special integers, exceeding 21061−1 of California State University. This experiment verifies that the QA algorithm based on D-Wave is an effective method to attack RSA.

Tsinghua Science & Technology•Dec 30, 2024•9 citations

Quantum Attacks on Modern Cryptography and Post-Quantum Cryptosystems

Zachary Marron

Cryptography is a critical technology in the modern computing industry, but the security of many cryptosystems relies on the difficulty of mathematical problems such as integer factorization and discrete logarithms. Large quantum computers can solve these problems efficiently, enabling the effective cryptanalysis of many common cryptosystems using such algorithms as Shor’s and Grover’s. If data integrity and security are to be preserved in the future, the algorithms that are vulnerable to quantum cryptanalytic techniques must be phased out in favor of quantum-proof cryptosystems. While quantum computer technology is still developing and is not yet capable of breaking commercial encryption, these steps can be taken immediately to ensure that the impending development of large quantum computers does not compromise sensitive data.

•Jan 1, 2018•0 citations

Quantum-Based Cryptanalysis Algorithms

Jincheng Zhang

This paper explores the potential of quantum computing to revolutionize cryptanalysis. It proposes a novel algorithm leveraging the principles of quantum computation, specifically utilizing variants of Shor's algorithm, to analyze and ultimately break currently prevalent cryptographic systems. The core claim centers on the disruptive capability of quantum computation, potentially rendering existing encryption methods obsolete. The algorithm is designed to exploit the exponential speedup offered by quantum computers in solving specific mathematical problems, such as integer factorization and discrete logarithms, which are the foundations of many widely used encryption schemes, including RSA and ECC. This work outlines the theoretical framework, detailing the mathematical underpinnings of the proposed analysis and highlighting the significant implications for cybersecurity. The focus remains on the algorithmic design and theoretical considerations, omitting experimental validation due to the current limitations of quantum computing hardware.

•Aug 29, 2026•0 citations

Factoring semi-primes with (quantum) SAT-solvers

Michele Mosca, Sebastian R. Verschoor

The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor's quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor's algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware.

arXiv:1902.01448•Scientific Reports•May 14, 2022•17 citations
This work focuses on quantum methods for cryptanalysis of schemes based on the integer factorization problem and the discrete logarithm problem. We demonstrate how to practically solve the largest instances of the factorization problem by improving an approach that combines quantum and classical computations, assuming the use of the best publicly available special-class quantum computer: the quantum annealer. We achieve new computational experiment results by solving the largest instance of the factorization problem ever announced as solved using quantum annealing, with a size of 29 bits. The core idea of the improved approach is to leverage known subexponential classical method to break the problem down into many smaller computations and perform the most critical ones on a quantum computer. This approach does not reduce the complexity class, but it assesses the pragmatic capabilities of an attacker. It also marks a step forward in the development of hybrid methods, which in practice may surpass classical methods in terms of efficiency sooner than purely quantum computations will.
This paper presents a new method to reduce the optimization of a pseudo-Boolean function to QUBO problem which can be solved by quantum annealer. The new method has two aspects, one is coefficient optimization and the other is variable optimization. The former is an improvement on the existing algorithm in a special case. The latter is realized by means of the maximal independent point set in graph theory. We apply this new method in integer factorization on quantum annealers and achieve the largest integer factorization (4137131) with 93 variables, the range of coefficients is [-1024,1024] which is much smaller than the previous results. We also focus on the quantum attacks on block ciphers and present an efficient method with smaller coefficients to transform Boolean equation systems into QUBO problems.
Abstract The discrete logarithm problem over a multiplicative group of integer modulo n is the key ingredient in the ElGamal encryption system. This problem has been proven to be tractable in polynomial time on a quantum computer by Shor's algorithm. This algorithm makes use of basic quantum gates, circuits, measurements and it has been experimented in the circuit‐gate framework of quantum computing. On the other hand, the adiabatic framework of quantum computing with the quantum annealers such as the D‐Wave machine that simulates the adiabatic process has become very popular, showing its potential for making a practical pathway to achieve quantum speedup. Furthermore, much progress has been reported recently on the tractability of the integer factoring problem, which is the other widely‐used encryption method, on quantum annealers. In this context, it is important to explore the tractability of the discrete logarithm problem too using quantum annealers. In this work we present a first step made in this direction, by converting the discrete logarithm problem over a multiplicative group into the problem of minimizing a binary quadratic form, a standard problem format acceptable to a quantum annealer. Our formulation was tested for small‐scale problem instances using the quantum‐classical hybrid platform PyQUBO and we discuss the computational challenges and propose several potential improvements to the formulation.
Integer factorization, the core of the Rivest-Shamir-Adleman (RSA) attack, is an exciting but formidable challenge. As of this year, a group of researchers' latest quantum supremacy chip remains unavailable for cryptanalysis. Quantum annealing (QA) has a unique quantum tunneling advantage, which can escape local extremum in the exponential solution space, finding the global optimal solution with a higher probability. Consequently, we consider it an effective method for attacking cryptography. According to Origin Quantum Computing, QA computers are able to factor numbers several orders of magnitude larger than universal quantum computers. We try to transform the integer factorization problem in RSA attacks into a combinatorial optimization problem by using the QA algorithm of D-Wave quantum computer, and attack RSA-2048 which is composed of a class of special integers. The experiment factored this class of integers of size 22048,N=p×qN=p\times qN=p×qAs an example, the article gives the results of 10 RSA-2048 attacks in the appendix. This marks the first successful factorization of RSA-2048 by D-Wave quantum computer, regardless of employing mathematical or quantum techniques, despite dealing with special integers, exceeding 21061−1 of California State University. This experiment verifies that the QA algorithm based on D-Wave is an effective method to attack RSA.
Cryptography is a critical technology in the modern computing industry, but the security of many cryptosystems relies on the difficulty of mathematical problems such as integer factorization and discrete logarithms. Large quantum computers can solve these problems efficiently, enabling the effective cryptanalysis of many common cryptosystems using such algorithms as Shor’s and Grover’s. If data integrity and security are to be preserved in the future, the algorithms that are vulnerable to quantum cryptanalytic techniques must be phased out in favor of quantum-proof cryptosystems. While quantum computer technology is still developing and is not yet capable of breaking commercial encryption, these steps can be taken immediately to ensure that the impending development of large quantum computers does not compromise sensitive data.
This paper explores the potential of quantum computing to revolutionize cryptanalysis. It proposes a novel algorithm leveraging the principles of quantum computation, specifically utilizing variants of Shor's algorithm, to analyze and ultimately break currently prevalent cryptographic systems. The core claim centers on the disruptive capability of quantum computation, potentially rendering existing encryption methods obsolete. The algorithm is designed to exploit the exponential speedup offered by quantum computers in solving specific mathematical problems, such as integer factorization and discrete logarithms, which are the foundations of many widely used encryption schemes, including RSA and ECC. This work outlines the theoretical framework, detailing the mathematical underpinnings of the proposed analysis and highlighting the significant implications for cybersecurity. The focus remains on the algorithmic design and theoretical considerations, omitting experimental validation due to the current limitations of quantum computing hardware.
The computational difficulty of factoring large integers forms the basis of security for RSA public-key cryptography. The best-known factoring algorithms for classical computers run in sub-exponential time. The integer factorization problem can be reduced to the Boolean Satisfiability problem (SAT). While this reduction has proved to be useful for studying SAT solvers, large integers have not been factored via such a reduction. Shor's quantum factoring algorithm factors integers in expected polynomial time. Large-scale fault-tolerant quantum computers capable of implementing Shor's algorithm are not yet available, preventing relevant benchmarking experiments. Recently, several authors have attempted quantum factorizations via reductions to SAT or similar NP-hard problems. While this approach may shed light on algorithmic approaches for quantum solutions to NP-hard problems, in this paper we study and question its practicality. We find no evidence that this is a viable path toward factoring large numbers, even for scalable fault-tolerant quantum computers, as well as for various quantum annealing or other special purpose quantum hardware.