Next update: I decided that the 2012 Sage GSoC project [^1] wasn't worth the trouble, so I started afresh [^2]. The result is available as;
http://trac.sagemath.org/ticket/15976
It's fairly straight-forward and only realises integer lattices, i.e.
subgroups of ZZ^n (I don't care about the more general RR^n case and I haven't
had any feedback motivating me to change that). There's a new class which
represents such lattices by a basis which is improved during the life-time of
the lattice object.
This ticket also updates our fpLLL interface to the 4.0 API. While I was at it
I also interfaced fpLLL's BKZ and shortest vector enumeration. Hence, Sage's
BKZ got a bit faster in the process:
sage: A = sage.crypto.gen_lattice(type='random', n=1, m=160, q=2^90, seed=42)
sage: %time A.BKZ(block_size=10)[0].norm().n()
CPU times: user 7.45 s, sys: 1.28 s, total: 8.73 s
Wall time: 8.73 s
6.24499799839840
sage: %time A.BKZ(block_size=10, algorithm="NTL")[0].norm().n()
CPU times: user 14.5 s, sys: 2.7 s, total: 17.2 s
Wall time: 17.2 s
6.48074069840786
Here's a shortest vector example:
sage: A = sage.crypto.gen_lattice(type='random', n=1, m=44, q=2^90, seed=42)
sage: L = Lattice(A)
sage: %time L.shortest_vector(algorithm="pari")
CPU times: user 11.9 s, sys: 660 ms, total: 12.6 s
Wall time: 12.6 s
(0, 1, 1, -2, 1, -1, 1, 1, 0, -1, 1, -1, 2, 0, 0, 1, 1, -1, 1, 1, 0, -1, 0, 0,
0, 1, -2, -1, 0, 0, 1, -1, 1, 3, 0, -1, 0, 1, -1, -2, 1, 0, -1, -1)
sage: L = Lattice(A)
sage: %time L.shortest_vector(algorithm="fplll") # default
CPU times: user 3.31 s, sys: 0 ns, total: 3.31 s
Wall time: 3.31 s
(0, 1, 1, -2, 1, -1, 1, 1, 0, -1, 1, -1, 2, 0, 0, 1, 1, -1, 1, 1, 0, -1, 0, 0,
0, 1, -2, -1, 0, 0, 1, -1, 1, 3, 0, -1, 0, 1, -1, -2, 1, 0, -1, -1)
sage:
However, in terms of inheritance hierarchy and categories the new class is a
wasteland. The inheritance hierarchy is:
sage.structure.sage_object.SageObject
sage.lattices.integer_lattices.IntegerLattice
Any recommendations what the new class should inherit from? I guess I could at
least introduce a generic lattice class that IntegerLattice would inherit
from, like this?
sage.structure.sage_object.SageObject
sage.lattices.lattices.Lattice
sage.lattices.integer_lattices.IntegerLattice
Cheers,
Martin
[1] Btw. I still haven't managed to contact the people responsible for that
project yet to find out what went wrong. Neither student nor mentor have
replied to my e-mail yet.
[2] I did import the diamond cutting implementation
On Sunday 16 Mar 2014 20:49:22 Martin Albrecht wrote:
> Okay, I imported the code base from
>
> https://github.com/poeschko/sage
>
> here:
>
> http://trac.sagemath.org/ticket/15955
>
> I really couldn't be bothered to import patch by patch as the original
> author made an interesting - let's ignore Sage's version control - choice.
> So all his commits are in one big commit.
>
> Well, almost all:
>
> - I fixed some things to adapt the patches to the current version of Sage
> and - I didn't import the hack (I think it is) which allows to deal with
> this situation:
>
> sage: A = Matrix(ZZ, [[4,2,0],[2,1,0],[0,0,1]])
> sage: A.LLL_gram()
> ...
> ValueError: a matrix from Full MatrixSpace of 3 by 2 dense matrices over
> Integer Ring cannot be converted to a matrix in Full MatrixSpace of 3 by 3
> dense matrices over Integer Ring!
>
> I'm not sure what should be done about this. In any case, I'd appreciate a
> second set of eyes on this. Clearly, there's work to be done.
>
> Cheers,
> Martin
>
> On Thursday 13 Mar 2014 15:26:28 Burcin Erocal wrote:
> > Hi Martin,
> >
> > On Thu, 13 Mar 2014 13:56:41 +0000
> >
> > Martin Albrecht <martinralbre...@googlemail.com> wrote:
> > > what happened to the Sage 2012 GSoC project on lattices described
> > >
> > > here:
> > > http://gsoc-sage-lattices.blogspot.co.uk/
> > >
> > > It doesn't seem to have been merged (?) I could use it to give my
> > > discrete Gaussian sampler over lattices code a home.
> >
> > The code is here:
> >
> > https://github.com/poeschko/sage
> >
> > AFAICT, it would require a nontrivial amount of work to merge. It was
> > based on Sage 5.2 IIRC. I don't know if there is a related ticket on
> > trac.
> >
> >
> > Cheers,
> > Burcin
signature.asc
Description: This is a digitally signed message part.
