Faster Lattice Basis Computation -- The Generalization of the Euclidean Algorithm
<|reference_start|>Faster Lattice Basis Computation -- The Generalization of the Euclidean Algorithm: The Euclidean algorithm 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_n)$ given vectors $A_1, \ldots , A_n \in \mathbb{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 \mathbb{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 $\tilde 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.<|reference_end|>
@article{klein2024faster,
    title={Faster Lattice Basis Computation via a Natural Generalization of the
  Euclidean Algorithm},
    author={Kim-Manuel Klein and Janina Reuter},
    journal={arXiv preprint arXiv:2408.06685},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.06685},
    primaryClass={cs.DS cs.DM math.AG}
}