Motivated by practical inefficiencies in direct implementations of Eisenbrand’s continued fraction-based shortest vector algorithm for 2-dimensional lattices and its limitation to the Chebyshev metric, this work revisits this problem from theoretical and experimental perspectives. Theoretically, we propose a geometrically redefined reduced basis that inherently encodes shortest vectors under \(\ell _1\) , \(\ell _2\) , and \(\ell _\infty \) norms—resolving Eisenbrand’s norm-specific constraint. Algorithmically, we develop a continued-fraction-free reduction framework that eliminates costly convergent computations and their associated large-integer arithmetic. Building on Eisenbrand’s unrealized accelerated framework, we extend Möller’s HGCD technique to three integers and develop our modified-HGCD algorithm, yielding the fully implemented \(O(M(n)\log n)\) solution for arbitrary lattice parameters. Extensive experiments confirm orders-of-magnitude efficiency improvements. Our approach bridges theoretical optimality with practical efficiency by unifying norm handling through newly defined reduced bases and avoiding Schönhage’s intricate back-up steps via stable HGCD adaptation.
