GoKawiilFactoring RSA-260 By Eric Lu 09.09.26
Over the past few weeks, the Cognition research team and I have been optimizing our job scheduler to better use disaggregated compute. As a proof of concept, and because I’ve enjoyed factoring numbers as a hobby for the past ten years or so, I drove a bevy of Devins to obtain a factorization of RSA-260. In order to do this, my Devins built the world's highest-performance GPU lattice siever, which enables factoring numbers at 10x lower cost than the previous public state of the art. Here is the factorization: 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199 = 4397328654844826923795068102505872571721883526553349659561256924505973939597593482272505698004801207988043088656411102133523080581 × 5028695206842569864686141618253083416610081090075366674776775706538324961364412200138116378509733307971876652984898985905923678379 RSA-260 (a 260 digit number) sets a new record for the largest publicly solved RSA Factoring Challenge problem, which benchmarks the feasibility of breaking the RSA cryptosystem. The previous record, RSA-250, was set in February 2020. For reference, state-of-the-art RSA public keys contain 2048 bit (~617 digit) factoring problems, while 1024-bit (~309 digit) RSA was deprecated in 2013. Below I’ll give some details about how this was accomplished, but here are two important takeaways: Hyperscalers or frontier AI labs could likely factor RSA-1024 numbers at a cost on the order of $30 million per number — and, with a bit more optimization, likely substantially less. On the other hand, RSA-2048 remains roughly a billion times harder than RSA-1024 and does not appear to be meaningfully affected by this work.
Devin is a sufficiently powerful software engineer to solve a challenging problem at the intersection of computational number theory and GPU performance engineering. My role was primarily to set priorities, establish benchmarks, and recognize when work was going off-track. Devin otherwise autonomously handled measurements, cluster operations, and optimization end-to-end. This substituted for what would likely have been a multi-month effort by a team of highly specialized domain experts. In conclusion, the barrier to entry for cryptanalytic work, other computational mathematics more broadly, and likely most large-scale scientific computing research, is far lower than it used to be. Exciting work beckons anywhere programming can be used to solve a research problem; I encourage all to be ambitious and explore what autonomous software engineering agents can do when applied to these fields!
Contrary to some circulating claims, I did not factor RSA-260 by guessing and checking 130-digit prime numbers by hand. Cognition also has not yet built a multi-thousand-qubit quantum computer. RSA-260 was factored by a new implementation of the general number field sieve (GNFS) for GPUs, prepared and run using Devin. GNFS is the most efficient algorithm known for (most) numbers above roughly 100 digits in size and was used in previous record-breaking RSA number factorizations. The implementation was a significantly modified CADO-NFS. I report essentially no algorithmic advancements — implementing lattice sieving and sparse linear system solving on GPUs required only “good old performance engineering” to take advantage of the preposterous memory systems of the GPU.
In total, I estimate that this factorization cost about 4,900 GPU-days, or 13.5 GPU-years, which is about $400k at current market prices. In more detail, modern GNFS implementations consist of a few stages run sequentially: polynomial selection, lattice sieving, and linear system solving. The time breakdown was: 643 GPU-days in polynomial selection (this is anomalously high basically due to operator incompetence)
3,813 GPU-days sieving
467 GPU-days linear system solving (of which about 7% failed to make progress due to crashes or preemption by more important work) I did this as a side project using a single-digit percentage of our cluster, in the course of optimizing our job scheduler to improve allocations to use disaggregated compute. What does this mean for larger RSA instances? RSA-1024 is equivalent to 309 digits; according to standard GNFS scaling this is merely 78x more computation than RSA-260. I estimate the cost of factoring RSA-1024 at market GPU prices to be roughly $30M, which can trade off against wall clock time. I know for a fact that the current implementation remains significantly suboptimal; I would not be surprised if moderate further work could reduce the cost of factoring RSA-1024 by another multiple of 2. Of course, the fact that RSA-1024 is insecure is not news. There was speculation that the NSA might have the capability to do RSA-1024 economically as early as the mid-2000s (see e.g. TWIRL or the Bernstein matrix machine). Instead, as we describe below, the main developments are (1) a potentially lower cost (in dollars and time) for the factorization, (2) potentially more parties capable of performing the factorizations (you just need enough GPUs rather than making specialized hardware), and (3) the relative ease with which non-cryptographers can now work on speeding up factoring. Finally, I emphasize that the efficiency gains have little impact on the feasibility of factoring RSA-2048-sized numbers with GNFS.
The factorization ran at no marginal cost on spare or fragmented compute that couldn’t be used for other purposes. Why does this compute exist? The clusters we use for LLM training and inference contain NVL72 racks, each nominally comprising 18 computers interconnected by fast NVLink. LLM workloads use groups of computers within single racks in order to take advantage of this fast interconnect. The job scheduler must solve a constrained optimization problem to pack workloads into racks. In this global allocation, some racks may end up with an idle node or two; sometimes jobs request spare nodes to accommodate failover, or jobs might need even numbers of computers on a rack that has only 17. For us, these inefficiencies amount to a single-digit percentage of overall compute. To make use of this spare compute, as a first step, I rigged our job scheduler to fill single-node jobs around other workloads at bottom priority. However, we also lacked a consistent source of readily preemptible single-node workloads. Naturally, at this point I thought of lattice sieving, which is a perfect fit for this situation. Lattice sieving is embarrassingly parallel over billions of small work units, can make progress using single nodes at a time, and is safe to preempt instantly. It is also the most computationally expensive part of GNFS, so getting sieving done is a lot of progress toward a factorization. However, all prior public GNFS factorization records used only CPUs for lattice sieving; indeed, due to challenges of efficiently implementing lattice sieving on GPUs, for a long time it was not clear that GPU lattice sieving could be more cost-effective overall. In short, all that I was missing was a sufficiently high-performance GPU lattice siever that could accept the parameters needed to factor RSA-260. So, what did I do? Ask Devin.
At August 13th 0:11:58 Pacific time I aimed Devin at producing a drop-in replacement for las , the CPU lattice siever of CADO-NFS. Here is the prompt I used: CADO-NFS is FOSS software for performing GNFS. I'd like you to develop a fast GPU lattice siever. This has historically been difficult with present techniques because optimizations for CPU lattice sieving employ a lot of conditional branching and complex memory access patterns, and the intersection of GPU kernel-writing experts and number field theory experts is quite small. However, the higher total memory bandwidth available in a GPU promises a higher performance ceiling. And that intersection now contains you. You have Modal access keys available that I authorize you to use to spin up a single GPU box for performance testing. Obtain the CUDA toolchain etc. and build locally; use GPU only for performance testing and shut it down between measurements. The resultant GPU lattice siever should be a drop-in replacement for the siever step of CADO-NFS. Iterate until you exceed the performance of the CPU lattice siever. Two hours later I added that glas (GPU las , of course) should be able to handle the parameters used for RSA-250. Then I went to bed. I woke up to find that, after another 7 hours of iteration, Devin had succeeded. Over the subsequent week I drove Devin to optimize lattice sieving, then the rest of the GNFS pipeline. First, I will give a high-level description of our GNFS optimizations, and then I will describe the optimization workflow. GNFS optimizations (high-level) At a high level, GNFS consists of a number of stages run sequentially: polynomial selection, lattice sieving, and linear system solving. Polynomial selection fixes the number field over which the algorithm is run. The choice of polynomial controls a constant-factor speedup on the lattice sieving step. It’s therefore typically worth spending a fixed fraction (~5%) of overall sieving compute finding a “good” polynomial. There was little technical innovation here; we adapted CADO’s stage-1 polynomial selection to GPUs (resulting in gps1 ), using also some kernel equipment from msieve’s well-optimized stage-1 polynomial selection. Polynomial selection is more or less embarrassingly parallel. The bulk of the GNFS computational effort is in lattice sieving. The goal of lattice sieving is to produce lots (8.3 billion in our case) of sparse linear relations over GF(2), where here (suppressing some details) the vector entries represent the parities of prime exponents in the prime factorization of a smooth number. Lattice sieving is also embarrassingly parallel over work items called “special q”s, but each work item requires performing a large number of read/writes at (for our purposes) pseudorandom locations in a large array; handling this was the primary technical challenge in optimizing sieving. Ultimately, we pack these relations into a large matrix over GF(2) and use linear system solving to find a linear dependence. At this scale, linear system solving is typically distributed and requires a lot of communication bandwidth; this is available in spades over Infiniband and NVLink. The block Wiedemann algorithm permits relaxing the communication constraint somewhat, and the particular implementation in CADO-NFS is also susceptible to optimization and running on GPUs, which we undertook. Solutions can be processed into congruences of squares modulo N, which yields the factorization. Overall, Devin substantially modified almost every piece, including modifying a couple of interfaces: A GPU-adapted version of CADO-NFS’s stage-1 polyselect, with components from msieve
A GPU-optimized lattice siever based on las
... continue reading