Survey of Integer Factorization Using Lattice-Based Algorithms
摘要
This survey examines the application of lattice-based algorithms to the integer factorization problem, with emphasis on how factorization can be formulated as a Shortest Vector Problem (SVP). The goal is to evaluate whether lattice reduction techniques originally developed for cryptography offer meaningful insight or practical leverage for factorizing composite integers, particularly in the post-quantum context. We review classical and modern lattice reduction methods, including the Lenstra Lenstra Lovász (LLL) algorithm, Block Korkine Zolotarev (BKZ) reductions, and heuristic sieve-based approaches. Their computational characteristics are compared against each other and against traditional factoring techniques such as the General Number Field Sieve (GNFS). We also summarize experimental findings reported in recent literature, including investigations of Schnorr’s algorithm, heuristic lattice sieves, and quantum-assisted hybrid approaches. Lattice-based approaches demonstrate conceptual promise for mapping integer factorization to structured lattice problems. Techniques such as BKZ, enumeration, and heuristic sieving can recover short vectors that encode factorization relations for small to medium-size integers. However, all currently known approaches face severe scalability limitations due to exponential growth in lattice dimension and reduction cost. Practical experiments in prior work, both classical and quantum-assisted, remain restricted to low-complexity instances far below cryptographic parameter sizes. While lattice methods deepen theoretical understanding of factorization and highlight structural connections relevant to post-quantum security, they are not yet practical competitors to state-of-the-art classical factoring algorithms. Their value presently lies in clarifying complexity assumptions, informing cryptographic hardness arguments, and motivating future research on scalable reductions, optimized sieving, and quantum-classical hybrid methods for high-dimensional lattices.