{"id":"arxiv/2604.09837","url":"https://arxiv.org/abs/2604.09837","tags":["quant-ph","cs.LO"],"score":0,"title":"Planted-solution SAT and Ising benchmarks from integer factorization","domain":"quant-ph","source":"arxiv","authors":["Itay Hen"],"reviews":0,"subject":"quant-ph","summary":"We present a family of planted-solution benchmark instances for satisfiability (SAT) solvers and Ising optimization derived from integer factorization. Given two primes $p$ and $q$, the construction encodes the arithmetic constraints of $N = p \\times q$ as a conjunctive normal form (CNF) formula whose satisfying assignments correspond to valid factorizations of~$N$. The known pair $(p,q)$ serves as a built-in ground truth, enabling unambiguous verification of solver output. We show that for two $d$-bit primes the total number of carry contractions is on the order of $d^4$. Empirical…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-10","reactions":{}}