WorksComputer Science
Semiprime Factorization with Discrete Diffusion and Beam Search: Scaling Laws
Abstract
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.
Introduction
Integer factorization is one of the most important open problems in computer science, cryptography, and algorithmic number theory. Given a composite integer , the objective is to identify its prime factors such that . In the context of public-key cryptography, such as the Rivest–Shamir–Adleman (RSA) cryptosystem ([40]), the modulus is restricted to be a balanced semiprime—the product of two distinct, large, and randomly chosen prime factors and of equal bit-length. The security guarantees of RSA rely on the assumption that the inverse operation of recovering and from is intractable without additional knowledge.
The integer factorization problem is known to belong to the complexity classes NP (Nondeterministic Polynomial time) and co-NP ([34]), as any proposed solution can be verified in polynomial time. However, it is widely believed to be neither NP-complete nor contained within the polynomial-time class P, even though there is not yet a definitive proof that integer factorization on classical hardware requires exponential or super-polynomial time. Consequently, this problem has attracted substantial research interest. A discovery of an efficient classical factorization method would undermine the security of modern digital infrastructure, making the integer factorization problem not only a question of broader theoretical interest, but one of deep practical significance.
There is no shortage of increasingly sophisticated heuristics that have been proposed over a long period of time. Early naive approaches, such as trial division and Pollard’s rho algorithm ([36]), require exponential time. Therefore, these methods are inapplicable at the cryptographically relevant scale. The current state-of-the-art classical algorithm is the General Number Field Sieve
Corresponding author(s): [email protected] (GNFS) ([4, 25, 27]), which was introduced as an evolution of the Quadratic Sieve (QS) ([37]). GNFS involves constructing two monic irreducible polynomials that share a common root modulo , and the search is performed across smooth numbers over complex algebraic number fields. The time complexity of GNFS is sub-exponential, namely
where . While GNFS outperforms other methods, it remains super-polynomial in the bit-length of . Consequently, an 896-bit RSA cryptographic modulus currently remains the largest publicly acknowledged number to have been factored, which required substantial compute ((Weis, 2026)).
Subsequently, Peter Shor introduced a quantum algorithm capable of efficiently solving integer factorization presuming access to future fault-tolerant quantum hardware ([32, 41]). Shor’s algorithm leverages quantum superposition and the Quantum Fourier Transform (QFT) to solve the underlying period-finding problem, reducing the factorization time complexity to a polynomial bound of . This places integer factorization within the Bounded-error Quantum Polynomial time class (BQP) ((Aaronson, 2010)). While such quantum computers remain far in the future, this finding has catalyzed the search for post-quantum cryptography.
Unsurprisingly, semiprime factorization has also been approached with machine learning methods, and more recently deep learning ([3, 20, 33]). This has proven to be challenging, given the discrete combinatorial nature of the problem. Minor changes in activations may translate into severe violations of the imposed constraints. Recently, machine learning approaches have moved away from one-shot prediction to generative models. By formulating integer factorization as a search over a constrained discrete space, it is possible to achieve effective approximations at smaller scales. Specifically, the introduction of discrete denoising diffusion models ([2]) has shown promise.
Here, we contribute an empirical study of the scaling laws for semiprime factorization via discrete diffusion, both with and without subsequent test-time search and post-processing. These scaling laws enable us to characterize the extent to which machine learning can hope to tackle this problem, and extrapolate the findings to project how much time and compute would be required. We conclude that this does not present a risk to the current RSA protocols. Finally, at the 68-bit () scale, we evaluate a 12B-parameter diffusion model paired with Coppersmith lattice post-processing across 15,523 held-out 68-bit semiprimes, recovering factors on a single test instance (1 candidate per instance) and analyzing the full MSB prefix-match distribution to show that the model captures coarse multiplicative magnitude bounds ( lift over uniform random bit-guessing) while decaying to near-chance accuracy on deeper factor bits.
Related Work
Factorization
The most promising classical factorization algorithms utilize the principle of identifying smooth numbers, which are integers with bounded prime factors ([11]). The Quadratic Sieve (QS) ([37, 38]) aims to discover integers and such that while ensuring , so that would then yield a non-trivial factor of .
The General Number Field Sieve (GNFS) ([4]) replaces the quadratic polynomials utilized in the QS with complex, higher-degree polynomials over algebraic number fields. The problem then becomes finding relations among elements within the ring of integers of a specific number field. During the sieve phase, many smaller integers are then factored to identify smooth relations, which can be achieved via Lenstra’s elliptic-curve factorization method [28].
Fermat’s factorization method presents an alternative approach, which is centered around the idea of representing an odd composite integer as the difference of two distinct squares: . This is highly efficient if the prime factors and are close to the square root of , within the asymptotic bound of [24]. In 1895, Lawrence extended Fermat’s algorithm for scenarios where is not close to 1 [17, 23]. It was shown that if one can deduce an approximation ratio , one can then construct an augmented multiplier and use Fermat’s method to factor quickly. Recently, there has been interest in utilizing Lawrence’s extension to reframe the factorization problem into a binary classification or regression problem [3] for deep learning. In this framing, neural networks are trained to estimate the ratio. While this framing is an easier output specification for neural networks, the performance has not been promising.
Neural Arithmetic
Using neural networks for integer factorization has proven to be challenging, which is due to highly non-smooth optimization landscapes (Veličković et al., 2019) and the hard combinatorial nature of the problem. To overcome these obstacles, Vector Symbolic Architectures (VSA) [15] represent complex sub-symbolic data structures as high-dimensional hypervectors [21]. Fractional Power Encoding (FPE) [13, 35] is frequently used within the VSA framework, involving repeated exponentiation of a base hypervector and binding these to different scalar quantities.
Resonator networks [12, 39] maintain several independent groups of hypervector estimates, and , in superposition, and update them iteratively based on the codebook matrices of possible factor representations. This dynamical system converges to a stable equilibrium state once the correct integer factors are isolated [22].
Diffusion Models
Denoising diffusion models were initially developed primarily for continuous domains [5, 10, 44] (Ho et al. 2020) and have seen extensive applications in image generation [10] (Ulhaq and Akhtar 2022). Gaussian noise is added in the forward pass and then iteratively removed in the learned neural inverse process. Discrete problems were initially approached mainly via standard autoregressive approaches, yet these approaches face difficulties in highly structured problems as an early error in the sequence would invalidate the rest of the solution. Discrete diffusion models help overcome this obstacle [2].
Discrete diffusion models are a good fit for highly structured problems as they couple parallel generation and iterative global refinement. These models are often defined with a Markovian transition matrix, rather than Gaussian noise [19]. Recent theoretical findings, tying the negative Evidence Lower Bound (ELBO) to the data entropy and the path Kullback-Leibler (KL) divergence, suggest that the diffusion loss naturally leads to the model correctly capturing the conditional expectation of the reverse denoising steps [2]. Discrete diffusion has shown great promise in structured domains like graph generation [7, 16, 29] (Vignac et al. 2022).
Recently, discrete diffusion has been experimented with for integer factorization [14]. The idea is to learn a mapping that iteratively corrects errors within partially correct solutions. The neural network is trained to output a clean sample , which is tightly conditioned on the product sequence. The approximation utilizes the full probabilistic information that is retained between steps:
With this approach, the model was able to recover prime factors for numbers up to 56 bits in length [14]. This work also highlighted an inverse exponential relationship between training compute allocation and inference cost: At a specific projected success rate, higher investment in pre-training has been shown to lead to an exponential decrease in the number of discrete sampling steps required.
Method
Data Representation
We formulate the semiprime factorization problem, , as a conditional sequence generation task. Given an integer , the objective is to generate the prime factors and . We represent all integers as binary strings. Assuming the prime factors and are bounded by , being the maximum number of factor bits, the binary representations of and are padded with leading zeros towards a fixed length . Similarly, occupies bits. The employed ordering goes from the Most Significant Bit (MSB) to the Least Significant Bit (LSB).
The input to the model is obtained by concatenating the bit strings for , , , resulting in a total sequence length of . The vocabulary consists of binary tokens , alongside designated mask and padding tokens. During generation, the bits corresponding to are unmasked and act as a fixed prefix. The model is tasked with inferring the subsequent masked bits corresponding to and .
Data Generation
Training examples are generated on the fly using deterministic pseudorandom streams, while excluding pre-generated held-out evaluation sets to prevent pair-level train/test leakage. At initialization, we pre-generate fixed held-out validation and test splits of 1,024 semiprimes each (with a larger 100,000-example held-out test set generated specifically for the 68-bit factorization evaluation in § 4.5); during on-the-fly training example generation, any sampled pair whose product appears in the held-out evaluation splits is rejected and resampled. To sample a factor pair, we draw two random integers uniformly from (without forcing the leading -th bit to 1, so factors have bit-length at most and are zero-padded to length ), advance each to the next prime via gmpy2.next_prime while rejecting primes or equal factors (), sort them so that to break permutation symmetry, and set .
Note that this holdout protocol enforces pair-level disjointness (), ensuring the model never sees a held-out semiprime during training, while drawing training and test pairs from the same underlying pool of primes (). Let denote the number of primes less than or equal to . For small bit-lengths (), a 100,000-step training run at batch size ( examples) makes multiple passes over the non-held-out training pairs (e.g., passes over pairs at , and passes over pairs at ) and exposes each individual prime factor thousands of times (e.g., occurrences per prime across primes at ). We discuss the implications of prime-vocabulary memorization versus pair-level generalization in § 5.
Model Architecture and Self-Conditioned Training
We approach semiprime factorization as a machine learning problem, framed as discrete diffusion over binary token sequences, utilising a bidirectional transformer (Vaswani et al., 2023) denoiser. During training, we use a noise schedule to corrupt the factor bits by replacing a dynamically sampled proportion of their tokens with the mask token, and train the model to reconstruct the clean binary values across all factor positions.
The spatial structure of the forward noising process is critical for learning multi-bit arithmetic dependencies, leading us to adopt contiguous blockwise masking rather than independent bitwise masking. For each training example we sample a noise level from the triangular density on (biasing towards higher noise levels while applying inverse-density importance weighting so the diffusion objective remains unbiased; see Appendix § 6.§ 3) and mask a contiguous block of length in and in , while leaving the prefix bits of unmasked. Masking contiguous spans forces the denoiser to resolve long-range carry propagation and global multiplicative constraints rather than relying on local bit interpolation.
To allow the discrete denoiser to refine its factor estimates across iterations without losing continuous uncertainty information when discretizing to hard tokens , we incorporate a gated feed-forward self-conditioning module (Chen et al., [6]). Rather than feeding only discrete tokens at each step, the model maps its previous step’s vocabulary logits into a continuous probability-weighted embedding over the shared normalized token embedding table , transforms through a zero-bias gated GeLU feed-forward network , and adds the result residually to the discrete canvas token embeddings prior to the first transformer layer (Appendix § 6.§ 2).
Training proceeds via a two-pass self-conditioned rollout on each minibatch (detailed in Appendix § 6.§ 3):
Pass 1 (Unconditioned Proposal): The denoiser is evaluated on the block-masked canvas with an all-zero self-conditioning tensor (and stop_gradient) to produce first-pass logits and soft self-conditioning embeddings .
Concave Canvas Resampling and Pass 2 (Self-Conditioned Update): During iterative inference, the denoiser encounters canvases containing a mixture of masked spans and potentially erroneous discrete bits committed at earlier steps. To match this distribution during training, we sample discrete tokens and overwrite each factor position of (both masked and initially unmasked) independently with probability (; Eq. (10)), forming a resampled canvas . On Pass 2, is retained with probability and zeroed out with probability so that a single parameter update per step trains the model predominantly in the self-conditioned regime while preserving calibration for the initial unconditioned step (). The training objective computes the importance-weighted cross-entropy between the Pass-2 predicted logits and the ground-truth binary tokens across all factor positions of and (Eq. (11)), training the denoiser both to inpaint masked blocks and to correct erroneous discrete tokens committed on unmasked positions.
Test-Time Denoising and Guided Search
At inference time, we consider two distinct decoding procedures that trade off single-trajectory iterative refinement against structured tree search over partial factor prefixes (full mathematical details and a step-by-step worked walkthrough are provided in Appendix § 6.§ 4).
Non-Monotonic Ancestral Block-Diffusion Sampling
Standard ancestral sampling generates a single candidate factorization over discrete steps () following a linearly decaying noise schedule , starting from a fully masked factor canvas () and . Unlike absorptive discrete diffusion samplers that monotonically unmask and freeze one token at a time, our ancestral sampler performs non-monotonic predict-and-remask block refinement. At each step :
The denoiser predicts clean binary logits across all factor bits simultaneously.
The temperature-scaled binary probabilities are converted into the continuous self-conditioning embedding and passed to step .
A complete clean discrete guess is sampled for all bits of and , and two fresh, independently positioned contiguous blocks of width are re-masked at newly sampled random offsets in and .
Because the masked window slides randomly across and at every step while continuous beliefs accumulate in , running steps (e.g., to for ) acts as annealed blocked-Gibbs refinement: bits outside the current mask that were guessed inconsistently at earlier steps can be re-masked and corrected on subsequent steps once neighbouring bits settle. No intermediate arithmetic check (whether ) is performed during the steps; verification occurs only once after step .
Guided Beam Search with Inner Mini-Denoising and Oracle Self-Conditioning
While non-monotonic ancestral sampling can revise earlier bit guesses, it still evolves a single stochastic trajectory without explicit arithmetic verification until the final step. To prevent early bit errors from derailing generation and to exploit deterministic arithmetic constraints during decoding, we replace single-trajectory generation with a two-level guided search procedure over the binary factor tokens (Figure 1 and Figure 2). While we had initially explored Monte Carlo Tree Search (MCTS) with PUCT selection (Silver et al., [42]), we empirically found it to be less effective than maintaining a synchronized frontier via beam search (Lowerre, [30]; Lys et al., [31]) augmented with iterative inner mini-denoising.

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 paths are retained in the beam.
Our procedure couples an outer beam search that commits to discrete factor bits one by one with an inner mini-denoising loop that uses the diffusion model—via a mechanism we term oracle self-conditioning—to calibrate the branching probabilities at each search depth:
Outer Loop (MSB-to-LSB Beam Search): The outer search operates sequentially over the factor positions () by alternating between the MSBs of (even steps , deciding bit ) and the MSBs of (odd steps , deciding bit ). At outer depth , each hypothesis node in the active beam of width partitions the factor positions into a subset of already committed (decided) MSB positions with fixed binary assignments () and a subset of remaining undecided masked positions .
Inner Loop (Mini-Denoising with Oracle Self-Conditioning): Before expanding a node at outer depth to decide the next target MSB , we run a short inner rollout of recurrent denoising passes () to let the diffusion model refine its beliefs over the undecided bits conditioned on the committed prefix . In standard diffusion self-conditioning, the model feeds back its own soft predictions across all factor positions. In oracle self-conditioning (Figure 1), any bit already committed by the outer beam search is treated as ground-truth (“oracle”) knowledge during the inner rollout: decided positions are clamped in the self-conditioning input to their exact one-hot token embeddings ([6]), while undecided masked positions continue to refine soft probability-weighted embeddings across the inner steps.
Even though the output logits at already-decided positions are discarded after the inner loop (since only the logit at the next undecided MSB position is read to expand the tree), clamping to one-hot self-conditioning embeddings is essential because the self-conditioning vector is added to the input canvas embeddings before entering the bidirectional transformer. Through all-to-all self-attention across all layers, every undecided masked position attends directly to the keys and values at decided positions . Injecting the one-hot embedding at both matches the Pass-2 training distribution on unmasked factor tokens and prevents internal conflict between the discrete canvas token and the model’s unconditioned prior when exploring lower-probability branches of the beam (see Appendix § 6.§ 4).
Putting the outer and inner loops together, the guided search proceeds over outer steps across a fixed-size frontier of hypothesis slots as follows (detailed in Appendix § 6.§ 4):
Initialization: At outer step , the frontier is initialized with slots where only slot 0 is marked active (score = 0.0, valid = True) with unmasked and all bits of and set to the mask token (), while slots are marked inactive (score = , valid = False) to prevent duplicate clones at the root. Thus, the number of active hypotheses grows as .
Expansion via Inner Mini-Denoising ( steps): At outer step , for each active candidate in the beam, we execute the inner mini-denoising loop (). Unlike ancestral sampling, the discrete canvas is held completely fixed throughout the inner loop (decided positions retain their committed tokens , undecided positions remain masked, and no re-masking occurs); only the continuous self-conditioning tensor evolves from by repeatedly merging the fixed one-hot oracle embeddings on with the refining soft predictions on (Figure 1). After inner passes, the calibrated binary log-probabilities at the target MSB position are used to expand each active parent into two child branches (), yielding up to candidate states.
Arithmetic Interval Feasibility Pruning: Because bit expansion proceeds from MSB to LSB, any partial assignment of prefixes and defines deterministic integer lower and upper bounds on each factor by setting all undecided lower bits in to 0 () or 1 (), respectively. Any child branch whose target semiprime falls outside the feasible product interval, i.e., , is immediately pruned by setting its score to (Figure 2).
Top- Selection: The remaining feasible children across all candidates are ranked by their cumulative log-probabilities, and the top candidates are retained to form the active frontier for outer step .
At the final depth (), and , so interval feasibility pruning reduces to exact multiplicative verification . If all branches become infeasible prior to reaching the final depth, the search terminates early and returns the highest-log-probability partial MSB prefix for lattice-based post-processing.
Post-Processing
Optionally, we perform post-processing of the ML predictions via Coppersmith’s algorithm [9]. Based on the Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm [26], Coppersmith’s method can efficiently find small roots of modular polynomial equations. In the context of semiprime factoring, Coppersmith’s theorem states that if at least half of the MSBs of either prime factor are known, the remaining unknown bits can be recovered in polynomial time.
Consequently, for a factorization to be successful, it is not strictly necessary for either the model or the test-time search to generate a fully accurate factorization, if the generated candidate is approximately correct with a sufficient degree of accuracy. Coppersmith’s method can complement the ML approaches to deterministically resolve the remaining bits.
Test-Time Scaling Laws
Given that scaling test-time compute is now seen as one of the primary directions for enhancing complex problem-solving capabilities in AI models [8, 43], our focus here was to not only develop scaling laws for discrete diffusion models in pretraining when attempting to solve the integer factorization problem, but perhaps even more importantly, understand the test-time scaling properties and the conditions under which beam search can help improve the factorization success rate at different levels of complexity, and for different levels of quality of the underlying diffusion model. Test-time scaling is particularly appealing in domains where verification remains easier than generation, making integer factorization a good match for the overall approach.
Given that the optimal test time compute allocation strategy depends, in principle, on the difficulty distribution across samples, uniform allocation is highly ineffective when that distribution is fairly mixed. In our case, however, we presume that we are solving a problem at a particular (fixed) bit-length, and since the factors themselves are sampled to be large, the intrinsic factorization difficulty remains fairly uniform, at each specific bit-length. We are therefore not concerned with adaptively allocating compute per-example, rather aiming to understand how much test-time compute is required in expectation to successfully factor numbers at increasing bit-lengths, for varying quality of the underlying model, expressed in its denoising negative log-likelihood. We evaluate both axes of test-time compute scaling empirically: scaling the denoising step budget of single-trajectory ancestral diffusion on long-horizon checkpoints in § 4.3 (Table 1 and Figure 5–Figure 6), and scaling the beam search frontier width with oracle self-conditioning across pre-training stages in Appendix § 8.§ 5 (Figure 16–Figure 18).
| Factor Bits | 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, ) across denoising step budgets . Models: 325M trained for 100k steps at , 325M trained for 348k steps at , and 12B trained for 109k steps at .

Figure 5. Log-linear scaling of single-trajectory ancestral solve rate with inference denoising steps across training horizons (30k, 100k, 1M steps) for a 325M model at 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 16. Test-Time Compute Scaling across Pre-Training Checkpoints. Exact factorization mean as a function of max search frontier size (, labeled on the horizontal axis; scale) across factor bit-lengths (, greedy decoding temperature , labeled ). Subplots denote pre-training progression (fraction complete ). Test-time search scaling yields monotonic performance gains, with larger frontier budgets partially compensating for earlier checkpoint maturity.

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 () bits, greedy decoding . Colored curves represent pre-training checkpoint stages (0.25 to 1.00). Note independent - and -axes per subplot. Within each fixed problem hardness, expanding test-time search compute demonstrates predictable efficiency scaling.
Results
Here we present a variety of empirical scaling laws for semiprime factorization using discrete diffusion models along the dimensions of data, model size, problem size, and test time compute. Additional plots, including those measured in terms of train time compute, are shown in the appendix.
Data
In Figure 3, we plot validation loss against training steps (which is equivalent to data seen, since all models use the same batch size).1 We see that the loss curves exhibit power law behavior. Unlike natural language, since prime factorization is a noiseless problem, it is no surprise that the y-intercepts of the fitted power laws can and often are 0. Importantly, because validation NLL averages over all factor positions (both masked and unmasked) across noise levels with importance weights , a non-factoring local-arithmetic baseline—which simply copies visible unmasked bits and propagates revealed MSB/LSB prefixes and suffixes across mismatched mask offsets without global factoring (derived in Appendix § 6.§ 3.1)—already achieves an importance-weighted validation NLL . Consequently, validation NLL values above reflect learning token copying and local carry/division consistency on partially unmasked canvases, whereas genuine factorization emerges only once validation NLL drops below .

Figure 3. Validation negative log-likelihood (NLL) across training steps (with power-law fits ) for the 325M model across factor bit-lengths .
Model Size
In Figure 4, we plot validation loss curves against train steps for three model sizes (325M, 1B, 2B) across a range of factor bits. The decrease in the final loss value with model size is a bit noisy: while 2B is always (tied) for the best, the relationship between 325M and 1B is inconsistent, where which one has the lowest loss changes across factor bits.

Figure 4. Validation NLL across training steps for three model sizes (325M, 1B, and 2B), faceted by factor bit-length .
Inference-Time Scaling
Here, we analyze how the performance of standalone single-trajectory ancestral diffusion (§ 3.4.1; temperature , no beam search, oracle self-conditioning, or Coppersmith post-processing) scales with the number of inference-time denoising steps (beam search frontier scaling is analyzed separately in Appendix § 8.§ 5, Figure 16–Figure 18). As detailed in § 3.4.1 and Appendix § 6.§ 4.1, the ancestral sampler performs no intermediate arithmetic check () during the steps; instead, scaling improves solve rate via non-monotonic blocked-Gibbs refinement as fresh contiguous blocks of width are repeatedly re-masked and re-evaluated against the evolving soft self-conditioning state.
Table 1 reports single-trajectory exact factorization accuracy on the held-out test set (1,024 semiprimes) across for three trained checkpoints: a 325M model trained for 100,000 steps at , a 325M model trained for 347,800 steps at , and a 12B-parameter model trained for 109,000 steps at . Whenever a model factorizes a non-zero fraction of held-out semiprimes at , accuracy improves roughly log-linearly with ; conversely, models with zero accuracy at low budgets () show no exact-factorization gains up to . For comparison at , trial division over odd candidates up to guarantees success in at most divisions.
In Figure 5, we illustrate this log-linear relationship across training horizons (30k, 100k, and 1M steps) on an initial (325M) baseline trained with pointwise token corruption prior to introducing contiguous blockwise masking and two-pass concave rollout resampling; better-trained checkpoints exhibit steeper test-time scaling slopes. Figure 6 evaluates checkpoints trained with our final blockwise-masking and two-pass rollout recipe (reaching accuracy at steps within 100k training steps for ) and demonstrates across model sizes and bit-lengths that single-trajectory solve rate at fixed is tightly governed by validation NLL. Notably,
solve rate in Figure 6 remains identically zero for all checkpoints with validation NLL and rises sharply only after NLL penetrates below —matching the exact theoretical NLL floor of our non-factoring local-arithmetic baseline (Appendix § 6.§ 3.1).
Problem Size
Our prime factorization setup gives us another dimension for which to analyze scaling: problem size (factor bits). Despite favorable scaling laws for data and test-time compute, we encounter a hurdle with problem size. In Figure 7, we plot loss curves for Flash 325M trained on factor bits 15, 16, 17, 18. What we see is roughly a geometric relation between factor bits and a given loss value below the non-factoring local-arithmetic threshold (Appendix § 6.§ 3.1); each increase in factor bit requires roughly a increase in training steps to achieve a given loss value. This trend suggests that data requirements scale exponentially in factor bits, i.e. linearly in the size of the problem. If this trend holds, this suggests that our diffusion model is unable to exploit substructure from a sparse amount of data, and requires seeing a large fraction of semiprime examples in order to perform well. In essence, our modeling component scales similarly to brute force methods.

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.
Evaluation at 68 Bits () with Coppersmith Post-Processing
To probe the upper boundary of our training recipe, we trained a 12B-parameter diffusion model at factor bits for 109K steps at batch size ( training examples, a negligible fraction of the distinct 34-bit-bounded semiprimes). As shown in Table 1, standalone ancestral sampling achieves 0% factorization at even with denoising steps. However, Coppersmith’s lattice-reduction method (§ 3.5) requires a candidate factor to match only the leading MSBs to recover the remaining 16 bits in polynomial time.
For this 68-bit experiment, we evaluated across a 100,000-example held-out test split using single-trajectory ancestral diffusion ( denoising steps, , without beam search), generating one candidate pair per test instance and running Coppersmith reduction (18-bit prefix) on and (2 factor candidates tested per instance). Because our data generator samples primes without forcing the 34-th bit to 1 (§ 3), 25,228 of the 100,000 held-out instances have two full 34-bit prime factors (), and 15,523 instances are strict 68-bit semiprimes ().
Out of the 15,523 strictly 68-bit held-out semiprimes, Coppersmith post-processing succeeded on 1 instance (0.0064%; 1/25,228 = 0.0040% across all pairs with two 34-bit factors), factoring
where matched the leading 19 18 MSBs of (and matched 8 MSBs of ).
To assess statistical significance against random prefix coincidence, Table 2 compares the model’s empirical MSB match distribution across all 15,523 full 68-bit instances against two non-factoring baselines: (A) naive independent uniform bit-guessing in , and (B) a zero-learning hyperbola magnitude prior. Because any valid ordered factor pair of with must satisfy and lie on the rectangular hyperbola , the hyperbola prior simply draws uniformly at random from the valid integer interval and sets by division. Across intermediate prefix lengths (), the 12B denoiser consistently matches leading prefixes at the rate of naive uniform bit-guessing (e.g., 189 vs. 60.6 expected matches at , ). Comparing against the hyperbola prior reveals the source of this lift: roughly 2.5 arises purely from restricting to the product hyperbola with , with a modest additional concentration over uniform hyperbola sampling (189 vs. 151.8 at $m \geq 10). Beyond bit , however, each additional bit halves the empirical survival rate ( per bit), mirroring random guessing on deeper factor bits. Consequently, at the Coppersmith threshold , a single observed hit across 15,523 single-sample trials (compared to 0.24 expected under naive uniform guessing and 0.62 under the hyperbola prior) reflects tail sampling from a magnitude-calibrated prior rather than reliable 68-bit algorithmic factorization—consistent with our exponential scaling law.
| MSBs () | 12B Count | 12B Rate | Uniform Prior | Hyperbola Prior |
| 15,489 | 99.78% | 75.00% (11,642.3) | 100.00% (15,523.0) | |
| 7,957 | 51.26% | 23.44% (3,638.2) | 47.84% (7,426.9) | |
| 2,526 | 16.27% | 6.15% (955.0) | 14.74% (2,288.4) | |
| 701 | 4.516% | 1.556% (241.6) | 3.924% (609.2) | |
| 189 | 1.218% | 0.390% (60.6) | 0.978% (151.8) | |
| 49 | 0.316% | 0.098% (15.2) | 0.238% (37.0) | |
| 14 | 0.090% | 0.024% (3.8) | 0.059% (9.1) | |
| 5 | 0.032% | 0.0061% (0.95) | 0.0142% (2.20) | |
| 1 | 0.0064% | 0.0015% (0.24) | 0.0040% (0.62) | |
| 1 | 0.0064% | 0.0008% (0.12) | 0.0020% (0.31) |
Table 2. Empirical leading-MSB prefix match distribution for the 12B model at (1 ancestral sample per instance, , across held-out 68-bit semiprimes with ), compared against (A) naive uniform random bit-guessing on 2 factor candidates with fixed leading bit 1 , and (B) a zero-learning hyperbola magnitude prior that samples a random point on the product hyperbola with by drawing uniformly from the valid integer interval and setting .
Conclusion
Through our experiments, we have identified several key insights. At small bit lengths (), our models are able to reach high semiprime factoring performance. Our training setup rules out direct memorization, leading us to conclude that the denoiser can learn to successfully solve the task given sufficient training data. Due to the overlap in the constituent prime factor pool that is used to derive semiprimes for training and testing, the model benefits from having encountered the same factors previously in different numbers. The size of this prime factor vocabulary scales as . This scaling aligns with our empirical finding that achieving a target validation loss requires a multiplicative growth in training data and compute () for each added factor bit. Our scaling results also indicate that the model fails to uncover any polynomial or sub-exponential factoring algorithm, scaling approximately as a kind of learned brute force search.
It is instructive to contrast this performance with the scaling dynamics arising in natural language modeling, where smooth power-law scaling and length generalization occur. This generalization stems from a rich, hierarchical, and locally constrained structure that the model is able to learn and exploit. In contrast, semiprime factorization is globally coupled and cryptographically pseudorandom; a single bit-flip in the semiprime number has discontinuous, chaotic effects on its factors. The lack of reusable local substructure makes it virtually impossible for a diffusion model to generalize from -bit instances to -bit instances without a prohibitive, exponential increase in data.
Finally, our 68-bit MSB distribution analysis reveals that while the denoiser reliably learns coarse multiplicative magnitude bounds ( prefix-match lift over naive random bits), its accuracy on deeper bits decays at near-chance rates. We therefore conclude that direct bit-prediction ML methods pose no present or future threat to RSA cryptography.
Architectural, Training, and Test-Time Search Details
In this appendix, we detail the input representations, self-conditioning architecture, importance-weighted diffusion training objective, and test-time beam search with oracle self-conditioning used in our experiments. We are unable to provide full architectural details, since we used proprietary Flash models as our transformer-based diffusion model.
Canvas Representation
Each factorization instance consists of a -bit semiprime and its two -bit prime factors , serialized into a single sequence (or canvas) of length :
where denotes the discrete token vocabulary containing binary bit tokens , the absorbing mask token, and the pad token (). Let denote the prefix offset corresponding to the conditioned semiprime .
Token Embedding Normalization. Let denote the learnable token embedding table with model dimension . Each row of is projected onto the unit Euclidean () sphere (, corresponding to root-mean-square ):
For a discrete noisy canvas , the raw token embeddings are scaled by upon lookup so that each token embedding has Euclidean norm (unit root-mean-square):
where is the one-hot encoding of .
Self-Conditioning Architecture
To allow the discrete diffusion denoiser to refine its factor estimates across iterations without losing continuous uncertainty information when discretizing to hard tokens, we incorporate a gated feed-forward self-conditioning module.
Soft-Logit Embedding. Given unnormalized vocabulary logits produced by a preceding denoising pass, we compute a continuous probability-weighted embedding over the shared normalized token embedding table :
Given that and project onto the exact same normalized basis , a degenerate (one-hot) probability distribution in Eq. (4) recovers the exact discrete token embedding in .
Prefix Zeroing and Gated FFN Transformation. Because the first positions correspond to the known semiprime , the self-conditioning module first masks out the prefix positions:
Rather than concatenating with the canvas representations along the channel dimension, is transformed by a dedicated pre-normalized gated GeLU feed-forward network (FFWSubBlock) with hidden expansion dimension and zero bias:
where and are learnable projection matrices and denotes elementwise multiplication. Because all linear projections in Eq. (7) are bias-free and , any zero vector in (such as the -bit prefix , or the entire self-conditioning tensor on the first denoising step) maps identically to .
Residual Combination and Output Normalization. The transformed self-conditioning signal is combined with the pre-normalized canvas embeddings from Eq. (3) via elementwise residual addition, followed by a scale-free RMSNorm layer before entering the -block bidirectional transformer trunk:
After passing through the bidirectional transformer layers, the final hidden states are unembedded via transposed projection against with tanh logit soft-capping () to yield the output logits. Note that the transformer denoiser takes no explicit scalar timestep or noise-level embedding ; instead, it infers the current progress of decoding directly from the spatial pattern of mask tokens on and the sharpness of the continuous self-conditioning embeddings .
Two-Pass Training Rollout and Noise-Level Loss Weighting
Importance-Weighted Noise Sampling and Blockwise Masking. During training, each example in a minibatch is assigned a noise proportion with . To reduce gradient variance without biasing the diffusion objective, we employ importance sampling with a triangular proposal distribution on . Specifically, we draw and set via inverse-transform sampling, pairing each example with its inverse-density importance weight:
Given , the forward masking process leaves the semiprime prefix intact and masks two independently positioned contiguous blocks of deterministic length starting at uniformly sampled bit offsets within and , respectively, yielding the corrupted canvas .
Two-Pass Self-Conditioning Rollout with Concave Canvas Resampling. Standard self-conditioning [6] randomly chooses with 50% probability whether to run a single unconditioned pass () or a two-pass self-conditioned rollout. In our pipeline, we instead execute a two-pass rollout on every training step so that Pass 2 can simultaneously train self-conditioning and expose the denoiser to partially resampled discrete canvases:
Pass 1 (Unconditioned Proposal): With dropout disabled, the denoiser is evaluated on with an all-zero self-conditioning tensor , producing first-pass logits . No parameter gradients are backpropagated through Pass 1.
Soft Self-Conditioning and Concave Canvas Resampling: We compute the soft self-conditioning embeddings via Eq. (4). In addition, during iterative test-time inference and beam search, the denoiser must operate on canvases containing a mixture of masked tokens and partially committed discrete predictions (some of which may be erroneous guesses from earlier steps). To simulate this regime during training, we sample discrete tokens and replace each factor position of (across both masked positions and initially unmasked ground-truth factor positions) with independently with a concave noise-dependent probability:
forming the resampled canvas . Note that vanishes at and peaks at when . Overwriting both masked and unmasked factor bits teaches Pass 2 not only to inpaint mask tokens using , but also to detect and correct erroneous discrete bit commitments on the canvas.
Pass 2 (Self-Conditioned Update with 1% Unconditioned Dropout): Because parameter gradients are computed exclusively on Pass 2, always passing would leave the denoiser untrained for the initial inference step , where no prior prediction exists (). Therefore, on Pass 2, is retained with Bernoulli probability and zeroed out () with probability . The denoiser then predicts second-pass logits from .
Importance-Weighted Cross-Entropy Loss. Only Pass 2 contributes to the parameter gradient. The batch loss is computed as the self-normalized importance-weighted cross-entropy:
Non-Factoring Local-Arithmetic Baseline
Because Eq. (11) and validation token accuracy are averaged across all factor positions of and —including both masked and unmasked positions—at noise levels on , a model with zero global factoring ability can still achieve a low validation NLL and high per-token accuracy. Specifically, consider an idealized non-factoring local-arithmetic baseline operating on a partially masked canvas that applies only three elementary local rules without attempting to factor :
Copying visible unmasked factor bits ( of all factor positions): At noise level , a contiguous block of width is masked in and in , leaving the remaining fraction of factor bits unmasked on . Under the triangular proposal on , the expected masked fraction is
meaning () of the factor bits are already visible on the input canvas. Even a pure token-copying baseline that copies the visible of bits (NLL , Accuracy ) and predicts 50/50 coin flips (NLL , Accuracy ) on the masked of bits already achieves unweighted NLL and Accuracy .
Odd parity on the two LSBs: Every prime is odd, so the least significant bits and are deterministically 1 even when covered by the mask.
Cross-factor MSB division and LSB modular multiplication across mismatched mask offsets: Because the contiguous mask starting offsets are drawn independently in and , the masked spans and rarely align:
LSB suffix propagation (): Whenever the mask in extends bits closer to the LSB than the mask in (or vice versa), the lowest bits of are unmasked while the corresponding lowest bits of are masked. Since odd primes are invertible modulo , schoolbook multiplication and carry propagation uniquely determine those masked LSBs of .
MSB prefix propagation (): Symmetrically, whenever , the leading MSBs of are visible while bits of are masked; long division of by the visible prefix of deterministically resolves the corresponding masked MSBs of (up to boundary carry).
For two independent uniform draws on , the expected offset mismatch is bits on the MSB side and bits on the LSB side, allowing local cross-factor arithmetic to deterministically resolve an additional – of all factor positions. On all remaining positions where both and are simultaneously masked beyond local carry reach, the baseline predicts a 50/50 coin flip (NLL , Accuracy ).
Integrating this non-factoring predictor over on (including the Pass-2 concave token replacement of Eq. (10)) yields two exact reference benchmarks corresponding to the two validation weighting conventions used across our figures:
Importance-Weighted Validation (, Main-Text Figure 3, Figure 4, Figure 6, and Figure 7): Multiplying each example by cancels the proposal density and heavily upweights low-noise examples (, where nearly all factor bits are unmasked and locally recoverable), yielding:
This explains the sharp phase transition in Figure 6: every checkpoint with weighted validation NLL has 0.0% exact solve rate, and non-zero factorization emerges only once validation NLL penetrates below 0.262.
Unweighted Validation (, Appendix § 8 Figure 8–Figure 15): Evaluating over on with unit weights yields:

Figure 8. IsoFLOP smile curves for , demonstrating the trade-off between final validation NLL (left) and final validation accuracy (right) against model parameters for fixed compute budgets.

Figure 15. Validation NLL versus cumulative training tokens (linear scale) for the 325M parameter model.
This explains why models at large bit-lengths () in Figure 8–Figure 15 plateau at NLL – and Accuracy : achieving 73.2% validation bit accuracy reflects mastering token copying and local MSB/LSB carry propagation on partially unmasked canvases, while still guessing 50/50 on the unfactored core.
Test-Time Denoising, Beam Search, and Oracle Self-Conditioning
Here we provide a full specification of our two test-time decoding procedures: single-trajectory non-monotonic ancestral sampling and guided MSB-to-LSB beam search with oracle self-conditioning.
Non-Monotonic Ancestral Block-Diffusion Sampling
Given a -step inference budget (), ancestral sampling initializes the canvas with the bits of unmasked and all factor bits of and set to the mask token (), alongside an all-zero self-conditioning tensor . At each step , with incoming noise level and target next-step noise level , the sampler executes four operations:
Denoising Forward Pass: The transformer denoiser evaluates to produce vocabulary logits .
Binary Logit Shaping and Temperature Scaling: To prevent the sampler from proposing non-binary tokens (mask or pad) at factor positions, we form shaped logits by setting the logits of all non-binary vocabulary entries to and scaling by sampling temperature :
Soft Self-Conditioning Update: The continuous self-conditioning tensor for step is computed from the shaped binary logits via Eq. (4): .
Full Factor Sampling and Fresh Contiguous Block Re-Masking: We sample a complete clean discrete factor hypothesis across all factor positions simultaneously: for (keeping ). If (), the sampler returns without re-masking. Otherwise (), rather than keeping previously unmasked bits frozen, the sampler applies the forward contiguous block-masking kernel at target noise level to . Specifically, at inference time we use deterministic floor rounding with a single-bit minimum floor:
draw two fresh, independent uniform block offsets , and replace the contiguous spans in and in of with the mask token to form .
Why Scaling Improves Accuracy Without Intermediate Verification. In standard absorptive discrete diffusion where one masked token is permanently unmasked per step, the process terminates after steps unless an external verifier restarts failed trajectories. By contrast, in our non-monotonic predict-and-remask sampler, no arithmetic check is ever performed during the steps. When (e.g., for ), the deterministic block width in Eq. (15) remains constant for consecutive steps before decrementing by 1. Across those steps, the masked window of width slides to newly sampled random offsets at every step while the continuous embedding carries forward the full probability distribution over at all factor bits. Consequently, any factor bit that was guessed inconsistently at an earlier step is repeatedly re-masked and re-evaluated in the context of updated beliefs elsewhere on the canvas. In particular, during the final steps where , Eq. (15) clamps , so the sampler executes steps of single-bit random-scan blocked-Gibbs refinement over and before final readout at .
Outer MSB-to-LSB Beam Search with Inner Mini-Denoising
While non-monotonic ancestral sampling refines a single trajectory, it can still be trapped in local modes when early high-order bit guesses are mutually inconsistent with . Guided beam search replaces single-trajectory sampling with a two-loop algorithm: an outer tree-search loop over that permanently commits one factor bit per step from MSB to LSB, and an inner mini-denoising loop of recurrent self-conditioning steps that estimates calibrated branching probabilities for the next undecided bit.
Alternating MSB-to-LSB Expansion Schedule and Frontier Initialization. Let and denote the bits of each factor ordered from MSB (, weight ) to LSB (, weight ), occupying canvas indices and , respectively. The outer loop alternates between factors at each depth :
After outer steps, every node in the beam shares the same set of decided canvas positions () and undecided masked positions ().
To maintain fixed tensor shapes of batch size on accelerators without evaluating duplicate root nodes at early depths, the frontier at is initialized with slots, for , where every slot contains followed by mask tokens, but only slot 0 is marked active:
Because invalid slots carry score , their children are automatically discarded during top- selection. Thus, at only slot 0 expands into 2 valid children (); at those valid states expand into valid children, and the active frontier grows as .
Inner Mini-Denoising Loop (): Frozen Canvas, Recurrent Self-Conditioning. At outer step , before branching on position , we run an inner loop of steps () on each beam slot's partial canvas . In sharp contrast to ancestral sampling, there is no re-masking or token sampling inside the inner loop:
The discrete input canvas remains completely frozen across all : positions hold their committed bits , and positions remain set to the mask token. Thus, the discrete fraction of masked factor tokens is constant at .
At , the inner rollout initializes and evaluates the denoiser to obtain initial logits .
For each subsequent inner step , the model constructs the oracle self-conditioning tensor by clamping all search-decided positions to their exact one-hot token embeddings while feeding back the temperature-scaled soft binary predictions at undecided positions :
After forward passes, we read out the binary log-probabilities for solely at the next target MSB position .
Why Clamping Decided Positions in Oracle Self-Conditioning Matters. A natural question is why Eq. (18) must explicitly inject the non-zero one-hot embedding at already-decided positions , given that (i) the discrete canvas already contains at position , and (ii) the output logits at are discarded after the inner loop. The reason is that modifies the input to layer 0 of the bidirectional transformer via (Eq. (8)). Because every transformer block applies bidirectional all-to-all self-attention across all positions, every undecided masked position attends directly to the keys and values produced at the decided positions :
Matching the Pass-2 Training Distribution: During Pass 2 of training (Appendix § 6.§ 3), unmasked factor positions carry both their discrete token embedding and a sharp, near-one-hot self-conditioning vector . If we instead passed at decided positions for , the layer-0 representation at would remain (a Pass-1 representation) while undecided positions would carry Pass-2 representations , creating a distribution mismatch across the attention context.
Enforcing Branch Consistency on Lower-Probability Beams: When beam search explores a branch that committed to a lower-probability bit assignment (e.g., , so the branch committed to while the model’s unconditioned Pass-1 logit at position still favours with probability $0.8), standard soft self-conditioning would feed a vector weighted 80% toward “1” into , directly contradicting the discrete canvas token (“0”). Clamping to the exact one-hot embedding of forces both the canvas pathway and the self-conditioning pathway to agree unanimously on the branch commitment .
Arithmetic Interval Feasibility Pruning. When each active beam hypothesis expands at position into two children assigning and with updated cumulative log-probability , the committed MSB prefixes define closed integer intervals and for the two factors:
Because , any completion of the undecided bits in must yield a product in . Thus, a child hypothesis is arithmetically feasible if and only if
Any child violating Eq. (21) is immediately pruned by setting and marking before selecting the top children for outer step .
Worked Example Walkthrough of Beam Search and Oracle Self-Conditioning
To make the interplay between the outer search loop, the -step inner loop, oracle self-conditioning, and arithmetic interval pruning concrete, consider factoring the 8-bit semiprime with factor bits (, , and ), beam width , and . The canvas has length :
(indices 1...8) (indices 9...12) (indices 13...16)
where have bit value , have value , have value , and have value .
Initialization (). The frontier has slots with and all 8 factor bits masked (M):
Slot 0: , , .
Slot 1: , , .
Outer Step (Deciding MSB at Canvas Index ).
Inner Mini-Denoising (): Throughout all 5 inner passes, the discrete canvas stays frozen with all 8 factor positions masked. At , , producing initial soft probabilities (say ). Since , for the oracle self-conditioning tensor simply feeds back the evolving soft embeddings at all 8 masked factor positions, sharpening the marginal belief at to, say, and .
Branching and Feasibility Pruning: Expanding Slot 0 on (while Slot 1’s children inherit score ) yields two active candidate children with :
Top-2 Selection: Slot 0 becomes [10001111 ∥ 1 M M M ∥ M M M M] (score = , valid = True), and Slot 1 remains invalid (score = ).
Outer Step (Deciding MSB at Canvas Index ).
Inner Mini-Denoising with Oracle Self-Conditioning (): Now () and . On every inner step , Eq. (18) clamps index 9 of to the exact one-hot embedding , while indices receive soft probability-weighted embeddings. After 5 inner passes, suppose and .
Branching and Feasibility Pruning: Expanding Slot 0 on :
Child A (): and , so (pruned).
Child B (): and , so (valid, cumulative score ).
Top-2 Selection: Slot 0 holds [10001111 ∥ 1 M M M ∥ 1 M M M] (score = , valid = True).
Outer Step (Deciding Second MSB at Canvas Index ).
Inner Mini-Denoising (): Now () are both clamped to one-hot embeddings in , while the 6 undecided bits refine their soft embeddings. Suppose after the model predicts and .
Branching and Feasibility Pruning: Expanding Slot 0 on :
Child A (): and , giving product interval (valid, score ).
Child B (): and , giving product interval (also valid, score ).
Top-2 Selection: Both children satisfy Eq. (21), so for the first time both slots of the beam become active: Slot 0 tracks the prefix and Slot 1 tracks the alternative prefix . Notice how at , when evaluating Slot 1 (where $p_1^* = 0 was chosen against the model’s 0.65 preference for ), clamping index 10 of to the one-hot embedding of “0” forces the inner mini-denoising loop to compute the distribution of conditioned on (which requires since $11 \times 11 = 121 < 143$), rather than leaking the model’s unconditioned preference for .
Continuing through outer step (), the interval bounds collapse to a single point and , where Eq. (21) verifies .
Supplementary Power-Law Results
Optimal Compute Allocation
To establish the optimal compute allocation in terms of model size and training tokens, we conducted an IsoFLOP analysis for the bit-length factorization task. Figure 8 shows the characteristic smile curves. The minima of these curves correspond to the compute-optimal model size for a given
FLOP budget. At these compute-optimal minima ( parameters), scaling the FLOP budget from to pushes validation NLL down from to (and validation accuracy up from to ), penetrating well below the unweighted non-factoring local-arithmetic baseline (NLL , Accuracy ; see Appendix § 6.§ 3.1). Conversely, on the right-hand branch of the smile curves ( parameters), over-allocating FLOPs to model parameters at the expense of training steps leaves the largest models token-starved near the NLL / Accuracy non-factoring baseline.
Impact of Factor Bit-Length
Note on the differences loss scale and step budget vs Figure 4: The main-text trajectories were trained for a fixed 100,000 steps with inverse-PDF noise-level importance weighting, whereas the Appendix sweeps use uniform example weighting across sampled noise levels and scale the training step budget as .
Figure 9 illustrates the increasing difficulty of the integer factorization problem as the number of factor bits increases. The final validation NLL increases and the final validation accuracy drops when factoring larger numbers. Because validation NLL and accuracy in Figure 8–Figure 15 average over all factor bits under with unit weights (Appendix § 6.§ 3.1), the plateau at NLL – and Accuracy – for in Figure 9 corresponds directly to the non-factoring local-arithmetic baseline of Eq. (13) (NLL , Accuracy ). At these larger bit-lengths and short step budgets ( steps), the models learn token copying, odd-parity LSBs, and local multiplicative/divisive consistency across partially unmasked factor spans, but make negligible progress on global factorization; genuine factoring capability emerges only once validation NLL penetrates substantially below this 0.375 floor (as seen at , where NLL reaches 0.360 and beam search solves of test instances in Figure 16).
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.
Here we present extended empirical results illustrating the model training dynamics and the power law fits, complementing the results in the main text.
Fitting Individual Trajectories
The faceted per-trajectory power-law fits for the 2B model are shown in Figure 10 and for the 325M model in Figure 11. The empirical validation NLL is fitted to the functional form , where represents the cumulative training tokens.

Figure 10. Faceted per-trajectory power-law fits for the 2B parameter model across factor bit-lengths to . 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 to .
The theoretical fit closely matches the empirical data across all evaluated bit-lengths. This indicates that the power-law decay consistently holds at the individual trajectory level. Note that for , the fitted asymptotes (Figure 11) reflect rapid power-law convergence toward the non-factoring local-arithmetic floor (Appendix § 6.§ 3.1) over the short sweep horizon, rather than convergence toward zero-loss factorization.
Training Dynamics
Figure 12 and Figure 13 show the log-log scaling trajectories of validation NLL versus cumulative training tokens for the 2B and 325M parameter models across factor bit-lengths . The validation NLL decay holds across different model scales, maintaining a linear trend in log-log space.
Figure 12. Validation NLL versus cumulative training tokens on a log-log scale for the 2B parameter model across factor bit-lengths to .

Figure 13. Validation NLL versus training tokens on a log-log scale for the 325M parameter model across various factor bit-lengths.
Figure 14 and Figure 15 present the validation NLL against cumulative training tokens on a standard linear scale for the 2B and 325M models respectively. While these plots clearly show the rapid initial improvement and the long-tail convergence as training progresses, the underlying power-law relationships are heavily compressed. This visualizes why log-log representations are necessary to properly analyze the scaling behavior and extrapolate future performance.

Figure 14. Validation NLL versus cumulative training tokens (linear scale) for the 2B parameter model.
Beam Search Frontier Scaling Across Pre-Training Stages
Figure 16–Figure 18 evaluate beam search with oracle self-conditioning and MSB-to-LSB interval feasibility pruning (§ 3.4; inner mini-denoising steps, greedy expansion, and frontier widths ) across on 1,024 held-out test semiprimes per configuration. Unlike Table 1—which evaluates long-horizon checkpoints (100k–348k training steps) using single-trajectory ancestral sampling—Figure 16–Figure 18 evaluate intermediate and final checkpoints (completion fractions 0.25, 0.50, 0.75, 1.00) from the short-horizon 2B difficulty-scaling sweep of Appendix § 8.§ 2, where total training steps scale as (i.e., only 2,500 steps at and 5,000 steps at ). Even on these lightly trained checkpoints (validation NLL at and at ), expanding the search frontier from to increases exact factorization accuracy from to at and at , whereas checkpoints stuck on the non-factoring validation plateau () remain at 0% across all tested beam widths.

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 , labeled ; greedy decoding . Colored lines denote factor bit-length . As pre-training matures, higher search budgets unlock substantially steeper performance trajectories compared to constrained search .
References
- [2]J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in neural information processing systems, 34:17981–17993, 2021.
- [3]S. Blake. Integer factorisation, Fermat & machine learning on a classical computer. arXiv preprint arXiv:2308.12290, 2023.arxiv.org/abs/2308.12290
- [4]J. P. Buhler, H. W. Lenstra Jr, and C. Pomerance. Factoring integers with the number field sieve. In The development of the number field sieve, pages 50–94. Springer, 2006.
- [5]H. Cao, C. Tan, Z. Gao, Y. Xu, G. Chen, P.-A. Heng, and S. Z. Li. A survey on generative diffusion models. IEEE transactions on knowledge and data engineering, 36(7):2814–2830, 2024.DOI
- [6]T. Chen, R. Zhang, and G. Hinton. Analog bits: Generating discrete data using diffusion models with self-conditioning, 2023a. URL https://arxiv.org/abs/2208.04202.
- [7]X. Chen, J. He, X. Han, and L.-P. Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. arXiv preprint arXiv:2305.04111, 2023b.arxiv.org/abs/2305.04111
- [8]Y. Chen, X. Pan, Y. Li, B. Ding, and J. Zhou. Provable scaling laws for the test-time compute of large language models. Advances in Neural Information Processing Systems, 38:167074–167108, 2026.arxiv.org/abs/2411.19477
- [9]D. Coppersmith. Finding a small root of a univariate modular equation. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 155–165. Springer, 1996.DOI
- [10]F.-A. Croitoru, V. Hondru, R. T. Ionescu, and M. Shah. Diffusion models in vision: A survey. IEEE transactions on pattern analysis and machine intelligence, 45(9):10850–10869, 2023.DOI
- [11]J. D. Dixon. Asymptotically fast factorization of integers. Mathematics of computation, 36(153):255–260, 1981.DOI
- [12]E. P. Frady, S. J. Kent, B. A. Olshausen, and F. T. Sommer. Resonator networks, 1: An efficient solution for factoring high-dimensional, distributed representations of data structures. Neural computation, 32(12):2311–2331, 2020.DOI
- [13]E. P. Frady, D. Kleyko, C. J. Kymn, B. A. Olshausen, and F. T. Sommer. Computing on functions using randomized vector representations (in brief). In Proceedings of the 2022 Annual Neuro-Inspired Computational Elements Conference, pages 115–122, 2022.DOI
- [14]Freivalds, Kārlis and Ozoliņš, Emīls and Bārzd̅iņš, Guntis. Discrete denoising diffusion approach to integer factorization. In International Conference on Artificial Neural Networks, pages 123–134. Springer, 2023.arxiv.org/abs/2309.05295
- [15]R. W. Gayler. Vector symbolic architectures answer Jackendoff’s challenges for cognitive neuroscience. arXiv preprint cs/0412059, 2004.DOI
- [16]K. K. Haefeli, K. Martinkus, N. Perraudin, and R. Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. arXiv preprint arXiv:2210.01549, 2022.arxiv.org/abs/2210.01549
- [17]M. Hittmeir. A time-space tradeoff for lehman’s deterministic integer factorization method. Mathematics of Computation, 90(330):1999–2010, 2021.DOI
- [19]E. Hoogeboom, D. Nielsen, P. Jaini, P. Forré, and M. Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in neural information processing systems, 34:12454–12465, 2021.
- [20]B. Jansen and K. Nakayama. Neural networks following a binary approach applied to the integer prime-factorization problem. In Proceedings. IEEE International Joint Conference on Neural Networks, volume 4, pages 2577–2582. IEEE, 2005.
- [21]P. Kanerva. Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors. Cognitive computation, 1(2):139–159, 2009.
- [22]D. Kleyko, C. Bybee, C. J. Kymn, B. A. Olshausen, A. Khosrowshahi, D. E. Nikonov, F. T. Sommer, and E. P. Frady. Integer factorization with compositional distributed representations. In Proceedings of the 2022 Annual Neuro-Inspired Computational Elements Conference, pages 73–80, 2022.DOI
- [23]F. W. Lawrence. Factorisation of numbers. Messenger of Math, 24:100–109, 1895.
- [24]R. S. Lehman. Factoring large integers. Mathematics of Computation, 28(126):637–646, 1974.
- [25]A. K. Lenstra and H. W. Lenstra. The development of the number field sieve, volume 1554. Springer Science & Business Media, 1993.
- [26]A. K. Lenstra, H. W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515––534, 1982.
- [27]A. K. Lenstra, H. W. Lenstra Jr, M. S. Manasse, and J. M. Pollard. The number field sieve. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, pages 564–572, 1990.
- [28]H. W. Lenstra Jr. Factoring integers with elliptic curves. Annals of mathematics, pages 649–673, 1987.
- [29]S. Limnios, P. Selvaraj, M. Cucuringu, G. Maple, G. Reinert, and A. Elliott. Sagess: Sampling graph denoising diffusion model for scalable graph generation. arXiv preprint arXiv:2306.16827, 2023.arxiv.org/abs/2306.16827
- [30]B. T. Lowerre. The Harpy speech recognition system. Carnegie Mellon University, 1976.
- [31]J. Lys, V. Gripon, A. Marmoret, L. Mauch, F. Cardinaux, G. B. Hacene, and B. Pasdeloup. D5P4: Partition determinantal point process for diversity in parallel discrete diffusion decoding, 2026. URL https://arxiv.org/abs/2603.19146.
- [32]T. Monz, D. Nigg, E. A. Martinez, M. F. Brandl, P. Schindler, R. Rines, S. X. Wang, I. L. Chuang, and R. Blatt. Realization of a scalable Shor algorithm. Science, 351(6277):1068–1070, 2016.DOI
- [33]R. Nene and S. Uludag. Machine learning approach to integer prime factorisation. arXiv preprint arXiv:2202.02023, 2022.
- [34]C. H. Papadimitriou. Computational complexity. In Encyclopedia of computer science, pages 260–265. 2003.
- [35]T. A. Plate. Holographic reduced representations. IEEE Transactions on Neural networks, 6(3):623–641, 1995.
- [36]J. Pollard. A Monte Carlo method for factorization. BIT Numerical Mathematics, 15:331–334, 1975.DOI
- [37]C. Pomerance. The quadratic sieve factoring algorithm. In Advances in cryptology, pages 169–182. Springer Berlin/Heidelberg, 1985.
- [38]C. Pomerance. A tale of two sieves. Notices of the American Mathematical Society, 43(12):1473–1485, 1996.
- [39]A. Renner, L. Supic, A. Danielescu, G. Indiveri, B. A. Olshausen, Y. Sandamirskaya, F. T. Sommer, and E. P. Frady. Neuromorphic visual scene understanding with resonator networks. Nature Machine Intelligence, 6(6):641–652, 2024.DOI
- [40]R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, 1978.
- [41]P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. arXiv preprint quant-ph/9508027, 1995.
- [42]D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, K. Simonyan, and D. Hassabis. Mastering chess and shogi by self-play with a general reinforcement learning algorithm, 2017. URL https://arxiv.org/abs/1712.01815.
- [43]C. Snell, J. Lee, K. Xu, and A. Kumar. Scaling LLM test-time compute optimally can be more effective than scaling model parameters, 2024. URL https://arxiv.org/abs/2408.03314.
- [44]J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International conference on machine learning, pages 2256–2265. PMLR, 2015.

