Low-Dimensional Lattice Basis Reduction Revisited

摘要: Low-Dimensional Lattice Basis Reduction Revisited Page 1 Low-Dimensional Lattice Basis Reduction Revisited Damien STEHLE Burlington, June 17th, 2004 Joint work with Phong NGUYEN http://www.loria.fr/~stehle/ damien.stehle@loria.fr Page 2 Low-Dimensional Lattice Basis Reduction Revisited Lattices • Lattice L = grid in a Euclidean space = discrete subgroup of Rd = {∑ m i=1 xibi | x1,...,xm ∈ Z}. • d is the space dim, m ≤ d the dim, [b1,...,bm] a basis. • L given by the integer matrix of one of its bases, along with its Gram matrix: G(b1,...,bm)=(〈bi,bj〉)i,j. • Complexity model: bit operations, without fast arithmetic. 2004/06/17 Damien STEHLE 1/23 Page 3 Low-Dimensional Lattice Basis Reduction Revisited Basic Definitions (1/2) • First minimum = λ1(L) = min(r | Bn(0,r) ∩ L = {0}). • SVP: find v ∈ L of length λ1(L). • i-th minimum = λi(L) = min(r | Bn(0,r) ∩ L has dim ≥ i). 0 b2 b1 2004/06/17 Damien STEHLE 2/23 …