  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 \mathbb{Z}$ and $a_2 \mathbb{Z}$ as $\gcd(a_1,a_2) \mathbb{Z} = a_1
\mathbb{Z} + a_2 \mathbb{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_m)$ given vectors $a_1, \ldots , a_m \in
\mathbb{Z}^n$ with $m> \mathrm{rank}(a_1, \ldots ,a_m)$. Similar to the
Euclidean algorithm, our algorithm is very easy to describe and implement and
can be written within 12 lines of pseudocode.
  While the Euclidean algorithm halves the largest number in every iteration,
our generalized algorithm halves the determinant of a full rank subsystem
leading to at most $\log (\det B)$ many iterations, for some initial subsystem
$B$. Therefore, we can compute a basis of the lattice using at most
$\tilde{O}((m-n)n\log(\det B) + mn^{\omega-1}\log(||A||_\infty))$ arithmetic
operations, where $\omega$ is the matrix multiplication exponent and $A = (a_1,
\ldots, a_m)$. Even using the worst case Hadamard bound for the determinant,
our algorithm improves upon existing algorithm.
  Another major advantage of our algorithm is that we can bound the entries of
the resulting lattice basis by $\tilde{O}(n^2\cdot ||A||_{\infty})$ using a
simple pivoting rule. This is in contrast to the typical approach for computing
lattice basis, where the Hermite normal form (HNF) is used. In the HNF, entries
can be as large as the determinant and hence can only be bounded by an
exponential term.
