# Brute force lattice problems

What are the easiest brute force algorithms for solving closest and shortest vector problems?

I want to find an arbitrary, but small ($\lesssim 20$) number of lattice vectors closest to a given point. Since I consider low spatial dimension of four or less, the hardness of the closest vector problem is not an important issue for me. On the other hand, I want guaranteed solutions, so no approximations. Is the easiest way to use the standard lattice reductions, such as the LLL algorithm?

-
I'd say this is almost better to ask over at mathematica.stackexchange, my bet is that if you ask nicely, you will even get working code for your problem. – Per Alexandersson Feb 27 '13 at 6:38
Thanks. I'm not searching for a Mathematica implementation (Python actually). I'm also ok implementing it myself. – Anton Akhmerov Feb 27 '13 at 18:01

I know this in the language of quadratic forms. Once you have expressed your form in any somewhat reduced form, you have $f(x) = (1/2) x^T A x$ where $A$ is a symmetric positive and integral matrix. To find all $f(x) \leq M$ what I do is find the largest possible value of each $x_i$ by Lagrange multipliers. This surrounds the ellipsoid by a rectangular shape. The diagonal entries of $A^{-1}$ are involved, as are some square roots. Then you just run a multiple loop, exhausting the rectangle thing. If this does not give enough short vectors, increase $M.$ The main point here is that you have small dimension.