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

International Conference on Signal Image Processing and Communication (ICSIPC)

Complexity Analysis of QUBO-Based Large Number Factorization Algorithm

Yifan Yuan, Pingjing Lu, Yiwei Gao, 陶向军, Zhang Luo

Published Apr 24, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1109/icsipc69751.2026.11584167

Related papers

General integer factorization algorithm based on Ising machine

Zhang Luo, Yifan Yuan, Zhicheng Wang +2 more

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.

EPJ Quantum Technology•Nov 21, 2025•3 citations

Quantum prime factorization algorithms using binary carry propagation

Ryou, Arim, Kim, Kiwoong, Jun, Kyungtaek

The RSA cryptosystem, which relies on the computational difficulty of prime factorization, faces growing challenges with the advancement of quantum computing. In this study, we propose a quantum annealing based approach to integer factorization using both high order unconstrained binary optimization (HUBO) and constrained quadratic model (CQM) formulations. We begin by modeling binary multiplication with explicit carry propagation, translating this into a HUBO representation and subsequently reducing it to a quadratic unconstrained binary optimization form compatible with current quantum solvers. To address scalability limitations, we implement a CQM approach with constraint relaxation and global product consistency. While the HUBO model successfully factors small semiprimes, it exhibits exponential memory growth, making it impractical for inputs larger than 10 bits. In contrast, the CQM model achieves accurate factorization of semiprimes up to 60 bits including N = 1152921423002469787 demonstrating significantly improved scalability. Experimental results further show that applying global product constraints enhances factorization accuracy and consistency across all tested instances. This work highlights both the promise and current limitations of quantum-assisted factorization and establishes a foundation for evaluating RSA security in the emerging quantum era.

arXiv:2506.16799•Jun 20, 2025•1 citation

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo Carro, Juan Marcos Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

•May 27, 2025•0 citations

Perspectives on Cryptographically Relevant Quantum Computing: Integer Factoring, Discrete Logarithm Problems

C. E. Veni Madhavan

We present our perspectives on the current status of, integer factoring and discrete logarithm, algorithms underlying the strength of classical public-key cryptography protocols used in key-exchange, encryption and digital signatures. We present an expository overview of the algebraic, number-theoretic and algorithmic principles behind the canonical, powerful algorithms used in the factoring of large, composite RSA modulii. These cover the two main ideas of group order based methods, and quadratic congruence based methods. We provide the resource estimates for the record breaking factoring based on the general number field sieve. Next we present an overview of the algorithmic theory of quantum computation behind, the polynomial time Shor's quantum algorithm for, period finding in hidden subgroup structure problems. This algorithm has played a key role in advancing post-quantum cryptography, and also in the exciting, contemporary developments in quantum computing, networking, sensing, and materials science as a whole. Latest advances in quantum computing rest on a variety of physics, engineering, algorithms, compilation, hardware, software techniques. There are several tradeoffs based on number of qubits, coherence times, control issues, errors and fault tolerance. In this environment, nuances of mathematical ideas, behind every step of the intricate arithmetical and algebraic computations under quantum models plays a significant role. We provide an overview of some of the recent ideas behind such algorithms. We conclude with a recent deep question on the ultimate feasibility of ultra large-scale, error-free, discrete, quantum computations required typically in cryptanalysis.

Galois Journal of Algebra•Oct 30, 2026•0 citations

Prime Factorization Using Partially Constrained Multiple Quantum Annealing With Analytical and Pattern-Based Variable Reduction

Xinyi Guo, Geguang Miao, Shinichi Nishizawa +2 more

Factorization of large semiprimes remains one of the most challenging problems for classical computers. Shor’s algorithm offers a quantum approach that reduces computational complexity, but its practical application is currently limited by hardware constraints. Meanwhile, as a provisional approach, quantum annealing (QA) has been explored through formulations of the quadratic unconstrained binary optimization (QUBO) problem. Among existing methods, the blockwise partial-product approach effectively reduced the QUBO variable count but was limited to semiprimes up to 21 bits. To extend factorization to larger semiprimes, this paper addresses key engineering challenges in constructing efficient QUBO formulations for prime factorization. We propose five techniques to reduce variable counts and improve scalability with current QA hardware: (1) dividing the problem into subproblems with partial constraints; (2) applying analytical reductions near the LSB; (3) applying analytical reductions near the MSB; (4) exploiting special patterns in semiprimes, with odd bit widths and long MSB-side zero sequences; and (5) balancing variable usage across both sides of the subproblem. Integrated into a QUBO converter, these methods enable stable factorization of semiprimes up to 47-bits within 20 seconds and can extend to special 2049-bit instances with 1001 consecutive MSB-side zeros.

IEEE Transactions on Computers•Jan 15, 2026•0 citations

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo, Juan Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

International Conference on Agents and Artificial Intelligence (ICAART)•Jan 1, 2026•1 citation
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.
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 RSA cryptosystem, which relies on the computational difficulty of prime factorization, faces growing challenges with the advancement of quantum computing. In this study, we propose a quantum annealing based approach to integer factorization using both high order unconstrained binary optimization (HUBO) and constrained quadratic model (CQM) formulations. We begin by modeling binary multiplication with explicit carry propagation, translating this into a HUBO representation and subsequently reducing it to a quadratic unconstrained binary optimization form compatible with current quantum solvers. To address scalability limitations, we implement a CQM approach with constraint relaxation and global product consistency. While the HUBO model successfully factors small semiprimes, it exhibits exponential memory growth, making it impractical for inputs larger than 10 bits. In contrast, the CQM model achieves accurate factorization of semiprimes up to 60 bits including N = 1152921423002469787 demonstrating significantly improved scalability. Experimental results further show that applying global product constraints enhances factorization accuracy and consistency across all tested instances. This work highlights both the promise and current limitations of quantum-assisted factorization and establishes a foundation for evaluating RSA security in the emerging quantum era.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
We present our perspectives on the current status of, integer factoring and discrete logarithm, algorithms underlying the strength of classical public-key cryptography protocols used in key-exchange, encryption and digital signatures. We present an expository overview of the algebraic, number-theoretic and algorithmic principles behind the canonical, powerful algorithms used in the factoring of large, composite RSA modulii. These cover the two main ideas of group order based methods, and quadratic congruence based methods. We provide the resource estimates for the record breaking factoring based on the general number field sieve. Next we present an overview of the algorithmic theory of quantum computation behind, the polynomial time Shor's quantum algorithm for, period finding in hidden subgroup structure problems. This algorithm has played a key role in advancing post-quantum cryptography, and also in the exciting, contemporary developments in quantum computing, networking, sensing, and materials science as a whole. Latest advances in quantum computing rest on a variety of physics, engineering, algorithms, compilation, hardware, software techniques. There are several tradeoffs based on number of qubits, coherence times, control issues, errors and fault tolerance. In this environment, nuances of mathematical ideas, behind every step of the intricate arithmetical and algebraic computations under quantum models plays a significant role. We provide an overview of some of the recent ideas behind such algorithms. We conclude with a recent deep question on the ultimate feasibility of ultra large-scale, error-free, discrete, quantum computations required typically in cryptanalysis.
Factorization of large semiprimes remains one of the most challenging problems for classical computers. Shor’s algorithm offers a quantum approach that reduces computational complexity, but its practical application is currently limited by hardware constraints. Meanwhile, as a provisional approach, quantum annealing (QA) has been explored through formulations of the quadratic unconstrained binary optimization (QUBO) problem. Among existing methods, the blockwise partial-product approach effectively reduced the QUBO variable count but was limited to semiprimes up to 21 bits. To extend factorization to larger semiprimes, this paper addresses key engineering challenges in constructing efficient QUBO formulations for prime factorization. We propose five techniques to reduce variable counts and improve scalability with current QA hardware: (1) dividing the problem into subproblems with partial constraints; (2) applying analytical reductions near the LSB; (3) applying analytical reductions near the MSB; (4) exploiting special patterns in semiprimes, with odd bit widths and long MSB-side zero sequences; and (5) balancing variable usage across both sides of the subproblem. Integrated into a QUBO converter, these methods enable stable factorization of semiprimes up to 47-bits within 20 seconds and can extend to special 2049-bit instances with 1001 consecutive MSB-side zeros.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.