Cognition’s research team recently factored RSA-260, a 260-digit number, establishing a new record for the largest publicly solved RSA Factoring Challenge problem and surpassing the previous RSA-250 solved in February 2020, the company says. This feat was achieved using a new GPU lattice siever built by Cognition’s “Devins,” enabling factoring at ten times lower cost than previously public methods. The team estimates hyperscalers could now factor RSA-1024 numbers for around $30 million.
Cognition’s GPU Lattice Siever Factors RSA-260
Cognition’s development of a GPU lattice siever enabled the factorization of RSA-260, a 260-digit number, by significantly reducing computational costs compared to previous methods. The team achieved this feat not through algorithmic breakthroughs in number theory, but by focusing on hardware acceleration and efficient implementation of the well-established general number field sieve, or GNFS, according to Cognition.
Prior public records for GNFS factorization relied exclusively on central processing units for the computationally intensive lattice sieving stage; Cognition’s innovation lies in successfully adapting this process for graphics processing units. The impetus for this project stemmed from a personal interest in factoring numbers, according to the lead researcher, who dedicated several weeks to optimizing a job scheduler for disaggregated compute resources.
This led to the prompt given to Cognition’s “Devin” AI system: “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.” Devin responded by creating a GPU-based replacement for las, the CPU lattice siever used in the CADO-NFS software package.
The system was instructed to iterate until it surpassed the performance of its CPU counterpart, utilizing a single GPU box for testing and adhering to strict resource constraints, the company says. The development process involved running Devin over a three-week period, demonstrating a focused and parallelized approach to optimization.
While acknowledging a limited understanding of the underlying mathematics, “I can tell you that polynomial selection provides a constant factor on lattice sieving yield; I cannot tell you how the polynomial is used in the siever”, the researcher emphasized the power of an approach to solving complex problems. This strategy appears to be yielding results beyond initial expectations, with the observed rate of progress suggesting a significant capability overhang yet to be fully explored.
The team’s success with RSA-260 builds on prior work in the field, Cognition reports. The implications of this advancement extend to the broader landscape of cryptographic security. While the team clarifies they did not factor RSA-260 by manually guessing prime numbers, or by utilizing a quantum computer, the increased efficiency of their method raises questions about the viability of RSA-1024 encryption, a benchmark previously considered secure.
The researcher notes that the team is now able to factor numbers at a significantly lower cost, and suggests that this capability could be applied to other challenging computational problems. “About three weeks elapsed from first prompt to RSA-260 factors found. The rate evinces a capability overhang whose extent we are only beginning to explore,” they stated, hinting at the potential for further breakthroughs.
The team also referenced existing integer-factorization software, msieve, as a point of comparison for their work. This suggests that the future of cryptography may lie not in discovering entirely new algorithms, but in optimizing existing ones for emerging computational platforms.
RSA-260 Factorization Cost: $400k and 13.5 GPU-Years
The factorization of RSA-260 required approximately $400,000 and 13.5 GPU-years of compute time, a figure that demonstrates a substantial reduction in the cost of factoring large numbers. This achievement, detailed by researchers at Cognition, utilized a newly developed GPU lattice siever and represents a significant decrease compared to previous methods; the team estimates the cost is ten times lower than the prior public state of the art, by the company’s account.
The implementation used existing infrastructure designed for large language model training, utilizing spare compute capacity within NVL72 racks interconnected by NVLink. This efficiency stems from a focus on performance engineering rather than novel algorithmic advancements, according to the researchers. Modern General Number Field Sieve implementations, like the modified CADO-NFS used in this project, consist of sequential stages: polynomial selection, lattice sieving, and linear system solving.
The team reports essentially no algorithmic advancements, instead concentrating on optimizing these established stages for GPU architecture and maximizing the use of the GPU’s memory systems. This approach allowed them to achieve a factorization cost of roughly $400,000, based on current market prices for GPU time.
A detailed breakdown reveals 643 GPU-days were used for polynomial selection (this is anomalously high basically due to operator incompetence), 3,813 GPU-days for sieving, and 467 GPU-days for linear system solving (of which about 7% failed to make progress due to crashes or preemption by more important work). While acknowledging that factoring RSA-2048-sized numbers remains computationally prohibitive with current methods, the reduction in cost for smaller RSA keys raises concerns about the vulnerability of systems still relying on that level of encryption.
The researchers emphasize that this isn’t simply about raw computational power, but also about accessibility; “you just need enough GPUs rather than making specialized hardware.” This suggests a democratization of factoring capabilities, potentially allowing a wider range of entities to challenge existing cryptographic systems. The team’s work builds on previous research, and the relative ease with which non-cryptographers can now contribute to accelerating factoring is a notable outcome, Cognition claims.
This opens up opportunities for a broader range of researchers and engineers to participate in the ongoing effort to improve factoring algorithms and assess the security of cryptographic systems. The team’s analysis also indicates that the factorization ran at no marginal cost, utilizing spare compute resources that would otherwise remain idle. This efficient use of existing infrastructure further underscores the potential for cost-effective advancements in the field of cryptography.
RSA-1024 Factoring Estimated at $30 Million with GPUs
While RSA-1024, equivalent to 309 digits, represents a 78-fold increase in computational complexity over RSA-260, the team’s analysis indicates a surprisingly manageable cost escalation for factoring it. This reduction in cost is not merely theoretical; it’s rooted in a technological leap. Cognition’s GPU lattice siever achieved a ten-fold decrease in the expense of factoring RSA-260 compared to previously published methods, a feat previously hampered by the difficulties of efficiently implementing lattice sieving on graphics processing units, the company says.
Prior public GNFS factorization records relied exclusively on CPUs for this important step, but the new implementation demonstrates that GPU-accelerated lattice sieving can be more cost-effective overall. The team’s work demonstrates that “all that I was missing was a sufficiently high-performance GPU lattice siever that could accept the parameters needed to factor RSA-260,” highlighting the critical role of optimized hardware in accelerating the process.
The implications extend beyond simply lowering the financial barrier to breaking RSA-1024. The team notes that the current implementation of the factorization pipeline remains significantly suboptimal, suggesting that further optimization could reduce the cost of factoring RSA-1024 by another multiple of two, according to Cognition.
While Devin successfully optimized and executed a complex computational pipeline, the team clarifies that it did not operate with complete autonomy. Human expertise was still required for tasks such as polynomial selection, initiated even before the linear algebra was fully optimized, based on an initial estimate that RSA-260 could be factored within a month.
Sparse Compute Utilization Enables Cost-Effective Factoring
The computational cost of factoring RSA-260, a 260-digit number, was reduced tenfold through a newly developed GPU lattice siever built by Cognition, demonstrating a substantial leap in factorization efficiency. This achievement wasn’t driven by specialized hardware, but by maximizing the utilization of existing infrastructure and a focus on performance engineering, allowing the team to use spare compute resources within their large language model training clusters, the company says.
The factorization process itself consumed 643 GPU-days for polynomial selection (this is anomalously high basically due to operator incompetence), 3,813 GPU-days for sieving, and 467 GPU-days for linear system solving, all completed as a side project utilizing a small fraction of Cognition’s overall compute capacity. This efficient use of resources has significant implications for factoring larger RSA keys; the team estimates that factoring RSA-1024, equivalent to a 309-digit number, could now be accomplished for approximately $30 million using current market GPU prices.
This estimate is based on standard General Number Field Sieve scaling, suggesting a 78-fold increase in computational effort compared to RSA-260, but the cost remains surprisingly accessible given the historical difficulty of factoring such large numbers. Further optimization of the factorization pipeline, the team believes, could potentially reduce this cost by another factor of two, highlighting the ongoing potential for improvement, Cognition reports. Cognition’s approach relied heavily on existing software and prior research.
The team built upon the foundation provided by CADO-NFS, an advanced and robust open-source implementation of the General Number Field Sieve algorithm, utilizing its established techniques, pipeline stages, and reference CPU implementation. This allowed them to focus on optimizing the GPU lattice siever and integrating it into their existing infrastructure. “It provided all the relevant techniques, the pipeline stages and their interfaces, and a reference CPU implementation,” the team noted, emphasizing the importance of building on established work.
The NVL72 racks within their LLM clusters, each nominally comprising 18 computers, proved important, as the fast NVLink connections facilitated efficient communication between GPUs during the factorization process. However, the team acknowledges potential drawbacks to relying heavily on automated tools like Devin. While Devin streamlined the measurement and analysis process, enabling faster progress and identification of areas for improvement, there are concerns about a potential loss of deep human understanding.
“I did not learn as much about NFS or GPU programming as I could have expected to had I done this on my own,” the researcher admitted, suggesting a need to balance automation with opportunities for hands-on learning. The team is actively considering how to allocate resources to maintain human expertise even as technology advances and incentivizes automation.
GPU Lattice Sieving Overcomes Historical Performance Challenges
The implementation of a GPU lattice siever enabled a factorization cost of approximately $400,000, a figure significantly lower than previous attempts at comparable calculations, and required 4,900 GPU-days, or 13.5 GPU-years, to complete. This achievement bypassed a longstanding challenge within Generalized Number Field Sieve (GNFS) implementations, where efficiently translating lattice sieving to GPU architecture had proven difficult, despite the potential for increased performance due to higher memory bandwidth. The team specifically targeted lattice sieving as an ideal workload for preemptible computing resources, noting its inherent parallelism across billions of small work units and its tolerance for immediate interruption without losing substantial progress.
This characteristic proved particularly valuable given a lack of consistent access to dedicated single-node workloads, allowing for efficient utilization of available GPU time. “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,” the team reports, emphasizing the method’s adaptability to fluctuating resource availability. The focus on sieving was strategic, as it represents the most computationally intensive portion of the GNFS process, meaning gains in this area translate directly into overall factorization speed.
The development of the GPU lattice siever itself was driven by an automated optimization tool, Devin, initially prompted with the task of creating a drop-in replacement for the CPU-based las siever used in the CADO-NFS software. After approximately seven hours of iteration, Devin successfully produced a functional GPU siever, which was then further refined over a week-long optimization process.
The team details outlining the timeline of this automated development, the company’s account states. Performance improvements were observed throughout the sieving phase, with two upgrades to the siever resulting in a 14-17% increase in efficiency. Measurements of end-to-end workunit times showed reductions across different GPU models: GB200s improved from 585 seconds to 486 seconds, GB300s from 586 seconds to 504 seconds, and B200s from 628 seconds to 541 seconds.
See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.
