Neural search explores a game linked to prime factoring challenge
Searching for Primes: A Neural AlphaZero Approach to a Factoring Game
Cryptography and Security
Summary
Factoring large numbers is a hard problem with important uses, like encryption. The authors study a puzzle-like game where solving it is as tough as factoring a big semiprime number. They use a special type of AI that learns and plans ahead, called AlphaZero, to play this game and see how well neural search helps solve factoring-like challenges. Their work shows how deep learning can tackle a problem tied closely to number theory and cryptography.
What this means in practice
- •For cryptographic engineers: Examine new neural network strategies for factoring challenges that underpin cryptographic security assumptions.
- •For game ai developers: Develop neural search algorithms in environments structurally equivalent to hard mathematical problems.
Authors
Marcel Crasmaru
Abstract
We study a one-player token game on an $N\times N$ board where tokens slide along diagonals or duplicate onto neighbouring ones to form a combinatorial rectangle $R\times S$. A conserved integer weight $W'$ and a strict monovariant guarantee $O(N^2)$-length solutions, placing the game in $\mathsf{NP}$. We prove that reaching a final position factors this $2N$-bit $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. However, 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. The game's entire difficulty is thus isolated to the initial number-theoretic split. Supplying the popcounts of the factors as a promise preserves this asymptotic hardness but bounds the target search space. We exploit this constrained space 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.