Semiprime Factorization with Discrete Diffusion and Beam Search: Scaling Laws
Brendan O Donoghue, Nenad Tomasev, Volodymyr Mnih, Timothy Nguyen, Dalin Guo, Arun Nair, Kenneth Yang, Alexandre Frechette, Jasper Xian, Jean Tarbouriech, Pavel Tyletski, Ingrid von Glehn, Johannes Bausch, Demis Hassabis, Raia Hadsell
cs.LG
2026-11-07
DeepMind lifts learning-based semiprime factorization from 56 to 68 bits with discrete diffusion plus lattice post-processing; compute roughly doubles per bit, so RSA stays safe.
RSA's security rests on one assumption: given n = p×q, the product of two large primes (a semiprime), recovering p and q is computationally infeasible. The strongest classical algorithm, the General Number Field Sieve, runs in sub-exponential time; the largest publicly factored RSA modulus stands at 896 bits. Shor's algorithm is polynomial on a quantum machine, but fault-tolerant hardware remains distant. A third path is learning factorization purely from data, with no number-theoretic priors. The previous record was 56 bits (Freivalds et al., 2023, discrete diffusion). DeepMind pushes it to 68 bits and, more importantly, measures scaling along four axes: data, model size, problem size, and test-time compute.
Factorization is cast as conditional generation over binary strings. n occupies 2k bits as a fixed unmasked prefix, the factors p and q occupy k masked bits each, and a bidirectional transformer denoiser learns to recover them. Training uses discrete diffusion, which corrupts tokens with masking rather than Gaussian noise. Each design choice targets a specific failure mode:
| Setting | Metric | Result |
| 30-bit (k=15), 325M, T=16,384 | Exact factorization | 87.60% |
| 40-bit (k=20), 325M, T=16,384 | Exact factorization | 8.30% |
| 68-bit (k=34), 12B, T=16,384 | Exact factorization | 0.00% |
| 68-bit, 12B + Coppersmith | 15,523 strict 68-bit semiprimes | 1 success (0.0064%) |
| Prior learning-based record | Bits factored | 56 |
For scale: at 30 bits, trial division guarantees success in at most 16,384 divisions, each vastly cheaper than one denoising step. Where ML works at all, it is far slower than the oldest algorithm in the book.
The scaling laws are the real deliverable. Data follows a clean power law. Validation NLL has a hard floor at 0.262, reachable by a non-factoring baseline that just copies visible bits and propagates local carries; solve rate stays exactly zero until NLL drops below it, then rises sharply. Problem size dominates: each additional factor bit costs roughly 2× the training steps at fixed loss. The model learned no sub-exponential algorithm; what it learned is closer to brute force with a neural prior. On test-time compute, models with nonzero solve rate improve roughly linearly in log T; the 68-bit model stayed at zero even at 16,384 steps.
The single 68-bit success deserves scrutiny. Across prefix lengths 4 to 16, the model's MSB match rate is about 3× uniform random guessing, but roughly 2.5× of that comes from a zero-learning prior restricting candidates to the product hyperbola; the learned concentration is only about 1.25×. Past bit 4, each additional bit multiplies the survival rate by 0.52, matching random decay. At the 18-bit Coppersmith threshold: one observed hit versus 0.24 expected under uniform guessing and 0.62 under the hyperbola prior. The honest reading is a tail draw from a magnitude-calibrated prior, not reliable algorithmic factorization.
The value is the measurement, not the record. Language modeling shows smooth power laws and length generalization because language has reusable hierarchical local structure. Semiprimes are globally coupled and cryptographically pseudorandom; flip one bit of n and the factors change chaotically. With no reusable substructure, data requirements grow exponentially in bit length. That is a quantified negative answer to whether learned search can crack pseudorandom problems, and a concrete explanation of why scaling curves from language do not transfer.
Three pieces are portable. The two-level search pattern (beam search plus feasibility pruning plus treating committed decisions as oracle conditioning) fits any domain where verification is easier than generation. The NLL-floor diagnostic, computing the mindless baseline's loss first and checking whether the model broke through, works in any constrained generation task. And approximate generation followed by exact post-processing, with Coppersmith in that role here, is a pattern worth seeking in other combinatorial problems.
The authors state the main ones themselves: computationally far less efficient than classical algorithms, no present or foreseeable threat to RSA, and scaling that resembles brute force. They also flag that training and test share the same prime pool: pairs never overlap, which rules out memorized answers, but at small bit lengths each prime is seen thousands of times, so the contribution of prime-vocabulary memorization cannot be cleanly separated.
Two more concerns on close reading. First, the 68-bit and 56-bit records are not the same kind of comparison: 56 bits was the diffusion model recovering factors on its own, while the 68-bit instance came from ancestral sampling (T=500, no beam search) producing a 19-bit prefix on one factor, with Coppersmith completing the remaining 16 bits, statistically indistinguishable from a prior tail draw. The record stands on the paper's own terms; its substance is thinner. Second, the model-size axis is weak: 2B is always best or tied, but 325M and 1B swap places across bit lengths, and the paper does not explain the noise.