Computing a reduced lattice basis from a generating system
Johannes A Buchmann, Volker Kessler · 1992
A polynomial time algorithm is presented that given a rational approximation to a lattice in real n-space and a lower bound for the first successive minimum calculates a reduced basis of that lattice. 1 Introduction In this paper we study the following problem: Suppose that the vectors a 1 ; : : : ; a k in Z n 1 \\Theta R n 2 ; n = n 1 + n 2 , generate an r-dimensional lattice L, i.e. L = k X j=1 Za j : Assume that we are given an algorithm that on input of some q 2 N calculates approximations to all the coordinates of those vectors such that the error is at most 2 \\Gammak\\Gamma1 Find a basis of that lattice; more precisely, an integer matrix that transforms the generating system into a basis of L. This problem arises, for example, if we wish to compute a reduced Z-basis of an order of an algebraic number field (see section 5), if we want to calculate a system of fundamental units of a number field from a generating system for the unit group (see [1],) or if we need to de...