Smooth-relation yield and the required lattice dimension in Schnorr-style (CVP-based) integer factoring

Schnorr's lattice-based factoring method and its quantum-assisted revivals reduce factoring an n-bit integer N to solving closest-vector problems (CVP) on a prime-number lattice, hoping that lattice vectors near the target encode enough B-smooth relation pairs (SR-pairs) to factor N. The load-bearing claim — that a lattice of sublinear dimension m = O(n/log n) suffices — remains unproven: brute-force experiments fail beyond about 70 bits, and all negative arguments to date are empirical or based on random-model heuristics. The open problem is a rigorous analysis of the relation-collection step: prove or disprove that sublinear dimension suffices — and, in the negative case, establish an asymptotic lower bound on the required dimension — and determine the probability, as a function of the bit length n, the lattice parameter l, the precision parameter c, and the smoothness bound B2, that near-optimal CVP solutions in this lattice family yield usable SR-pairs. This would settle whether any hybrid classical/quantum CVP-based factoring scheme can scale to cryptographically relevant sizes, including the claimed 372-qubit attack on RSA-2048.

Background

Classical factoring algorithms such as the quadratic sieve and the number field sieve work by relation collection: find more than $\pi(B)$ pairs of integers $(u,v)$ — where $\pi(B)$ is the number of primes up to a smoothness bound $B$ — such that $u$, $v$, and $|u-vN|$ are all $B$-smooth (all their prime factors are at most $B$); enough independent such relations produce a factor of $N$ by linear algebra modulo 2. Following the source comment, a $B_2$-smooth relation pair (SR-pair) is such a pair $(u,v)$ with $u$, $v$, and $|u-vN|$ all $B_2$-smooth.

A lattice is a discrete additive subgroup of $\mathbb{R}^d$ given by integer combinations of a basis; the closest vector problem (CVP) asks for the lattice point nearest to a given target vector, and the shortest vector problem (SVP) for the shortest nonzero lattice vector. Both underpin lattice-based cryptography. In 1991, C. P. Schnorr proposed generating the required smooth relations from a prime number lattice (independently analyzed by Adleman): the lattice is built from the logarithms of the primes in the factor base, so a lattice vector close to a suitable target encodes integers $u$ and $v$ that are smooth by construction, while $|u-vN|$ is small and therefore plausibly smooth. This turns factoring into a sequence of CVP instances, but the lattice dimension required grows with the size of $N$, which kept the method uncompetitive with sieving; no rigorous bound on the required dimension was ever established.

In 2021 Schnorr posted the claim that a lattice of dimension only $m=\mathcal{O}(n/\log n)$, where $n=\log_2 N$ is the bit length of $N$, suffices to produce enough relations ('this destroys the RSA cryptosystem'); the ePrint offers no proof. Léo Ducas's open-source experiments (SchnorrGate, 2021) indicated that in such sublinear dimensions the algorithm already fails on 40-bit numbers, and most lattice experts believe the required dimension is much larger — but again without proof.

Yan et al. (2022) revived the claim in quantum form: they retained Schnorr's sublinear-dimension lattice and replaced the classical CVP heuristic by the quantum approximate optimization algorithm (QAOA), a shallow variational quantum heuristic with no proven speedup for such problems. They reported factoring integers up to 48 bits with 10 superconducting qubits and extrapolated that 372 physical qubits would challenge RSA-2048. Their construction exposes hyperparameters: the lattice parameter $l$ (larger $l$ gives a larger lattice dimension $m$ and plausibly more relations at higher enumeration cost), the precision parameter $c$ (which scales the final lattice row and target coordinate, and hence the lattice determinant), and the smoothness bound $B_2$ (suggested near $2m^2$); factoring succeeds once roughly $\pi(B_2)$ independent SR-pairs are collected.

The claim drew immediate criticism. Khattar and Yosri — the authors of the source comment — implemented the full pipeline with a configurable hyperparameter sweep and, decisively, replaced QAOA by exact brute-force enumeration, i.e. a hypothetical perfect quantum optimizer: the sublinear-dimension lattice still fails to produce enough SR-pairs for random 80-bit integers and beyond (lattice dimensions up to 30 with $c=4$; the choice $l=2$ rescued 70-bit instances but not 80-bit ones). Grebnev et al. showed that the complexity of the classical reduction step was never analyzed; Aboumrad, Widdows and Kaushik gave a heuristic argument from the exponential decay of smooth-number density that the method cannot scale; Prokop and Wallden heuristically extrapolated pre-trained QAOA (depth $p=3$) for SVP and found success probability about $2^{-0.695n}$ in the search-space dimension — slightly worse than fault-tolerant Grover search — bounding fixed-depth pre-trained QAOA refinement of this kind.

All of this negative evidence is empirical or heuristic (random-lattice and smoothness models). The source comment records that the sublinear-resource claims rest on Schnorr's algorithm "whose efficiency and probability of success are unknown"; what remains genuinely unresolved is the rigorous theory of the relation-collection step itself: the probability that near-optimal CVP solutions in this lattice family yield usable SR-pairs, as a function of $n$, $l$, $c$, and $B_2$; the asymptotically required lattice dimension; and the conjectured but unexplained positive effect of the precision parameter $c$ on the probability of finding near-target vectors. Adjacent rigorous theory exists — Mulder, Sterner and van Woerden (2025) analyzed the prime-number lattice to find large pairs of consecutive smooth integers ('smooth twins') for isogeny cryptography, confirming that its short vectors carry smoothness structure — but the factoring-yield question has not been touched, and a 2026 survey of lattice-based factorization concludes that every known approach remains far below cryptographic sizes.

Problem Statement

Consider the family of CVP-based factoring constructions of Schnorr (1991; ePrint 2021/933) and Yan et al. (2022): a prime-number lattice of dimension $m$ built on the first $m$ primes — the factor base for the candidate pair, so that $u$ and $v$ are smooth by construction over those primes — with lattice parameter $l$ controlling the dimension $m$ and precision parameter $c$ scaling the final lattice row and target coordinate (hence the lattice determinant), where a near-optimal solution of the closest vector problem encodes a candidate pair $(u,v)$, and the pair is usable only if $|u-vN|$ is also $B_2$-smooth for the separate smoothness bound $B_2$ (an SR-pair).

Concretely, in the source construction (Khattar–Yosri comment, Eqs. (1)–(3)) the bit length is $n=\lfloor\log_2 N\rceil$ and the dimension is set by $m=\lfloor l\,n/\lfloor\log_2 n\rceil\rfloor$; the basis matrix has diagonal entries $f(1),\dots,f(m)$, a random permutation of $(\lceil 1/2\rceil,\lceil 2/2\rceil,\dots,\lceil m/2\rceil)$, and final row $(\lfloor 10^{c}\ln p_{1}\rceil,\dots,\lfloor 10^{c}\ln p_{m}\rceil)$ of rounded prime logarithms, with target vector $t=(0,\dots,0,10^{c}\ln N)$; each CVP instance is randomly generated. The source experiments used $l\in\{1,2\}$ and $c=4$, and Yan et al. suggest $B_2\sim 2m^2$. In what follows, admissible hyperparameters $(l,c,B_2)$ are those, possibly depending on $n$, for which the construction is well defined and $m$ remains $\mathcal{O}(n/\log n)$.

(1) Sublinear-dimension claim. Prove or disprove that there exist admissible hyperparameters $(l,c,B_2)$ in this family for which lattice dimension $m=\mathcal{O}(n/\log n)$, with $n=\log_2 N$, suffices to factor random $n$-bit RSA-style integers $N$ (i.e. semiprimes, the ensemble used in the source experiments): solving the resulting CVP instances — exactly, or to the approximation quality assumed by these algorithms — yields at least $\pi(B_2)+O(1)$ independent SR-pairs in polynomially many trials with non-negligible probability. A negative answer should establish an asymptotic lower bound on the required dimension $m(n)$, or prove that the expected SR-pair yield per trial in the sublinear regime is insufficient for all admissible $(l,c,B_2)$.

(2) SR-pair yield law and the role of precision. Determine, rigorously, the expected number of SR-pairs obtained per CVP solution as a function of $(n,l,c,B_2)$ for the stated constructions — the expectation taken over the random generation of the CVP instances (random permutation basis and random target vector, as above) — making explicit how the lattice determinant, controlled by the precision parameter $c$, influences the probability of finding near-target lattice vectors, and thereby prove or refute the conjectured positive effect of $c$ on SR-pair yield.

A rigorous resolution of (1) in either direction settles the source question of whether any hybrid classical/quantum CVP-based factoring scheme in this family can scale to cryptographically relevant sizes, and each constitutes a complete answer to this statement. Sub-question (2) — the exact yield law and the resolution of the conjectured positive effect of $c$ — deepens the analysis and constitutes substantial partial progress, but neither branch of (1) presupposes it. Purely heuristic random-model arguments and finite-size experiments do not resolve the asymptotic claim by themselves.

References

1. C. P. Schnorr, Factoring Integers and Computing Discrete Logarithms via Diophantine Approximation, Advances in Cryptology — EUROCRYPT '91, Lecture Notes in Computer Science 547, pp. 281–293 (1991), DOI 10.1007/3-540-46416-6_24, https://doi.org/10.1007/3-540-46416-6_24
2. Claus Peter Schnorr, Fast Factoring Integers by SVP Algorithms, corrected, IACR Cryptology ePrint Archive 2021/933 (2021), https://eprint.iacr.org/2021/933
3. Bao Yan, Ziqi Tan, Shijie Wei, Haocong Jiang, Weilong Wang, Hong Wang, Lan Luo, Qianheng Duan, Yiting Liu, Wenhao Shi, Yangyang Fei, Xiangdong Meng, Yu Han, Zheng Shan, Jiachen Chen, Xuhao Zhu, Chuanyu Zhang, Feitong Jin, Hekang Li, Chao Song, Zhen Wang, Zhi Ma, H. Wang, Gui-Lu Long, Factoring integers with sublinear resources on a superconducting quantum processor (2022), arXiv:2212.12372, https://arxiv.org/abs/2212.12372
4. Tanuj Khattar, Noureldin Yosri, A comment on "Factoring integers with sublinear resources on a superconducting quantum processor" (2023), arXiv:2307.09651, DOI 10.48550/arXiv.2307.09651, https://arxiv.org/abs/2307.09651
5. Sergey V. Grebnev, Maxim A. Gavreev, Evgeniy O. Kiktenko, Anton P. Guglya, Albert R. Efimov, Aleksey K. Fedorov, Pitfalls of the sublinear QAOA-based factorization algorithm (2023), arXiv:2303.04656, journal version DOI 10.1109/ACCESS.2023.3336989 (IEEE Access), https://arxiv.org/abs/2303.04656
6. Willie Aboumrad, Dominic Widdows, Ananth Kaushik, Quantum and Classical Combinatorial Optimizations Applied to Lattice-Based Factorization (2023), arXiv:2308.07804, https://arxiv.org/abs/2308.07804
7. Miloš Prokop, Petros Wallden, Heuristic Time Complexity of NISQ Shortest-Vector-Problem Solvers (2025), arXiv:2502.05284, journal version DOI 10.1109/TQE.2025.3620104 (IEEE Transactions on Quantum Engineering), https://arxiv.org/abs/2502.05284
8. Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia, On the practicality of quantum sieving algorithms for the shortest vector problem (2024), arXiv:2410.13759, https://arxiv.org/abs/2410.13759
9. Erik Mulder, Bruno Sterner, Wessel van Woerden, Large smooth twins from short lattice vectors (2025), arXiv:2509.17699, https://arxiv.org/abs/2509.17699
10. Luis Sánchez Cano, Ginés Carrascal de las Heras, Guillermo Botella Juan, Alberto del Barrio García, Factoring integers via Schnorr's algorithm assisted with VQE (2024), arXiv:2411.16632, https://arxiv.org/abs/2411.16632
11. Narendra N. Hegade, Enrique Solano, Digitized-counterdiabatic quantum factorization (2023), arXiv:2301.11005, https://arxiv.org/abs/2301.11005
12. Max O. Al-Hasso, Marko von der Leyen, A Probabilistic Computing Approach to the Closest Vector Problem for Lattice-Based Factoring (2025), arXiv:2510.19390, https://arxiv.org/abs/2510.19390
13. Sarang Vehale, Deeksha Kushwah, Rahul Kumar Neiwal, Amit Saxena, Survey of Integer Factorization Using Lattice-Based Algorithms, SN Computer Science 7 (2026), DOI 10.1007/s42979-026-05231-x, https://doi.org/10.1007/s42979-026-05231-x
14. Léo Ducas, Testing Schnorr's factorization claim in Sage (SchnorrGate) (2021), https://github.com/lducas/SchnorrGate
15. Scott Aaronson, Cargo Cult Quantum Factoring, Shtetl-Optimized blog post of January 4, 2023, https://scottaaronson.blog/?p=6957