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.
We study whether a transformer network can learn the deterministic sequence of trees generated by the iterated prime factorization of the natural numbers. Each integer is mapped into a rooted planar tree and the resulting sequence NT defines an arithmetic text with measurable statistical structure. A transformer network (the GPT-2 architecture) is trained from scratch on the first 1011 elements and evaluated on next-token prediction and masked-token prediction tasks, with a Hidden Markov Model as baseline and a scaling analysis over context window, dataset size, vocabulary size and model size. The model reaches a word accuracy of about 0.4, well above the baseline, and its performance remains stable on test blocks located at 1013-1015, far beyond the training interval. Moreover, the likelihood assigned by the trained model separates the arithmetic text from two controls: synthetic token sequences that preserve the marginal token frequencies but not their order, with a separation that widens with the context, and sequences containing more than three consecutive square-free integers, a configuration that arithmetic forbids. These results indicate that the transformer captures regularities of the arithmetic text that go beyond its frequency profile.
Alessandro Breccia, Federica Gerace, Marco Lippi +2
Department of Mathematics, University of Bologna, Italy · Gatsby Computational Neuroscience Unit, UCL, UK · Department of Information Engineering, University of Florence, Italy
Numbers have algebraic structure that standard neural embeddings often fail to expose. We introduce Prime Fourier Embeddings (PFE), which encode integers as prime-indexed (cos, sin) pairs derived from the harmonic analysis of Q, providing a pre-structured representation in which modular arithmetic reduces to selecting the relevant prime channel rather than discovering algebraic structure from scratch. We prove that any linear map equivariant with respect to the product group action on PFE must be block-diagonal with one independent block per prime -- a consequence of Schur's lemma applied to the resulting character decomposition. For square-free composite moduli, the Chinese Remainder Theorem predicts which prime channels are task-relevant. Both predictions are confirmed empirically: ablation studies show specialization ratios exceeding 500x between task-relevant and task-irrelevant channels, with perfect in-distribution test accuracy across all square-free composite moduli tested.
Hyunsang Hwang, Suhyun Bae, Donghun Lee
Department of Mathematics, Korea University, Seoul, South Korea.
We train a two-layer transformer encoder to classify rational elliptic curves E/Q of conductor ≤10000 as either rank 0 or rank 1 from the first 128 normalized Frobenius traces. We achieve >99% accuracy on both classes, and accuracy is essentially unchanged on test curves with no isogeny or quadratic-twist relative in the training set. We then apply techniques from mechanistic interpretability such as attention analysis, linear probing, activation patching, logit attribution, and neuron-level circuit analysis to reverse-engineer the algorithm the (centroid in function space) model learned. We find that a sparse circuit of 20 out of 512 layer-1 MLP neurons is sufficient for rank prediction under a linear probe with an AUROC of 0.992 at plateau, implementing a push-pull detector architecture of rank-0 and rank-1 detectors with a one-sided readout. However, we notice that the model has sub-optimal readout problems indicating a mismatch in rank-order between the readout pathway and the discriminative circuit. Critically, the learned input weights of the top discriminating neuron match the Mestre-Nagao sum heuristic weights log(p)/(p⋅logB) with a Spearman coefficient r=0.997 and Pearson coefficient r=0.952: the model has learnt a result from analytic number theory from the Frobenius trace data alone. We additionally find that all 50 independently trained models concentrate CLS attention on prime positions at 2-50× the rate of composite positions. The CLS embedding encodes logL(E,1) with R2=0.962±0.011 across the 50 models (after controlling for the conductor). Activation patching analysis reveals that attention weights are dissociated from causal information flow. Additionally, the 50 solutions from training are near-identical in function space (with pairwise agreement >98.8%) despite large weight space barriers.