DeepMind's AI agents cut the theoretical cost of factoring many 1024-bit RSA keys, ending a 33-year stall

On November 6, Google DeepMind announced that human-guided AI agents had found two weaknesses in legacy 1024-bit RSA. One is a working paper you can read today: Fan Factories, dated November 5, which lowers the theoretical cost of factoring many same-size RSA moduli when only a modest shared precomputation is available. It moves a constant that had not changed since 1993. It does not factor any single key faster, it has not been implemented, and its abstract says it does not threaten deployed cryptosystems based on 2048-bit and larger RSA.

What the paper actually improves

The general number field sieve (GNFS) factors an integer in heuristic time L[1.923], and progress in the field is measured by that constant. Don Coppersmith introduced two variants in 1993. The multiple number field sieve (MNFS) lowers the constant to 1.902. His factorization factory exploits the fact that the rational side of the sieve depends only on the size of the integer: sieve it once at a cost of L[2.007], store the results, and each later integer of that size costs L[1.639].

That left a gap. A factory with a precomputation of only about one GNFS run gained nothing, so the best per-integer cost at that budget stayed at MNFS’s 1.902 for 33 years.

The new construction gives each target integer its own family, or fan, of number fields, all drawing on the shared precomputed table. With a budget of one GNFS run, each further integer costs L[1.793]. The paper determines the optimum in closed form for every budget, and fans beat all earlier methods for budget exponents strictly between 1.902 and about 1.950, which at 1024 bits is roughly half a GNFS run to 2.3 GNFS runs.

Reading the 1/58 figure

At 1024 bits, with lower-order terms set to zero, each further integer costs about 1/58 of a GNFS run, 30 times less than with MNFS. Counting the precomputation, M keys cost about 1 + M/58.5 GNFS runs, against M/1.94 for MNFS. The fan factory wins from three keys onward, and its average per-key cost comes within a factor of 2 of the 1/58 figure once M reaches 59.

Four limits matter as much as the headline:

• One key gets nothing. With no shared work, the fan factory reduces to MNFS.
• It doesn’t lower the floor. With unlimited precomputation, Coppersmith’s original factory remains optimal: about 14 GNFS runs up front at 1024 bits, then about 1/7300 of a run per integer. The fan is a gain for modest budgets only.
• Memory is a serious obstacle. At a one-run budget the stored table holds about 2^75 pairs at 1024 bits, while the paper’s cost figures assume a unit-cost RAM model in which that storage is not penalized. Cost under the area-time model, where storage is expensive, is an open question.
• Batch mode gains little. Factoring integers together with no precomputation improves the exponent by at most 0.018, a leading-order factor of at most 1.75 at 1024 bits.

The paper’s own table shows why a growing ratio doesn’t translate into danger for larger keys. At 2048 bits the per-key saving rises to 1/240 of a GNFS run and the advantage over MNFS to 99x, but the entry fee is a precomputation of about 2^117 operations.

The signature result is harder to check

The second advance concerns forging RSA signatures when an attacker can get a device to sign values of their choosing. It is reported in a companion paper titled “Modular Roots from a Restricted Oracle,” which we could not obtain, so these figures come from secondary coverage rather than the source.

According to Data Studios, padding adds no meaningful protection once an attacker controls roughly half of the signed block. When the attacker controls only something like a 32-byte digest, the agents’ method is estimated to be about 1,600 times better than the best previous one for 1024-bit keys. That number is a theoretical estimate. The measured result is smaller: an AI-written implementation reproduced a known attack on a previously solved 1024-bit benchmark with 3.5 times less CPU time, 391 core-years against 1,380. Plain English characterizes this as an implementation gain within the same algorithm, in a sandbox assuming offline oracle access that live systems must forbid.

How the AI was used

The paper says the results came from a two-agent harness, in which one model generated proofs and a second verified them. It names no models. The author list includes DeepMind researchers Dj Dvijotham, Abhradeep Thakurta and Pushmeet Kohli, alongside Nadia Heninger (also affiliated with UC San Diego) and Emmanuel Thomé (also affiliated with Inria), two established figures in practical factoring. Coverage describes humans choosing the problems and judging significance.

The verification claim has a precise boundary. The algebraic identities and exact feasibility witnesses are machine-checked in Lean 4, but the calculus arguments such as stationarity and monotonicity are proved in the text, and the whole analysis rests on the standard NFS heuristics. The Lean work certifies the optimization given the cost model. It says nothing about whether the model predicts real hardware. This follows a run of AI-assisted results checked in Lean, including OpenAI’s claim against the Exponential Time Hypothesis, still under expert review.

What to watch

The paper names its main open question directly: no fan factory exists, and the key size at which one would overtake a well-tuned sieve is unknown. Independent review comes first, since both papers are unreviewed working documents. The practical takeaway needs no new mathematics. NIST has disallowed RSA keys below 2048 bits for new signatures since the end of 2013, according to Data Studios, and the paper is another reason for anyone still holding a large population of 1024-bit keys to retire it, because this work specifically lowers the cost of attacking many keys of one size.