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.
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.
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.
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.
This document details the methodology and steps taken to convert Higher Order Unconstrained Binary Optimization (HUBO) models into Quadratic Unconstrained Binary Optimization (QUBO) models. The focus is primarily on prime factorization problems; a critical and computationally intensive task relevant in various domains including cryptography, optimization, and number theory. The conversion from Higher-Order Binary Optimization (HUBO) to Quadratic Unconstrained Binary Optimization (QUBO) models is crucial for harnessing the capabilities of advanced computing methodologies, particularly quantum computing and DYNEX neuromorphic computing. Quantum computing offers potential exponential speedups for specific problems through its intrinsic parallelism capabilities. Conversely, DYNEX neuromorphic computing enhances efficiency and accelerates the resolution of intricate, pattern-oriented tasks by simulating memristors in GPUs, employing a highly decentralized approach, via Blockchain technology. This transformation enables the exploitation of these cutting-edge computing paradigms to address complex optimization challenges effectively. Through detailed explanations, mathematical formulations, and algorithmic strategies, this document aims to provide a comprehensive guide to understanding and implementing the conversion process from HUBO to QUBO. It underscores the importance of such transformations in making prime factorization computationally feasible on both existing classical computers and emerging computing technologies.
Objective: to study the transformational potential of quantum annealing in solving the problem of simple factorization. Research method(s): the approach includes a comprehensive review of recent experimental breakthroughs and theoretical innovations. In particular, we analyze techniques such as surface code memory, HUBO and QUBO formulations, range-dependent Hamiltonian algorithms, modular locally structured embedding methods, and a modified multiplication table method random number. Research Output(s): the study evaluates the application of quantum annealing to factorization of primes, showing that advanced problem mapping techniques, such as the HUBO and QUBO formulations, significantly improve the efficiency of representing complex factorization problems on quantum hardware. Notably, the inclusion of surface code memory increases the stability of qubit states during annealing, reducing errors and improving computational accuracy It also demonstrates that Hamiltonian's range-dependent algorithms and modular, locally structured embedding methods help optimize qubit interaction, enabling a more accurate factorization process. A modified multiplication table method is presented, providing an optimized computational strategy, especially effective for large composite numbers. Preliminary experiments with random numbers confirm the theoretical conclusions, indicating that these integrated methods allow for better performance than traditional approaches. Taken together, the results highlight the potential of quantum annealing as a solid foundation for solving complex cryptographic problems and lay the foundation for future research into scalable quantum algorithms and hardware implementations. Scientific novelty: the work combines several advanced quantum annealing techniques for factorization of prime numbers, combining experimental innovations with theoretical developments to propose a new framework that improves the efficiency of cryptographic computing.
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 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.