Portal de Periódicos da CAPES

Computing a lattice basis from a system of generating vectors

1989; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-51517-8_89

1611-3349

Johannes Buchmann, Michael Pohst,

Cryptography and Data Security

In this paper we describe how the LLL-algorithm can be used to compute a basis of a lattice L in R n from a system of k generating vectors and a lower bound for the lengths of the non zero vectors in L. The algorithm which we present is proved to be polynomial time in n + k and the size of the input data. The algorithm is applied to the problem of finding multiplicative relations between units of algebraic number fields. Numerical results show that our method works very efficiently.