Closest vector from a lattice

Damien Stehle

2009-04-20 08:55:40 UTC

Let L be a lattice. Let a' be a vector outside L. How can we find
the closest vector of L from a' using SAGE or Magma?

Hi Santanu,

In Magma, you can do ClosestVectors(L, a': Max:=1);
(Max:=1 to get only one closest if there are several solutions).

In Sage, I don't know if there is a closest vectors function.
However, if a vector that is not much further
than the best one is sufficient for your application, then you may use
what is called Babai's nearest plane algorithm (it is also
much faster than any Closest Vectors function). That can be done as
follows (I call B a basis of L, and I assume we talk about column
vectors):
1- Construct the matrix B' = (B|a')
(0|C)
This matrix has one more row and one more column than B.
C' is a "large enough" constant. Max |B_{i,j}| does the job.
2- Call LLL on B' (available in SAGE and Magma). I call B2 the output.
3- Let e be the last column of B2, without the last coordinate.
Then b:=a'-e is a lattice vector close to a'.

We have ||b-a'|| <= 2^{d/2+1}.dist(a', L), if the standard LLL
parameters
are used.

Regards,
Damien

--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-***@googlegroups.com
To unsubscribe from this group, send email to sage-support-***@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---