MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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 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 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.

It is also possible to more precisely describe the ellipsoid, using the quadratic formula or the like, thus investigating fewer useless points. But for low dimension I would say it does not matter.

-

This sounds like you should consider the Fincke-Pohst algorithm. There are many implementations, see for example these slides.

-