Computing a Lattice Basis Revisited

Given (a,b) \in \mZ^2, Euclid's algorithm outputs the generator \gcd(a,b) of the ideal a\mZ + b\mZ. Computing a lattice basis is a high-dimensional generalization: given \mathbfa _1,\dots,\veca _n \in \mZ^m, find a \mZ-basis of the lattice L=\ \sum_i=1 ^n x_i \veca _i, x_i \in \mZ\ generated by the \veca _i's. The fastest algorithms known are HNF algorithms, but are not adapted to all applications, such as when the output should not be much longer than the input. We present an algorithm which extracts such a short basis within the same time as an HNF, by reduction to HNF. We also present an HNF-less algorithm, which reduces to Euclid's extended algorithm and can be generalized to quadratic forms. Both algorithms can extend primitive sets into bases.