Viable fac-relation generation for Schnorr's lattice-based factoring: approximate CVP beyond Babai versus the smoothness barrier

Schnorr's approach reduces integer factoring to collecting many 'fac-relations' — pairs $(u,v)$ for which both $u$ and $u-vn$ factor entirely over a basis of small primes — obtained from approximate solutions of closest-vector instances in a specially constructed 'prime lattice'. Aboumrad, Widdows, and Kaushik (2023) showed experimentally and heuristically that this route fails to scale: the density of smooth candidates decays exponentially with the bit length, so end-to-end lattice-based factoring lags far behind classical sieves, and quantum refinements of the Babai nearest-plane step do not change this. They nonetheless posed a precise open question: does there exist any polynomial-time, or substantially subexponential, classical or quantum algorithm that generates fac-relations of sufficient density and diversity to make the Schnorr-style reduction viable — in particular, an approximate closest-vector procedure systematically closer to the target than Babai nearest-plane?

Background

Factoring a large semiprime $n=pq$ into its two prime factors is the computational assumption underlying the RSA cryptosystem. The best general-purpose classical algorithms are subexponential: the quadratic sieve runs in time $L_n[1/2]$ and the general number field sieve (GNFS) in $L_n[1/3]$ , where $L_n[\alpha]=\exp(O((\log n)^{\alpha}(\log\log n)^{1-\alpha}))$ interpolates between polynomial time ( $\alpha=0$ ) and exhaustive search ( $\alpha=1$ ). Shor's quantum algorithm factors in polynomial time but requires fault-tolerant quantum computers far beyond current hardware.

A lattice is the set of all integer linear combinations $\{\lambda_1 b_1+\dots+\lambda_m b_m:\lambda_i\in\mathbb{Z}\}$ of given basis vectors. The closest vector problem (CVP) asks, given a lattice and a target vector $t$ , for the lattice vector closest to $t$ ; it is NP-hard in general (the closely related shortest vector problem, SVP, was proven NP-hard under randomized reductions by Ajtai in 1998). The Lenstra–Lenstra–Lovász (LLL) algorithm computes a reduced basis of a lattice in polynomial time, and Babai's nearest-plane algorithm uses such a reduced basis to find a lattice vector within a bounded factor of the closest one, by greedily rounding the target's coefficients with respect to the Gram–Schmidt orthogonalization of the basis.

Schnorr (1990, published in the DIMACS series in 1993; refined 2013; and revived in a 2021 preprint) proposed to use CVP for the data-collection phase of factoring. An integer is $y$ -smooth if all of its prime factors are at most $y$ . Fix the factor basis $p_1,\dots,p_m$ of the first $m$ primes and consider the 'prime lattice' $B_{m,c}$ whose columns combine the permuted logarithms $f(j)=\log p_{\sigma(j)}$ with a final row $\lceil 10^c\ln p_j\rceil$ , where $c$ is a precision parameter and $\sigma$ a random permutation. A lattice coefficient vector $e\in\mathbb{Z}^m$ with $B_{m,c}e$ close to the target $t=(0,\dots,0,\lceil 10^c\ln n\rceil)$ yields

$u=\prod_{e_j\ge 0}p_j^{e_j},\qquad v=\prod_{e_j<0}p_j^{-e_j},$

with $\log(u/(vn))$ small, so that $S=u-vn$ is small; if both $u$ and $S$ are $p_m$ -smooth, the pair $(u,v)$ is a fac-relation (called a smooth relation pair by Yan et al.). Enough independent fac-relations, combined by linear algebra modulo 2 over the exponent vectors, produce a congruence of squares that factors $n$ , exactly as in classical sieve methods. Schnorr proved (asymptotically) that if $B_{m,c}e$ is sufficiently close to $t$ in $\ell_\infty$ - and $\ell_1$ -norm, then $|S|=p_m^{o(1)}$ .

The obstacle is smoothness scarcity. By estimates going back to Dickman and de Bruijn — the proportion of integers below $x$ that are $x^{1/a}$ -smooth is asymptotically $\rho(a)$ for the Dickman function $\rho$ , which decays roughly like $\exp(-a\log a)$ — the fraction of candidate values $S$ of size about $\sqrt{n}$ (or larger) that are $p_m$ -smooth is exponentially small in the smoothness parameter. Aboumrad, Widdows, and Kaushik (2023) combined this with the prime number theorem to argue that in the sublinear-lattice-dimension regime of Yan et al. (2022) — who proposed using the quantum approximate optimization algorithm (QAOA, a variational quantum heuristic) to refine Babai's CVP approximation, and speculated that parts of an RSA-2048 factorization calculation might fit on a quantum processor with 372 qubits — exponentially many lattice instances would be needed. Their end-to-end implementation could not factor numbers beyond 72 bits overnight while the quadratic sieve handled 110-bit numbers in moments, and simple classical alternatives to QAOA (testing several roundings per lattice) performed better. Independent critiques (Grebnev et al. 2023; Khattar and Yosri 2023) reached similarly negative conclusions about the sublinear-resource claims.

The source paper nevertheless observes that the mathematical picture 'left a slight possibility, at least in principle', and asks: 'Is there some approximate solution to the CVP, that is closer than the Babai nearest plane approximation, but does not suffer from the NP-hardness of solving the full CVP, so that the search for fac-relations is both tractable and fruitful enough to solve the factoring problem?' A closely connected analytic gap is that no non-asymptotic quantitative theory exists for the smoothness probability of $S=u-vn$ as a function of the properties of the producing lattice vector — the estimation error, the size of $v$ , and the coordinate structure — which the source notes is difficult to quantify because these quantities are interrelated.

Problem Statement

Does there exist a classical or quantum algorithm that, given an arbitrary semiprime $n$ , generates Schnorr-type fac-relations — pairs $(u,v)$ with $u=\prod_{e_j\ge 0}p_j^{e_j}$ , $v=\prod_{e_j<0}p_j^{-e_j}$ arising from a lattice coefficient vector $e$ whose prime-lattice image $B_{m,c}e$ approximates the target $t$ , such that both $u$ and $S=u-vn$ are $p_m$ -smooth over the factor basis of the first $m$ primes — of sufficient density and diversity (enough independent relations to solve the exponent system modulo 2 and produce a congruence of squares) so that the end-to-end factoring of $n$ via the Schnorr pipeline has total cost polynomial in $\log n$ , or at least substantially subexponential in the sense of meaningfully improving on the $L_n[1/3]$ complexity of the general number field sieve? In particular, determine whether an approximate solution to these CVP instances can be computed tractably while being systematically closer to the target than Babai's nearest-plane approximation in the $\ell_2$ sense relevant to practical heuristics, so that the exponentially small smoothness probability of the resulting candidates — as predicted by Dickman–de Bruijn asymptotics — is overcome in aggregate. The scientific objective is a definitive determination of the viability of the Schnorr-style reduction from factoring to lattice CVP: either a demonstrated and justified viable relation-generation algorithm, or a rigorous demonstration that the exponential smoothness scarcity of prime-lattice CVP candidates cannot be overcome in aggregate. Either branch resolves the task and each is independently refutable: an affirmative resolution requires a justified algorithm whose end-to-end factoring cost is $L_n[\alpha]$ for some constant $\alpha<1/3$ (the polynomial case $\alpha=0$ included), and a negative resolution requires a rigorous demonstration that no Schnorr-type relation-generation algorithm — over any approximate-CVP or relation-finding procedure in the prime-lattice pipeline, not only Babai nearest-plane — attains such a bound, that is, that the Dickman–de Bruijn scarcity persists for the aggregate relation yield across all lattice instances, not merely within a single lattice. The 'In particular' CVP-improvement question is a focusing sub-question: settling it bears on, but is not by itself equivalent to, settling this existence question.

References

Willie Aboumrad, Dominic Widdows, Ananth Kaushik, 'Quantum and Classical Combinatorial Optimizations Applied to Lattice-Based Factorization', arXiv:2308.07804 (2023), DOI 10.48550/arXiv.2308.07804, https://arxiv.org/abs/2308.07804
C. P. Schnorr, 'Factoring integers and computing discrete logarithms via diophantine approximation', in Advances in Computational Complexity Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 13, American Mathematical Society (1993), pp. 171–181, DOI 10.1090/dimacs/013/10, https://doi.org/10.1090/dimacs/013/10
Claus Peter Schnorr, 'Factoring Integers by CVP Algorithms', in M. Fischlin and S. Katzenbeisser (eds.), Number Theory and Cryptography, Lecture Notes in Computer Science 8260, Springer (2013), pp. 73–93, DOI 10.1007/978-3-642-42001-6_6, https://doi.org/10.1007/978-3-642-42001-6_6
Claus Peter Schnorr, 'Fast Factoring Integers by SVP Algorithms', IACR Cryptology ePrint Archive, Report 2021/232 (2021), https://eprint.iacr.org/2021/232
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', arXiv:2212.12372 (2022), DOI 10.48550/arXiv.2212.12372, https://arxiv.org/abs/2212.12372
Narendra N. Hegade, Enrique Solano, 'Digitized-counterdiabatic quantum factorization', arXiv:2301.11005 (2023), DOI 10.48550/arXiv.2301.11005, https://arxiv.org/abs/2301.11005
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', arXiv:2303.04656 (2023), DOI 10.48550/arXiv.2303.04656, https://arxiv.org/abs/2303.04656
Tanuj Khattar, Noureldin Yosri, 'A comment on "Factoring integers with sublinear resources on a superconducting quantum processor"', arXiv:2307.09651 (2023), DOI 10.48550/arXiv.2307.09651, https://arxiv.org/abs/2307.09651
Willie Aboumrad, Dominic Widdows, 'Mod2VQLS: a Variational Quantum Algorithm for Solving Systems of Linear Equations Modulo 2', arXiv:2311.12771 (2023), DOI 10.48550/arXiv.2311.12771, https://arxiv.org/abs/2311.12771
Marco Tesoro, Ilaria Siloi, Daniel Jaschke, Giuseppe Magnifico, Simone Montangero, 'Integer factorization via tensor-network Schnorr's sieving', arXiv:2410.16355 (2024, v3 2026); published in Physical Review A (2026), DOI 10.1103/d9dl-ctt4, https://arxiv.org/abs/2410.16355
Dennis Willsch, Philipp Hanussek, Georg Hoever, Madita Willsch, Fengping Jin, Hans De Raedt, Kristel Michielsen, 'The State of Factoring on Quantum Computers', arXiv:2410.14397 (2024, v2 2025), DOI 10.48550/arXiv.2410.14397, https://arxiv.org/abs/2410.14397
Ben Priestley, Petros Wallden, 'A practically scalable approach to the closest vector problem for sieving via QAOA with fixed angles', arXiv:2503.08403 (2025); published in Quantum Science and Technology (2026), DOI 10.1088/2058-9565/ae4cc6, https://arxiv.org/abs/2503.08403
Max O. Al-Hasso, Marko von der Leyen, 'A Probabilistic Computing Approach to the Closest Vector Problem for Lattice-Based Factoring', arXiv:2510.19390 (2025), DOI 10.48550/arXiv.2510.19390, https://arxiv.org/abs/2510.19390
Bao Yan, Shijie Wei, Guilu Long, 'The status and prospect of quantum-classical combination integer factorization algorithm', Scientia Sinica Informationis (2025), DOI 10.1360/ssi-2025-0105, https://doi.org/10.1360/ssi-2025-0105
Sarang Vehale, Deeksha Kushwah, Rahul Kumar Neiwal, Amit Saxena, 'Survey of Integer Factorization Using Lattice-Based Algorithms', SN Computer Science (2026), DOI 10.1007/s42979-026-05231-x, https://doi.org/10.1007/s42979-026-05231-x
Erik Mulder, Bruno Sterner, Wessel van Woerden, 'Large smooth twins from short lattice vectors', arXiv:2509.17699 (2025, v2 2026), DOI 10.48550/arXiv.2509.17699, https://arxiv.org/abs/2509.17699
L. Babai, 'On Lovász' lattice reduction and the nearest lattice point problem', Combinatorica 6(1) (1986), pp. 1–13, DOI 10.1007/BF02579403, https://doi.org/10.1007/BF02579403
Miklós Ajtai, 'The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)', Proceedings of the thirtieth annual ACM symposium on Theory of Computing (STOC '98) (1998), DOI 10.1145/276698.276705, https://doi.org/10.1145/276698.276705
Adolf Hildebrand, 'On the number of positive integers ≤ x and free of prime factors > y', Journal of Number Theory 22 (1986), DOI 10.1016/0022-314X(86)90013-2, https://doi.org/10.1016/0022-314X(86)90013-2
Ilia V. Zalivako, Andrey Yu. Chernyavskiy, Anastasiia S. Nikolaeva, Alexander S. Borisenko, Nikita V. Semenin, Kristina P. Galstyan, Andrey E. Korolkov, Sergey V. Grebnev, Evgeniy O. Kiktenko, Ksenia Yu. Khabarova, Aleksey K. Fedorov, Ilya A. Semerikov, Nikolay N. Kolachevsky, 'Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor', arXiv:2503.10588 (2025); published in Quantum Information & Computation (2025), DOI 10.2478/qic-2025-0021, https://arxiv.org/abs/2503.10588