On Apr 20, 4:35 am, Santanu Sarkar <sarkar.santanu....@gmail.com>
wrote:
> 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-support@googlegroups.com
To unsubscribe from this group, send email to
sage-support-unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
