In mathematics, the goal of
lattice basis reduction is given an integer
lattice basis as input, to find a
basis with short, nearly
orthogonal vectors. This is realized using different algorithms, whose running time is usually at least exponential in the dimension of the lattice.