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

EPJ Quantum Technology

General integer factorization algorithm based on Ising machine

Zhang Luo, Yifan Yuan, Zhicheng Wang, Mingche Lai, Pingjing Lu

Published Nov 21, 2025• 3 citations
Publisher

Abstract

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.

DOI
10.1140/epjqt/s40507-025-00449-9

Related papers

Complexity Analysis of QUBO-Based Large Number Factorization Algorithm

Yifan Yuan, Pingjing Lu, Yiwei Gao +2 more

The integer factorization problem constitutes a fundamental mathematical cornerstone of modern public-key cryptography, with its inherent computational asymmetry directly underpinning the security of encryption protocols such as RSA. In recent years, propelled by advances in Ising machines and quantum annealing hardware, factorization methods based on Quadratic Unconstrained Binary Optimization (QUBO) models have emerged as a promising alternative research trajectory. This paper presents a systematic complexity analysis of QUBO-based integer factorization algorithms, establishing rigorous theoretical bounds on their computational resource requirements through formal mathematical derivation. Our results indicate that the preprocessing time complexity scales as$O\left(m_{N}^{3}\right)$, which remains within the realm of classical computational feasibility. In contrast, the space complexity scales as$O\left(m_{N}^{2}\right)$. Without altering the binary multiplication table-based modeling approach, this space complexity is constrained to be at least quadratic. Consequently, the physical resource demands imposed by the spatial complexity far exceed the capabilities of current and near-term annealing hardware. Hence, while the temporal overhead does not present a fundamental impediment, the spatial constraints render a generalpurpose QUBO-based attack against RSA-2048 physically unrealizable in the short term.

International Conference on Signal Image Processing and Communication (ICSIPC)•Apr 24, 2026•0 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

Prime factorization algorithm based on parameter optimization of Ising model

Baonan Wang, Feng Hu, Haonan Yao +1 more

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.

Scientific Reports•Apr 28, 2020•74 citations

Integer factorization via spatial photonic Ising machine using a lattice sieve method

Jie Yang, Wenjia Zhang, Junjie Yu +2 more

Integer factorization, a cryptographic cornerstone, remains exponentially hard for classical computers, while quantum approaches, though theoretically polynomial-time, still face hardware limitations. We propose an Ising-accelerated lattice sieve method using a photonic Ising machine to solve the NP-hard closest vector problem efficiently. Our approach requires only sub-linear growth in spin number and stable dynamic range of the interaction matrix as integer bit-length increases, minimizing hardware demands. We construct a programmable spatial photonic Ising machine based on a Dammann grating. Through multi-path simulated annealing experiments on the constructed SPIM, we experimentally achieved the complete factorization of a 32-bit integer and demonstrated the identification of multiple distinct smooth relation pairs required for factorizing a 100-bit integer. To further validate the generality and scalability of the proposed method, we performed classical computer simulations of the multi-path annealing process, achieving factorization of integers up to 120 bits and establishing a benchmark for lattice sieve-based factorization.

Optics Express•Jun 22, 2026•0 citations

Deciphering a Million-Plus RSA Integer with Ultralow Local Field Coefficient h and Coupling Coefficient J of the Ising Model by D-Wave 2000Q

Chao Wang, Qiaoyun Hu, Haonan Yao +2 more

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.

Tsinghua Science & Technology•Dec 4, 2023•5 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
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 integer factorization problem constitutes a fundamental mathematical cornerstone of modern public-key cryptography, with its inherent computational asymmetry directly underpinning the security of encryption protocols such as RSA. In recent years, propelled by advances in Ising machines and quantum annealing hardware, factorization methods based on Quadratic Unconstrained Binary Optimization (QUBO) models have emerged as a promising alternative research trajectory. This paper presents a systematic complexity analysis of QUBO-based integer factorization algorithms, establishing rigorous theoretical bounds on their computational resource requirements through formal mathematical derivation. Our results indicate that the preprocessing time complexity scales asO(mN3)O\left(m_{N}^{3}\right)O(mN3​), which remains within the realm of classical computational feasibility. In contrast, the space complexity scales asO(mN2)O\left(m_{N}^{2}\right)O(mN2​). Without altering the binary multiplication table-based modeling approach, this space complexity is constrained to be at least quadratic. Consequently, the physical resource demands imposed by the spatial complexity far exceed the capabilities of current and near-term annealing hardware. Hence, while the temporal overhead does not present a fundamental impediment, the spatial constraints render a generalpurpose QUBO-based attack against RSA-2048 physically unrealizable in the short term.
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.
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.
Integer factorization, a cryptographic cornerstone, remains exponentially hard for classical computers, while quantum approaches, though theoretically polynomial-time, still face hardware limitations. We propose an Ising-accelerated lattice sieve method using a photonic Ising machine to solve the NP-hard closest vector problem efficiently. Our approach requires only sub-linear growth in spin number and stable dynamic range of the interaction matrix as integer bit-length increases, minimizing hardware demands. We construct a programmable spatial photonic Ising machine based on a Dammann grating. Through multi-path simulated annealing experiments on the constructed SPIM, we experimentally achieved the complete factorization of a 32-bit integer and demonstrated the identification of multiple distinct smooth relation pairs required for factorizing a 100-bit integer. To further validate the generality and scalability of the proposed method, we performed classical computer simulations of the multi-path annealing process, achieving factorization of integers up to 120 bits and establishing a benchmark for lattice sieve-based factorization.
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.
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.