DeepMind factors 68-bit semiprimes with discrete diffusion and beam search

weballergy · x · 2026-11-10

A DeepMind team (including Demis Hassabis) shows in a new arXiv paper that Transformers trained with discrete denoising diffusion and decoded via guided test-time beam search can learn to factor semiprime integers directly from data, reaching 68-bit integers — a solid advance over the prior 56-bit learning-based state of the art.

Key findings:

No domain-specific number-theoretic priors are needed; the diffusion model acts as a generative prior proposing promising factor candidates, which exact verification or lattice-based post-processing then completes.
The authors derive empirical scaling laws relating approximation quality to data volume, model size, and test-time compute. Unlike language, problem size (bit length) is the key driver: compute for fixed accuracy scales exponentially with bit length.
The method is less compute-efficient than classical factoring algorithms, and the projected cost for cryptographically relevant integers remains prohibitive — posing no threat to current cryptography.

Original post →

DeepMind factors 68-bit semiprimes with discrete diffusion and beam search

More from Safety