The quadratic sieve is a classic algorithm for breaking large numbers into their prime factors, and it matters for cryptography because the security of widely used encryption systems like RSA depends on factoring being hard. The algorithm is notoriously difficult to run efficiently on modern hardware because it jumps around in memory unpredictably, causes lots of branch mispredictions, and resists the kind of regular, parallel computation that processors love. Previous attempts to speed it up using graphics processing units (GPUs) only moved certain pieces of the algorithm to the GPU while leaving the rest on the CPU.
This work presents CUDA-MPQS, a version of the quadratic sieve where every single stage of the computation runs on the GPU, with the CPU doing little more than housekeeping. The result is a highly efficient implementation that keeps the GPU busy nearly all the time without the usual overhead of coordinating between the CPU and GPU. Using this system, the authors factored RSA-155, a well-known 512-bit challenge number whose factorization was considered a landmark when it was first accomplished in 1999 using a more powerful algorithm called the number field sieve. The new result is the largest number ever factored using the quadratic sieve specifically, requiring about 700 GPU-hours spread across 64 high-end Nvidia H100 chips.
The performance comparisons are striking. On a single H100, the system factors a smaller benchmark number called RSA-100 in about 29 seconds, beating top CPU-based factoring tools running on 96 processor cores. The energy and time required scale in a predictable way as the numbers get larger, and the approach is roughly proportional to the number of GPU cores available, meaning it should get faster as GPUs improve. The authors also point out that their system factored RSA-150, the previous quadratic sieve record, using far fewer computational resources than the prior record holder needed.