This paper provides a new (second) way, which is completely different from Shor's algorithm, to show the optimistic potential of a D-Wave quantum computer for deciphering RSA and successfully factoring all integers within 10000. Our method significantly reduced the local field coefficient [Formula: see text] and coupling term coefficient [Formula: see text] by more than 33% and 26%, respectively, of those of Ising model, which can further improve the stability of qubit chains and improve the upper bound of integer factorization. In addition, our results obtained the best index (20-bit integer (1028171)) of quantum computing for deciphering RSA via the quantum computing software environment provided by D-Wave. Furthermore, Shor's algorithm requires approximately 40 qubits to factor the integer 1028171, which is far beyond the capacity of universal quantum computers. Thus, post quantum cryptography should further consider the potential of the D-Wave quantum computer for deciphering the RSA cryptosystem in future.
This paper provides a new (second) way, which is completely different from Shor's algorithm, to show the optimistic potential of a D-Wave quantum computer for deciphering RSA and successfully factoring all integers within 10000. Our method significantly reduced the local field coefficient [Formula: see text] and coupling term coefficient [Formula: see text] by more than 33% and 26%, respectively, of those of Ising model, which can further improve the stability of qubit chains and improve the upper bound of integer factorization. In addition, our results obtained the best index (20-bit integer (1028171)) of quantum computing for deciphering RSA via the quantum computing software environment provided by D-Wave. Furthermore, Shor's algorithm requires approximately 40 qubits to factor the integer 1028171, which is far beyond the capacity of universal quantum computers. Thus, post quantum cryptography should further consider the potential of the D-Wave quantum computer for deciphering the RSA cryptosystem in future.
This work is the first to determine that a real quantum computer (including generalized and specialized) can decipher million-scale RSA relying solely on quantum algorithms, showing the real attack potential of D-Wave machines. The influence of different column widths on RSA factorization results is studied on the basis of a multiplication table, and the optimal column method is determined by traversal experiments. The traversal experiment of integer factorization within 10 000 shows that the local field and coupling coefficients are 75%-93% lower than the research of Shanghai University in 2020 and more than 85% lower than that of Purdue University in 2018. Extremely low Ising model parameters are crucial to reducing the hardware requirements, prompting factoring 1 245 407 on the D-Wave 2000Q real machine. D-Wave advantage already has more than 5000 qubits and will be expanded to 7000 qubits during 2023–2024, with remarkable improvements in decoherence and topology. This machine is expected to promote the solution of large-scale combinatorial optimization problems. One of the contributions of this paper is the discussion of the long-term impact of D-Wave on the development of post-quantum cryptography standards.
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.
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.
Integer factorization, a fundamental problem in computational mathematics, holds critical significance for modern cryptography, particularly in RSA encryption. Traditional approaches such as the number field sieve face exponential complexity limitations, while Shor’s quantum algorithm remains impractical due to hardware constraints. This study proposes a universal algorithm for integer factorization based on Ising machines by transforming the problem into a Quadratic Unconstrained Binary Optimization (QUBO) formulation. The algorithm introduces an optimal reduction formula to optimize the parameter ranges of local field coefficients ( h ) and coupling coefficients ( J ) in the Ising model. Additionally, a non-uniform column grouping method is employed to resolve the conflict between coefficient ranges and carry auxiliary quantum bits(qubits), minimizing the number of auxiliary qubits with minimal compromise on coefficient ranges. Using this approach, we successfully factorized the 22-bit integer 2,093,809 with only 118 qubits. Extrapolating to existing photonic Ising machines with 100,000 qubits, our method demonstrates the potential to factorize 631-bit integers, highlighting its promise for efficient large-scale integer factorization. All results presented in this paper are obtained from simulations on Fixstars Amplify and D-Wave simulators.
The security of the RSA cryptosystem is based on the difficulty of factoring a large number N into prime numbers [Formula: see text] and [Formula: see text] satisfying [Formula: see text]. This paper presents a prime factorization method using a D-Wave quantum computer that could threaten the RSA cryptosystem in the future. The starting point for this method is very simple, representing two prime numbers as qubits. Then, we set the difference between the product of the two prime numbers expressed in qubits and N as a cost function, and we find the solution when the cost function is minimized. D-Wave's quantum annealer can find the minimum value of any quadratic problem. However, the cost function must be a higher-order unconstrained optimization (HUBO) model because it contains second- or higher-order terms. We used a hybrid solver accessible via Leap, D-Wave's real-time quantum cloud service, and the dimod package provided by the D-Wave Ocean software development kit (SDK) to solve the HUBO problem. We also successfully factorized 102,454,763 with 26 logical qubits. In addition, we factorized 1,000,070,001,221 using the range-dependent Hamiltonian algorithm.
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.