Faster Lattice Basis Computation via a Natural Generalization of the Euclidean Algorithm

The Euclidean algorithm is one of the oldest algorithms known to mankind. Given two integral numbers a1 and a2, it computes the greatest common divisor (gcd) of a1 and a2 in a very elegant way. From a lattice perspective, it computes a basis of the lattice generated by a1 and a2 as gcd(a1,a2) ℤ = a1 ℤ + a2 ℤ. In this paper, we show that the classical Euclidean algorithm can be adapted in a very natural way to compute a basis of a lattice that is generated by vectors A1, … , An ∈ ℤd with n> rank(A1, … ,An). Similar to the Euclidean algorithm, our algorithm is easy to describe and implement and can be written within 12 lines of pseudocode. As our main result, we obtain an algorithm to compute a lattice basis for given vectors A1, … , An ∈ ℤd in time (counting bit operations) LS + Õ((n−d)d2 · log(||A||), where LS is the time required to obtain the exact fractional solution of a certain system of linear equalities. The analysis of the running time of our algorithms relies on fundamental statements on the fractionality of solutions of linear systems of equations. So far, the fastest algorithm for lattice basis computation was due to Storjohann and Labahn (ISSAC 1996) having a running time of Õ(ndωlog||A||), where ω denotes the matrix multiplication exponent. We can improve upon their running time as our algorithm requires at most Õ(maxn−d, d2dω(2)−1 log||A||) bit operations, where ω(2) denotes the exponent for multiplying a n× n matrix with an n× n2 matrix. For current values of ω and ω(2), our algorithm improves the running time therefore by a factor of at least d0.12 (since n>d) providing the first general runtime improvement for lattice basis computation in nearly 30 years. In the cases of either few additional vectors, e.g. n−d ∈ do(1), or a very large number of additional vectors, e.g. n−d ∈ Ω (dk) and k>1, the run time improves even further in comparison. At last, we present a postprocessing procedure which yields an improved size bound of √d ||A|| for vectors of the resulting basis matrix. The procedure only requires Õ(d3 log||A||) bit operations. By this we improve upon the running time of previous results by a factor of at least d0.74.