GPU-Accelerated Graph-Colored Simulated Annealing for Integer Factorization
Advith Desu, Aryan Namboodiri, Anil Prabhakar
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.