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

GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization

Advith Desu, Aryan Namboodiri, Anil Prabhakar

Published Sep 14, 2026• 0 citations
Publisher

Abstract

Abstract The security of RSA rests on the hardness of factoring a semiprime N = PQ. We present an end-to-end pipeline that turns this into an optimization problem: factorization is mapped to a sparse Ising model whose lowest-energy spin configuration encodes the bits of P and Q. We solve this model on a single NVIDIA GH200 GPU using a graph-colored simulated annealer designed around the sparsity of the underlying coupling matrix. To maximize efficiency, we use graph coloring to let multiple spins update in parallel without breaking the energy bookkeeping along with optimal assignment of per spin energy calculation on the threads in the GPU to maximize efficiency. The annealer rarely lands exactly on the ground state but consistently gets close, and a guided post-processing search: wheel-sieve brute force, or Coppersmith’s lattice method closes the residual distance. The full pipeline reliably factors 128-bit semiprimes on a single GPU host.

DOI
10.21203/rs.3.rs-10379044/v1

Related papers

Binary optimization by momentum annealing

Takuya Okuyama, Tomohiro Sonobe, Ken‐ichi Kawarabayashi +1 more

One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.

Physical review. E•Jul 10, 2019•102 citations

GPU-Based Digital Annealing for Accelerating Large-Scale Combinatorial Optimization

Nistala Krishna Vamsi, Ashutosh Kumar Singh, A K Prabhakar

We present a GPU-based digital annealer (DA) implementation to efficiently solve large-scale combinatorial optimization problems mapped onto Ising spin models. Our implementation employs Metropolis-Hastings dynamics with simulated annealing on NVIDIA A-100 GPUs, achieving up to 40-fold speedup over sequential CPU implementations for 32,000 -spin problems and scaling to 65,025 spins. Comprehensive benchmarking on the standard maxcut “Gset” dataset reveals that our DA consistently outperforms the commercial Gurobi optimiser across most of density-topology classes, achieving superior solution quality (lower optimality gaps), computational efficiency ($2.4 \times$ to $40.8 \times$ speedup), and high success rates ($83.3 \%$ average, with perfect performance on sparse Erdős-Rényi and moderatedensity skewed graphs). For cryptographic bent function discovery, our DA successfully identifies solutions up to 12 variables within minutes, significantly outperforming D-Wave’s quantum annealer, which fails to report results beyond 4 variables due to hardware connectivity constraints.

Supercomputing India (SCI)•Dec 9, 2025•0 citations

A GPU-Based Ising Machine With a Multi-Spin-Flip Capability for Constrained Combinatorial Optimization

Satoru Jimbo, Tatsuhiko Shirai, Nozomu Togawa +2 more

Ising machines are domain-specific computers that solve combinatorial optimization problems (COPs). They utilize an Ising model to represent a COP and search for the optimal spin configuration of the Ising model to solve the COP. Most Ising machines are based on simulated annealing (SA) and update the spin configuration according to single-spin-flip Markov Chain Monte Carlo methods. However, supporting a multi-spin flip is important to enhance the search performance of SA-based Ising machines when constrained COPs are solved. In this paper, we extend the merge method, which was introduced to provide a multi-spin-flip capability for SA-based Ising machines, and formulate it as a series of matrix multiplications that can be executed on a graphics processing unit (GPU) efficiently. We then construct a GPU-based Ising machine that implements the GPU-oriented merge method together with an extended SA algorithm. We finally demonstrate its superiority over the state-of-the-art GPU-based Ising machine for quadratic knapsack problems.

IEEE Access•Jan 1, 2024•8 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

Integer factorization via tensor-network Schnorr's sieving

Marco Tesoro, Ilaria Siloi, Daniel Jaschke +2 more

Classical public-key cryptography standards rely on the Rivest-Shamir-Adleman (RSA) encryption protocol. The security of this protocol is based on the exponential computational complexity of the most efficient classical algorithms for factoring large semiprime numbers into their two prime components. Here, we address RSA factorization building on Schnorr's mathematical framework where factorization translates into a combinatorial optimization problem. We solve the optimization task via tensor network methods, a quantum-inspired classical numerical technique. This tensor network Schnorr's sieving algorithm displays numerical evidence of polynomial scaling of resources with the bit-length of the semiprime. We factorize RSA numbers up to 100 bits and assess how computational resources scale through numerical simulations up to 130 bits, encoding the optimization problem in quantum systems with up to 256 qubits. Only the high-order polynomial scaling of the required resources limits the factorization of larger numbers. Although these results do not currently undermine the security of the present communication infrastructure, they strongly highlight the urgency of implementing postquantum cryptography or quantum key distribution.

arXiv:2410.16355•Physical Review A•Jan 22, 2026•15 citations

Benchmark study of simulated quantum annealing and asynchronous parallel simulated annealing for quadratic unconstrained binary optimization-based semiprime factorization

Gianbiagio Curato, Manuel Ponzi, Edoardo Chiatello +1 more

Simulated quantum annealing (SQA) has been widely studied as a heuristic for solving hard optimization problems, including integer factorization formulated as a quadratic unconstrained binary optimization (QUBO) problem. In this work, we present a replication-oriented benchmark of annealing-based solvers applied to biprime factorization using the direct QUBO mapping. We perform a controlled comparison of SQA, implemented via path-integral Monte Carlo, simulated annealing (SA), and asynchronous parallel simulated annealing (A-PSA), evaluating their performance in terms of probability of success and time to solution. Here, A-PSA denotes a multistart strategy consisting of multiple independent SA trajectories with no inter-replica interactions. Solver and encoding parameters are systematically optimized using Bayesian optimization to ensure a fair and reproducible comparison. Our results reproduce previously reported performance trends: SQA outperforms conventional SA on the considered QUBO landscapes, while SQA and A-PSA can exhibit closely comparable performance in specific regimes, highlighting the importance of multistart baselines in annealing-based benchmarking. All simulations are performed on commodity multithreaded CPU hardware using open-source software, enabling straightforward reproducibility without reliance on specialized experimental platforms. As a reference benchmark, the largest semiprime successfully factorized in our study is 8 219 999 = 32 749 × 251 , matching results previously obtained using quantum annealing hardware.

APS Open Science•Jun 3, 2026•0 citations
Abstract The security of RSA rests on the hardness of factoring a semiprime N = PQ. We present an end-to-end pipeline that turns this into an optimization problem: factorization is mapped to a sparse Ising model whose lowest-energy spin configuration encodes the bits of P and Q. We solve this model on a single NVIDIA GH200 GPU using a graph-colored simulated annealer designed around the sparsity of the underlying coupling matrix. To maximize efficiency, we use graph coloring to let multiple spins update in parallel without breaking the energy bookkeeping along with optimal assignment of per spin energy calculation on the threads in the GPU to maximize efficiency. The annealer rarely lands exactly on the ground state but consistently gets close, and a guided post-processing search: wheel-sieve brute force, or Coppersmith’s lattice method closes the residual distance. The full pipeline reliably factors 128-bit semiprimes on a single GPU host.
One of the vital roles of computing is to solve large-scale combinatorial optimization problems in a short time. In recent years, methods have been proposed that map optimization problems to ones of searching for the ground state of an Ising model by using a stochastic process. Simulated annealing (SA) is a representative algorithm. However, it is inherently difficult to perform a parallel search. Here we propose an algorithm called momentum annealing (MA), which, unlike SA, updates all spins of fully connected Ising models simultaneously and can be implemented on GPUs that are widely used for scientific computing. MA running in parallel on GPUs is 250 times faster than SA running on a modern CPU at solving problems involving 100 000 spin Ising models.
We present a GPU-based digital annealer (DA) implementation to efficiently solve large-scale combinatorial optimization problems mapped onto Ising spin models. Our implementation employs Metropolis-Hastings dynamics with simulated annealing on NVIDIA A-100 GPUs, achieving up to 40-fold speedup over sequential CPU implementations for 32,000 -spin problems and scaling to 65,025 spins. Comprehensive benchmarking on the standard maxcut “Gset” dataset reveals that our DA consistently outperforms the commercial Gurobi optimiser across most of density-topology classes, achieving superior solution quality (lower optimality gaps), computational efficiency (2.4×2.4 \times2.4× to 40.8×40.8 \times40.8× speedup), and high success rates (83.3%83.3 \%83.3% average, with perfect performance on sparse Erdős-Rényi and moderatedensity skewed graphs). For cryptographic bent function discovery, our DA successfully identifies solutions up to 12 variables within minutes, significantly outperforming D-Wave’s quantum annealer, which fails to report results beyond 4 variables due to hardware connectivity constraints.
Ising machines are domain-specific computers that solve combinatorial optimization problems (COPs). They utilize an Ising model to represent a COP and search for the optimal spin configuration of the Ising model to solve the COP. Most Ising machines are based on simulated annealing (SA) and update the spin configuration according to single-spin-flip Markov Chain Monte Carlo methods. However, supporting a multi-spin flip is important to enhance the search performance of SA-based Ising machines when constrained COPs are solved. In this paper, we extend the merge method, which was introduced to provide a multi-spin-flip capability for SA-based Ising machines, and formulate it as a series of matrix multiplications that can be executed on a graphics processing unit (GPU) efficiently. We then construct a GPU-based Ising machine that implements the GPU-oriented merge method together with an extended SA algorithm. We finally demonstrate its superiority over the state-of-the-art GPU-based Ising machine for quadratic knapsack problems.
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.
Classical public-key cryptography standards rely on the Rivest-Shamir-Adleman (RSA) encryption protocol. The security of this protocol is based on the exponential computational complexity of the most efficient classical algorithms for factoring large semiprime numbers into their two prime components. Here, we address RSA factorization building on Schnorr's mathematical framework where factorization translates into a combinatorial optimization problem. We solve the optimization task via tensor network methods, a quantum-inspired classical numerical technique. This tensor network Schnorr's sieving algorithm displays numerical evidence of polynomial scaling of resources with the bit-length of the semiprime. We factorize RSA numbers up to 100 bits and assess how computational resources scale through numerical simulations up to 130 bits, encoding the optimization problem in quantum systems with up to 256 qubits. Only the high-order polynomial scaling of the required resources limits the factorization of larger numbers. Although these results do not currently undermine the security of the present communication infrastructure, they strongly highlight the urgency of implementing postquantum cryptography or quantum key distribution.
Simulated quantum annealing (SQA) has been widely studied as a heuristic for solving hard optimization problems, including integer factorization formulated as a quadratic unconstrained binary optimization (QUBO) problem. In this work, we present a replication-oriented benchmark of annealing-based solvers applied to biprime factorization using the direct QUBO mapping. We perform a controlled comparison of SQA, implemented via path-integral Monte Carlo, simulated annealing (SA), and asynchronous parallel simulated annealing (A-PSA), evaluating their performance in terms of probability of success and time to solution. Here, A-PSA denotes a multistart strategy consisting of multiple independent SA trajectories with no inter-replica interactions. Solver and encoding parameters are systematically optimized using Bayesian optimization to ensure a fair and reproducible comparison. Our results reproduce previously reported performance trends: SQA outperforms conventional SA on the considered QUBO landscapes, while SQA and A-PSA can exhibit closely comparable performance in specific regimes, highlighting the importance of multistart baselines in annealing-based benchmarking. All simulations are performed on commodity multithreaded CPU hardware using open-source software, enabling straightforward reproducibility without reliance on specialized experimental platforms. As a reference benchmark, the largest semiprime successfully factorized in our study is 8 219 999 = 32 749 × 251 , matching results previously obtained using quantum annealing hardware.