Searching for Primes: A Neural AlphaZero Approach to a Factoring Game

A token-sliding game on an N\timesN board is shown to be equivalent to integer factoring, and AlphaZero-style search is used to probe the limits of neural look-ahead on this factoring-equivalent environment.

Marcel Crasmaru· 2026· DOI 10.48550/arXiv.2609.22968

The core problem

Integer factoring is a central computational problem, underpinning the security of widely deployed cryptographic systems. This work introduces a one-player token game played on an N \times N board, where tokens slide along diagonals or duplicate onto neighbouring cells to form a combinatorial rectangle R \times S . The game is governed by a conserved integer weight W^{'} and a strict monovariant, which together guarantee that solutions have length O (N^{2}), placing the game in the complexity class NP . The central claim is that reaching a final position of this game factors the 2 N -bit integer W^{'} into two N -bit factors V, M < 2^{N} that encode the rectangle's rows and columns. Consequently, solving the game for a balanced-semiprime target is equivalent to integer factoring. The paper then exploits a constrained search space—obtained by supplying the popcounts of the factors as a promise—using a learned policy/value network and an AlphaZero-style Monte-Carlo tree search, empirically probing the limits of neural look-ahead on a factoring-equivalent environment.

Innovation

The paper establishes several theoretical results and reports empirical findings from the AlphaZero-style search. **Theoretical results.** - The game is in NP : solutions have length O (N^{2}) due to the strict monovariant. - Reaching a final position factors the 2 N -bit W^{'} into two N -bit factors V, M < 2^{N} . - For a balanced-semiprime target, solving the game is equivalent to integer factoring. - If the target rectangle is known, the solution reduces to two polynomial-time steps: a forced downward chip-flow and a 0/1 -polynomial factorisation leveraging Cohn's theorem. - Supplying the popcounts of the factors as a promise preserves asymptotic hardness but bounds the target search space. **Empirical results.** The authors exploit the constrained space using a learned policy/value network and an AlphaZero-style Monte-Carlo tree search. They empirically probe the limits of neural look-ahead on a factoring-equivalent environment. The results characterise how the promise on popcounts constrains the search and how neural guidance performs within that constrained space. No specific numerical performance metrics are provided in the abstract; the empirical contribution is

Integer factoring is a central computational problem, underpinning the security of widely deployed cryptographic systems. This work introduces a one-player token game played on an N \times N board, where tokens slide along diagonals or duplicate onto neighbouring cells to form a combinatorial rectangle R \times S . The game is governed by a conserved integer weight W^{'} and a strict monovariant, which together guarantee that solutions have length O (N^{2}), placing the game in the complexity class NP . The central claim is that reaching a final position of this game factors the 2 N -bit integer W^{'} into two N -bit factors V, M < 2^{N} that encode the rectangle's rows and columns. Consequently, solving the game for a balanced-semiprime target is equivalent to integer factoring. The paper then exploits a constrained search space—obtained by supplying the popcounts of the factors as a promise—using a learned policy/value network and an AlphaZero-style Monte-Carlo tree search, empirically probing the limits of neural look-ahead on a factoring-equivalent environment.

The methodology proceeds in two parts: a theoretical reduction and an empirical search algorithm.

Why it matters

The work isolates the computational difficulty of the game to the initial number-theoretic split. Once the target rectangle is known, the remaining steps are polynomial-time: a forced downward chip-flow and a 0/1 -polynomial factorisation leveraging Cohn's theorem. This separation is significant because it shows that the game's hardness is not in the token dynamics but in the number-theoretic core. The promise on popcounts of the factors preserves asymptotic hardness while bounding the target search space. This makes the problem amenable to heuristic and learning-based search, such as the AlphaZero-style MCTS used here. The empirical probing of neural look-ahead on a factoring-equivalent environment provides insight into the limits of such methods. The approach connects combinatorial game theory, integer factoring, and neural search, suggesting a new testbed for evaluating look-ahead algorithms on hard number-theoretic problems. **Implications.** The reduction implies that any progress on solving the game efficiently would yield an efficient factoring algorithm, with consequences for cryptography. Conversely, the promise-constrained version offers a controlled setting to study neural search. The use of Cohn's theorem for 0/1 -polynomial factorisation is a key technical ingredient that bridges the game's combinatorial structure to algebraic factoring. **Limitations and future work.** The abstract does not report specific empirical performance metrics, so the practical scalability of the neural approach remains to be quantified. Future work could explore larger N, different promise types, and comparisons with classical factoring algorithms.

Who should read this

CS practitioners and researchers

Opening member content…