The Euclidean algorithm is one of the oldest algorithms known to mankind. Given two integral numbers a_1 and a_2, it computes the greatest common divisor (gcd) of a_1 and a_2 in a very elegant way. From a lattice perspective, it computes a basis of the sum of two one-dimensional lattices a_1 Z and a_2 Z as gcd(a_1,a_2) Z = a_1 Z + a_2 Z. In this paper, we show that the classical Euclidean algorithm can be adapted in a very natural way to compute a basis of a general lattice L (A_1, \ldots , A_n) given vectors A_1, \ldots , A_n \in Z^d with n> \mathrm{rank}(a_1, \ldots ,a_d). Similar to the Euclidean algorithm, our algorithm is very easy to describe and implement and can be written within 12 lines of pseudocode.
Our generalized version of the Euclidean algorithm allows for several degrees of freedom in the pivoting process. Hence, in a second step, we show that this freedom can be exploited to make the algorithm perform more efficiently. As our main result, we obtain an algorithm to compute a lattice basis for given vectors A_1, \ldots , A_n \in Z^d in time (counting bit operations) LS + \tilde O ((n-d)d^2 \cdot \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 Labhan [SL96] having a running time of O (nd^\omega\log ||A||). For current upper bounds of $LS$, our algorithm has a running time improvement of a factor of at least d^{0.12} over [SL96]. Our algorithm is therefore the first general algorithmic improvement to this classical problem in nearly 30 years.