Abstract
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.
Original language | English |
---|---|
Title of host publication | Algorithmic Number Theory; Proceedings of the 9th International Symposium on Algorithmic Number Theory (ANTS-IX); Lecture Notes in Computer Science 6197 |
Editors | Guillaume Hanrot, Francois Morain, Emmanuel Thome |
Place of Publication | Germany |
Publisher | Springer, Springer Nature |
Pages | 157-173 |
Number of pages | 17 |
ISBN (Print) | 9783642145179 |
DOIs | |
Publication status | Published - 2010 |
Event | The 9th International Symposium on Algorithmic Number Theory (ANTS-IX) - Nancy, France Duration: 19 Jul 2010 → 23 Jul 2010 |
Conference
Conference | The 9th International Symposium on Algorithmic Number Theory (ANTS-IX) |
---|---|
City | Nancy, France |
Period | 19/07/10 → 23/07/10 |