SIMULTANEOUS REDUCTION OF A LATTICE BASIS AND ITS RECIPROCAL BASIS

Given a lattice L we are looking for a basis B = [b1,..., b(n)] of L with the property that both B and the associated basis B* = [b1*,...,b(n)*] of the reciprocal lattice L* consist of short vectors. For any such basis B with reciprocal basis B* let S(B) = max/1 less-than-or-equal-to i less-than-or-equal-to n (\b(i)\ . \b(i)*\). Hastad and Lagarias [7] show that each lattice L of full rank has a basis B with S(B) less-than-or-equal-to exp(c1 . n1/3) for a constant cl independent of n. We improve this upper bound to S(B) < exp(c2 . (ln n)2) with c2 independent of n. 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 [GRAPHICS] 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.