Simultaneous reduction of a lattice basis and its reciprocal basis

Given a latticeL we are looking for a basisB=b ₁, ...b _n ] ofL with the property that bothB and the associated basisB ^*=b ₁ ^* , ...,b _n ^* ] of the reciprocal latticeL ^* consist of short vectors. For any such basisB with reciprocal basisB ^* let . Håstad and Lagarias 7] show that each latticeL of full rank has a basisB withS(B)exp(c ₁·n ^1/3) for a constantc ₁ independent ofn. We improve this upper bound toS(B)exp(c ₂·(lnn)²) withc ₂ independent ofn.We will also introduce some new kinds of lattice basis reduction and an algorithm to compute one of them. The new algorithm proceeds by reducing the quantity . In combination with an exhaustive search procedure, one obtains an algorithm to compute the shortest vector and a Korkine-Zolotarev reduced basis of a lattice that is efficient in practice for dimension up to 30.