We demonstrate that transformer architectures trained with discrete denoising diffusion and decoded via guided test-time beam search can learn to recover the prime factors of semiprime integers directly from data. Our approach establishes a new frontier for learning-based semiprime factorization, successfully factoring 68-bit integers-a substantial advance over the prior 56-bit state of the art. While computationally less efficient than classical factoring algorithms, our model requires no domain-specific number-theoretic priors and learns purely from training examples. In practice, the diffusion model acts as a generative prior, identifying promising factor candidates where exact verification or lattice-based post-processing can complete the factorization. Furthermore, we derive empirical scaling laws relating approximation quality to training data volume, model size, and test-time computation. In contrast to language, problem size is the key driver of scaling behavior. Achieving a fixed accuracy on a held-out test set requires compute that scales exponentially with bit length. Consequently, our findings pose no threat to security, as the projected compute cost required to factorize cryptographically relevant integers remains prohibitive.
Figures & tables
Figure 1: The oracle self-conditioning iteration. During the inner mini-denoising loop, decided bits are mapped to one-hot target embeddings, while remaining masked positions receive soft logits. Both signals are merged to form the conditioning input for the subsequent denoising step.
Figure 2: Beam search expansion and feasibility pruning. At each step, valid states in the active beam are expanded. If a partial assignment violates the arithmetic constraints, it is pruned. The remaining feasible states are ranked, and the top B paths are retained in the beam.
Figure 3: Validation negative log-likelihood (NLL) across training steps s (with power-law fits L(s)=As−α+L∞ ) for the 325M model across factor bit-lengths k∈{15,…,21} .
Figure 4: Validation NLL across training steps for three model sizes (325M, 1B, and 2B), faceted by factor bit-length k∈{15,…,21} .
Factor Bits
Diffusion Steps
1024
2048
4096
8192
16384
15
64.55%
68.85%
76.47%
80.18%
87.60%
20
1.86%
3.42%
4.59%
6.35%
8.30%
34
0.00%
0.00%
0.00%
0.00%
0.00%
Table 1: Single-trajectory ancestral diffusion exact factorization accuracy on the held-out test set ( 1,024 test instances per bit-length; no beam search or Coppersmith post-processing; 1 sample per test instance, τ=0.7 ) across denoising step budgets T . Models: 325M trained for 100k steps at k=15 , 325M trained for 348k steps at k=20 , and 12B trained for 109k steps at k=34 .
Figure 5: Log-linear scaling of single-trajectory ancestral solve rate with inference denoising steps T across training horizons ( 30k , 100k , 1M steps) for a 325M model at k=15 trained with our initial pointwise-corruption baseline recipe (prior to contiguous blockwise masking and two-pass concave rollout used in Figure 6 and Table 1 ).
Figure 6: Each point on the above plot is a model’s solve rate and validation loss at a particular point in training. The lower the validation loss, the higher the solve rate for any fixed number of denoising steps. This is true across various model sizes.
Figure 7: Loss curves for Flash 325M trained on factor bits 15, 16, 17, 18. We look at the final loss values of factor bits 16, 17, 18 and trace horizontal lines showcasing at what step loss curves corresponding to lower factor bits achieve those loss levels. Circled are approximate points along the loss curve for factor bit 15 where the horizontal lines meet it, corresponding to points in training where it achieves the final loss that the factor bits 16, 17, 18 problem achieves. Square boxes denote analogous approximate points of intersection among the other loss curves.
MSBs ( m )
12B Count
12B Rate
Uniform Prior
Hyperbola Prior
≥2
15,489
99.78%
75.00% ( 11,642.3 )
100.00% ( 15,523.0 )
≥4
7,957
51.26%
23.44% ( 3,638.2 )
47.84% ( 7,426.9 )
≥6
2,526
16.27%
6.15% ( 955.0 )
14.74% ( 2,288.4 )
≥8
701
4.516%
1.556% ( 241.6 )
3.924% ( 609.2 )
≥10
189
1.218%
0.390% ( 60.6 )
0.978% ( 151.8 )
≥12
49
0.316%
0.098% ( 15.2 )
0.238% ( 37.0 )
Table 2: Empirical leading-MSB prefix match distribution P(Lmatch≥m) for the 12B model at k=34 ( 1 ancestral sample (p^,q^) per instance, T=500 , across N=15,523 held-out 68-bit semiprimes with n≥267 ), compared against (A) naive uniform random bit-guessing on 2 factor candidates with fixed leading bit 1 ( 1−(1−2−(m−1))2 ), and (B) a zero-learning hyperbola magnitude prior that samples a random point on the product hyperbola p^q^≈n with p^≥q^ by drawing p^ uniformly from the valid integer interval {⌈n⌉,…,234−1} and setting q^=⌊n/p^⌋ .
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 8: IsoFLOP smile curves for k=24 , demonstrating the trade-off between final validation NLL (left) and final validation accuracy (right) against model parameters for fixed compute budgets.
Figure 9: Difficulty scaling illustrating the degradation of final validation NLL (left) and final validation accuracy (right) as the number of factor bits increases, compared between the 325M and 2B models.
Figure 10: Faceted per-trajectory power-law fits for the 2B parameter model across factor bit-lengths k=16 to k=40 . The fits closely track the empirical validation NLL with low mean absolute percentage error (MAPE).
Figure 11: Faceted per-trajectory power-law fits for the 325M parameter model across factor bit-lengths k=16 to k=40 .
Figure 12: Validation NLL versus cumulative training tokens on a log-log scale for the 2B parameter model across factor bit-lengths k=16 to k=40 .
Figure 13: Validation NLL versus training tokens on a log-log scale for the 325M parameter model across various factor bit-lengths.
Figure 14: Validation NLL versus cumulative training tokens (linear scale) for the 2B parameter model.
Figure 15: Validation NLL versus cumulative training tokens (linear scale) for the 325M parameter model.
Figure 16: Test-Time Compute Scaling across Pre-Training Checkpoints. Exact factorization mean as a function of max search frontier size ( B∈{32,128,512,1024} , labeled N on the horizontal axis; log2 scale) across factor bit-lengths ( k∈{16,20,24,28} , greedy decoding temperature τ=0 , labeled T=0 ). Subplots denote pre-training progression ( fraction complete∈{0.25,0.50,0.75,1.00} ). Test-time search scaling yields monotonic performance gains, with larger frontier budgets partially compensating for earlier checkpoint maturity.
Figure 17: Pre-Training Stage Progression vs. Test-Time Search Budget. Exact factorization mean vs. pre-training completion fraction ( 0.25 to 1.00 ), faceted by search frontier size ( B∈{32,128,512,1024} , labeled N ; greedy decoding τ=0 ). Colored lines denote factor bit-length ( k∈{16,20,24,28} ). As pre-training matures, higher search budgets ( B=1024 ) unlock substantially steeper performance trajectories compared to constrained search ( B=32 ).
Figure 18: Compute Efficiency (Test-Time FLOPs vs. Performance). Exact factorization mean as a function of total test-time inference FLOPs, faceted by factor bit-length ( k∈{16,20,24,28} bits, greedy decoding τ=0 ). Colored curves represent pre-training checkpoint stages ( 0.25 to 1.00 ). Note independent x - and y -axes per subplot. Within each fixed problem hardness, expanding test-time search compute demonstrates predictable efficiency scaling.
Department of Mathematics, University of Bologna, Italy · Gatsby Computational Neuroscience Unit, UCL, UK · Department of Information Engineering, University of Florence, Italy