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

Journal of quantum computing

Effects of T-Factor on Quantum Annealing Algorithms for Integer Factoring Problem

Zhiqi Liu, Shihui Zheng, Xingyu Yan, Pan Ping, Licheng Wang

Published Jan 1, 2023• 0 citations
Publisher

Abstract

The hardness of the integer factoring problem (IFP) plays a core role in the security of RSA-like cryptosystems that are widely used today. Besides Shor’s quantum algorithm that can solve IFP within polynomial time, quantum annealing algorithms (QAA) also manifest certain advantages in factoring integers. In experimental aspects, the reported integers that were successfully factored by using the D-wave QAA platform are much larger than those being factored by using Shor-like quantum algorithms. In this paper, we report some interesting observations about the effects of QAA for solving IFP. More specifically, we introduce a metric, called T-factor that measures the density of occupied qubits to some extent when conducting IFP tasks by using D-wave. We find that T-factor has obvious effects on annealing times for IFP: The larger of T-factor, the quicker of annealing speed. The explanation of this phenomenon is also given.

DOI
10.32604/jqc.2023.045572

Related papers

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

Breaking RSA Security With A Low Noise D-Wave 2000Q Quantum Annealer: Computational Times, Limitations And Prospects

Riccardo Mengoni, Daniele Ottaviani, Paolino Iorio

The RSA cryptosystem could be easily broken with large scale general purpose quantum computers running Shor's factorization algorithm. Being such devices still in their infancy, a quantum annealing approach to integer factorization has recently gained attention. In this work, we analyzed the most promising strategies for RSA hacking via quantum annealing with an extensive study of the low noise D-Wave 2000Q computational times, current hardware limitations and challenges for future developments.

arXiv:2005.02268•May 5, 2020•7 citations

Quantum annealing distributed integer decomposition study of local field coefficient h and coupling coefficient J with stability Ising model

Chao Wang, Haonan Yao, BaoNan WANG +1 more

The difficulty in factoring large integers is a security basis of Rivest-Shamir-Adleman public key cryptography. Quantum annealing, a completely different method as compared with that of Shor’s algorithm, can transform an integer factorization problem into a combinatorial optimization problem using the quantum tunneling effects of D-wave quantum annealing to leap from local minima. In this paper, a new distributed integer factorization algorithm based on quantum annealing, which transforms an arbitrary integer into a stable Ising model executable using a D-wave quantum computer, is proposed. The stability and range of the local field coefficient h and the coupling term coefficient J of the Ising model are important factors that affect the success rate of integer factorization. Compared with the algorithm of Purdue University’s Jiang et al., the proposed method reduces the number of logical bits and the parameters of h and J by more than 60% and 40%, respectively, and the ranges of the coefficients of the Ising model are stable. Compared with the algorithm of Lockheed Martin Warren, the parameters of the proposed method are reduced in the orders from 106 to 102 of magnitude when the Ising model is guaranteed to be stable. In addition, to prove the correctness of the algorithm, Warren traversed factorization within 1000 integers. The proposed method traverses all integers within 10000 and all of them are successfully factored. The experimental results of this paper exceed the results of Shor’s algorithm, Jiang’s algorithm and the maximum published factorization scale of Lockheed Martin Warren’s algorithm.

Zhongguo kexue. Wulixue Lixue Tianwenxue•Jan 21, 2020•3 citations

RSA Prime Factorization on IBM Qiskit

Matthew Evans Audric Rengkung, Arya Wicaksana

The advancement of quantum computing in recent years poses severe threats to the RSA public-key cryptosystem. The RSA cryptosystem fundamentally relies its security on the computational hardness of number theory problems: prime factorization (integer factoring). Shor’s quantum factoring algorithm could theoretically answer the computational problem in polynomial time. This paper contributes to the experiment and demonstration of Shor’s quantum factoring algorithm for RSA prime factorization using IBM Qiskit. The performance of the quantum program is evaluated based on user time and the success probability. The results show that a more significant public modulus N in the RSA public key improves factorization’s computational hardness, requiring more quantum bits to solve. A further enhancement on implementing Shor’s oracle function is essential in increasing success probability and reducing the number of shots required.

Journal of Internet Services and Information Security•May 30, 2023•8 citations

Quantum Shor's Algorithm vs. Classical General Number Field Sieve (GNFS) Approach for Large Integer Factorization

S. S. Kavitha, Narasimha Kaulgud, B. Sharmila +3 more

Quantum integer factorization is a groundbreaking field that explores the use of quantum algorithms, notably Shor's algorithm, to efficiently factorize large integers into their prime components. Its potential implications on modern encryption techniques, such as the Rivest-Shamir-Adleman (RSA) algorithm, are of considerable interest. This paper's central aim is to contrast the computational time and implementation of the Integer Factorization Problem (IFP) between classical and quantum computers. The inner workings of Quantum Shor's algorithm are broken down step by step, and the estimated processing time is contrasted with the classical General Number Field Sieve (GNFS) approach. Given the exponential speedup provided by quantum computing, this comparison helps assess Shor's algorithm's possible advantage over GNFS in factoring large numbers. Direct comparisons with GNFS are currently difficult due to Shor's algorithm's reliance on large-scale quantum computer development for practical execution speeds. This paper focuses on solving integer factorization up to$2^{n}$bits.

International Conference on Next Generation Communication & Information Processing (INCIP)•Jan 23, 2025•1 citation

Research on Quantum Annealing Integer Factorization Based on Different Columns

Baonan Wang, Xiaoting Yang, Dan Zhang

The majority of scholars believe that Shor’s algorithm is a unique and powerful quantum algorithm for RSA cryptanalysis, so current postquantum cryptography research has largely considered only the potential threats of Shor’s algorithm. This paper verifies the feasibility of deciphering RSA public key cryptography based on D-Wave, which is the second most effective RSA attack method after Shor’s algorithm. This paper proposes the influence of different column methods on the final integer factorization, puts forward a new dimension reduction formula, simplifies the integer factorization model based on quantum annealing, simulates it with the qbsolv quantum computing software environment provided by D-Wave, and factors the integer 1630729 (an 11-bit prime factor multiplied by an 11-bit prime factor). The research results show that choosing an appropriate number of columns and column width in the binary integer factorization multiplication table is very important for studying the optimization ability of the quantum annealing algorithm. In fact, Science, Nature, IEEE Spectrum, and the National Academies of Sciences (NAS) are consistent in asserting that the practical application of general-purpose quantum computers is far in the future. Therefore, although D-Wave computers were initially mainly purchased by Lockheed Martin, Google, etc., for purposes such as image processing, machine learning, combinatorial optimization, and software verification, post quantum cryptography research should further consider the potential of the D-Wave quantum computer in deciphering RSA cryptosystems in the future, and a discussion of this potential is one of the contributions of this paper.

Frontiers in Physics•Jun 1, 2022•10 citations
The hardness of the integer factoring problem (IFP) plays a core role in the security of RSA-like cryptosystems that are widely used today. Besides Shor’s quantum algorithm that can solve IFP within polynomial time, quantum annealing algorithms (QAA) also manifest certain advantages in factoring integers. In experimental aspects, the reported integers that were successfully factored by using the D-wave QAA platform are much larger than those being factored by using Shor-like quantum algorithms. In this paper, we report some interesting observations about the effects of QAA for solving IFP. More specifically, we introduce a metric, called T-factor that measures the density of occupied qubits to some extent when conducting IFP tasks by using D-wave. We find that T-factor has obvious effects on annealing times for IFP: The larger of T-factor, the quicker of annealing speed. The explanation of this phenomenon is also given.
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.
The RSA cryptosystem could be easily broken with large scale general purpose quantum computers running Shor's factorization algorithm. Being such devices still in their infancy, a quantum annealing approach to integer factorization has recently gained attention. In this work, we analyzed the most promising strategies for RSA hacking via quantum annealing with an extensive study of the low noise D-Wave 2000Q computational times, current hardware limitations and challenges for future developments.
The difficulty in factoring large integers is a security basis of Rivest-Shamir-Adleman public key cryptography. Quantum annealing, a completely different method as compared with that of Shor’s algorithm, can transform an integer factorization problem into a combinatorial optimization problem using the quantum tunneling effects of D-wave quantum annealing to leap from local minima. In this paper, a new distributed integer factorization algorithm based on quantum annealing, which transforms an arbitrary integer into a stable Ising model executable using a D-wave quantum computer, is proposed. The stability and range of the local field coefficient h and the coupling term coefficient J of the Ising model are important factors that affect the success rate of integer factorization. Compared with the algorithm of Purdue University’s Jiang et al., the proposed method reduces the number of logical bits and the parameters of h and J by more than 60% and 40%, respectively, and the ranges of the coefficients of the Ising model are stable. Compared with the algorithm of Lockheed Martin Warren, the parameters of the proposed method are reduced in the orders from 106 to 102 of magnitude when the Ising model is guaranteed to be stable. In addition, to prove the correctness of the algorithm, Warren traversed factorization within 1000 integers. The proposed method traverses all integers within 10000 and all of them are successfully factored. The experimental results of this paper exceed the results of Shor’s algorithm, Jiang’s algorithm and the maximum published factorization scale of Lockheed Martin Warren’s algorithm.
The advancement of quantum computing in recent years poses severe threats to the RSA public-key cryptosystem. The RSA cryptosystem fundamentally relies its security on the computational hardness of number theory problems: prime factorization (integer factoring). Shor’s quantum factoring algorithm could theoretically answer the computational problem in polynomial time. This paper contributes to the experiment and demonstration of Shor’s quantum factoring algorithm for RSA prime factorization using IBM Qiskit. The performance of the quantum program is evaluated based on user time and the success probability. The results show that a more significant public modulus N in the RSA public key improves factorization’s computational hardness, requiring more quantum bits to solve. A further enhancement on implementing Shor’s oracle function is essential in increasing success probability and reducing the number of shots required.
Quantum integer factorization is a groundbreaking field that explores the use of quantum algorithms, notably Shor's algorithm, to efficiently factorize large integers into their prime components. Its potential implications on modern encryption techniques, such as the Rivest-Shamir-Adleman (RSA) algorithm, are of considerable interest. This paper's central aim is to contrast the computational time and implementation of the Integer Factorization Problem (IFP) between classical and quantum computers. The inner workings of Quantum Shor's algorithm are broken down step by step, and the estimated processing time is contrasted with the classical General Number Field Sieve (GNFS) approach. Given the exponential speedup provided by quantum computing, this comparison helps assess Shor's algorithm's possible advantage over GNFS in factoring large numbers. Direct comparisons with GNFS are currently difficult due to Shor's algorithm's reliance on large-scale quantum computer development for practical execution speeds. This paper focuses on solving integer factorization up to2n2^{n}2nbits.
The majority of scholars believe that Shor’s algorithm is a unique and powerful quantum algorithm for RSA cryptanalysis, so current postquantum cryptography research has largely considered only the potential threats of Shor’s algorithm. This paper verifies the feasibility of deciphering RSA public key cryptography based on D-Wave, which is the second most effective RSA attack method after Shor’s algorithm. This paper proposes the influence of different column methods on the final integer factorization, puts forward a new dimension reduction formula, simplifies the integer factorization model based on quantum annealing, simulates it with the qbsolv quantum computing software environment provided by D-Wave, and factors the integer 1630729 (an 11-bit prime factor multiplied by an 11-bit prime factor). The research results show that choosing an appropriate number of columns and column width in the binary integer factorization multiplication table is very important for studying the optimization ability of the quantum annealing algorithm. In fact, Science, Nature, IEEE Spectrum, and the National Academies of Sciences (NAS) are consistent in asserting that the practical application of general-purpose quantum computers is far in the future. Therefore, although D-Wave computers were initially mainly purchased by Lockheed Martin, Google, etc., for purposes such as image processing, machine learning, combinatorial optimization, and software verification, post quantum cryptography research should further consider the potential of the D-Wave quantum computer in deciphering RSA cryptosystems in the future, and a discussion of this potential is one of the contributions of this paper.