Short Bases of Lattices over Number Fields
Claus Fieker and Damien Stehlé
Lattices over number fields arise from a variety of sources in
algorithmic algebra and more recently cryptography. Similar to the
classical case of Z-lattices, the choice of a nice, ``short''
(pseudo)-basis is important in many applications. In this article, we
provide the first algorithm that computes such a ``short''
(pseudo)-basis. We utilize the LLL algorithm for Z-lattices
together with the Bosma-Pohst-Cohen Hermite Normal Form and some size
reduction technique to find a pseudo-basis where each basis vector
belongs to the lattice and the product of the norms of the basis
vectors is bounded by the lattice determinant, up to a multiplicative
factor that is a field invariant. As it runs in polynomial time, this
provides an effective variant of Minkowski's second theorem for
lattices over number fields.