Computing the Shortest Vector in a Lattice Using the Alternating Direction Method of Multipliers

Computing the shortest vector in a lattice has many applications in computer science and engineering such as in cryptography, coding theory, and quantum computing. One of the best known algorithms for computing such shortest vectors is the Lenstra, Lenstra and Lovasz (LLL) algorithm. Unfortunately the LLL algorithm has a worst-case exponential running time, and its practical performance depends heavily on the lattice structure. In this paper, we propose an efficient implementation of the Alternating Direction Method of Multipliers for finding the shortest vector in a lattice. Our algorithm is an improved stochastic version of the ADMM algorithm proposed by Takapoui, Moehle, Boyd and Bemporad. The performance of our method is illustrated via extensive numerical experiments on various lattice structures. The numerical results show that our method significantly outperforms the LLL algorithm in terms of running time and solution quality.