Opened 5 years ago

Closed 5 years ago

#15976 closed enhancement (fixed)

IntegerLattice class

Reported by: malb Owned by:
Priority: major Milestone: sage-6.3
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Martin Albrecht Reviewers: Daniel Krenn, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 6957074 (Commits) Commit: 6957074e911206b46fbfa7cb64bddc32d72d7f6c
Dependencies: Stopgaps:

Description

This ticket implements sage.lattices.integer_lattice.IntegerLattice which represents a discrete subgroup of ZZn.

This class is inspired by #15955 but except for the voronoi cell implementation, it is implemented anew from scratch.

This ticket also includes an updated interface to fpLLL which uses Cython's C++ features, uses the fpLLL 4.0 API and interfaces not only with LLL but also with fpLLL's BKZ and shortest vector enumeration.

Change History (87)

comment:1 Changed 5 years ago by malb

  • Branch set to u/malb/15976_integer_lattice
  • Commit set to f9b4bdd650679c3569cbf01bf1c3cbfc8b66474e

New commits:

6bad3f6first draft of IntegerLattice class
f9b4bddmodern interface to fpLLL

comment:2 Changed 5 years ago by git

  • Commit changed from f9b4bdd650679c3569cbf01bf1c3cbfc8b66474e to 9a76b85a9836117c3efb97e474b292481f0f67ec

Branch pushed to git repo; I updated commit sha1. New commits:

9a76b85documentation changes

comment:3 Changed 5 years ago by git

  • Commit changed from 9a76b85a9836117c3efb97e474b292481f0f67ec to ab6ec77d9bda25e73b96ae81a7f88532b0e17e77

Branch pushed to git repo; I updated commit sha1. New commits:

ab6ec77actually use fpLLL in IntegerLattice.shortest_vector

comment:4 Changed 5 years ago by git

  • Commit changed from ab6ec77d9bda25e73b96ae81a7f88532b0e17e77 to a13b4aad3e9578866922d01932e6abac02687718

Branch pushed to git repo; I updated commit sha1. New commits:

a13b4aaadded more of a class hierarchy

comment:5 Changed 5 years ago by malb

  • Status changed from new to needs_review

comment:6 follow-up: Changed 5 years ago by SimonKing

Hi Martin!

You asked me to have a look at your code from the categorical point of view.

It really depends what you want to model.

Currently, you start on top of SageObject, which is about as basic as it can be. A SageObject hasn't even support for different categories. So, if for you a lattice is not more than an object, then it's fine.

A bit less basic is CategoryObject, which is for objects in arbitrary categories. In particular, it would be a suitable starting point for objects that do not have elements (i.e., whose category is not a sub-category of the category of sets). So, if you want that your lattice is a semigroup, but you do not want to implement elements of the semigroup, then it's fine---almost. AFAIK, it is mathematically possible to define the notion of a semigroup just in terms of morphisms and direct products, and it is not needed to refer to elements in the definition. However, Sage's category framework expects semigroups to be sets, and thus the TestSuite would complain that element creation fails.

If your lattices are supposed to be groups (in particular, sets), then the lattice should inherit from Parent, and you should implement elements as well, inheriting from Element (or rather ModuleElement, since you want to add elements). I guess it would be fine to import some implementation of integer vectors (I am sure those things exist somewhere in Sage), and assign it as a class attribute IntegerLattice.Element.

Next, if you decide to inherit from Parent and assign .Element, you should do self._init_category_(Groups()) (or a better category, if there is any) during initialisation of your lattice. This should be enough to enable element creation and let the test suites (TestSuite(YourLattice).run()) pass. If it isn't---well, then we'll take care of it later.

It could make sense to have a look at sage.combinat.free_module.CombinatorialFreeModule and sage.combinat.free_module.CombinatorialFreeModuleElement. I have not much experience with it, but I know that people use it to implement all kind of things, including algebras. And it does inherit from Parent.

On a different note: Would it make sense to use UniqueRepresentation or at least CachedRepresentation for lattices? It seems strange to me to have a function Lattice that does nothing more than hand the arguments to the IntegerLattice constructor and return the result.

Provided that you want some kind of caching for your lattices, you could do

class Lattice(CachedRepresentation, Parent):
    "This is a stub, non-integral lattices will be implemented later"
    Element = some.suitable.VectorClass
    @staticmethod
    def __classcall_private__(cls, basis, lll_reduce):
        # do some preprocessing of arguments, throw
        # an error if the basis is not integral
        return IntegerLattice(preprocessed_basis, lll_reduce)
    def __cmp__(...):
        # We don't inherit from UniqueRepresentation, hence, we admit the
        # possibility that different bases result in the same lattice.
        # Perhaps move this to IntegerLattice, unless the same algorithm
        # would work for general lattices.

class IntegerLattice(Lattice):
    ...
Last edited 5 years ago by SimonKing (previous) (diff)

comment:7 in reply to: ↑ 6 ; follow-up: Changed 5 years ago by malb

Replying to SimonKing:

Hi Simon,

thanks a lot for your comments!

If your lattices are supposed to be groups (in particular, sets), then the lattice should inherit from Parent, and you should implement elements as well, inheriting from Element (or rather ModuleElement, since you want to add elements). I guess it would be fine to import some implementation of integer vectors (I am sure those things exist somewhere in Sage), and assign it as a class attribute IntegerLattice.Element.

Next, if you decide to inherit from Parent and assign .Element, you should do self._init_category_(Groups()) (or a better category, if there is any) during initialisation of your lattice. This should be enough to enable element creation and let the test suites (TestSuite(YourLattice).run()) pass. If it isn't---well, then we'll take care of it later.

I tried to go down this route: I inherited from Parent and set self._init_category_(CommutativeAdditiveGroups()). The TestSuite(L).run() now first complaints that there is no _an_element_() which is easily fixable. However, the next complaint is that elements created by some_element() do not live in the lattice but in Zn. I am not sure I want my lattice vectors to live in the lattice, but if I wanted to do that, I'd have to define my lattice as a proper submodule of Zn? I'd view the lattice somewhat analogously to an ideal in a multivariate ring, would we want our ideal elements to live anywhere but the ring?

On a different note: Would it make sense to use UniqueRepresentation or at least CachedRepresentation for lattices? It seems strange to me to have a function Lattice that does nothing more than hand the arguments to the IntegerLattice constructor and return the result.

I don't want to cache my representations or make lattices unique. It is useful to have two objects representing the same lattice: one with a good basis and one with a bad basis (that's the secret and public key respectively in many crypto systems). I'd expect Lattice to grow when the need arises: lattices over Q, over R, over polynomial rings and stuff.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 5 years ago by SimonKing

Replying to malb:

However, the next complaint is that elements created by some_element() do not live in the lattice but in Zn. I am not sure I want my lattice vectors to live in the lattice, but if I wanted to do that, I'd have to define my lattice as a proper submodule of Zn?

There is something called "facade". I didn't try to fully understand it, but I think the idea is: If you have the set of prime numbers, then its elements are just natural numbers. That's to say, the parent of the elements of Primes() is ZZ, not Primes():

sage: P = Primes()
sage: p = P.an_element()
sage: p
43
sage: p.parent()
Integer Ring

This is done by telling that Primes() is a "facade set":

sage: P.category()
Category of facade infinite enumerated sets

Your situation could be similar: You have a lattice L in RR^n, and the parent of the elements of L wouldn't be L but RR^n (but please not ZZ^n, since you need the embedding!).

So, could be that using

sage: Category.join([FacadeSets(),CommutativeAdditiveGroups()])
Category of facade commutative additive groups

to initialise your lattice's category would suffice.

I'd view the lattice somewhat analogously to an ideal in a multivariate ring, would we want our ideal elements to live anywhere but the ring?

No, see above. But for historical reasons, we have

sage: P.<x,y> = QQ[]
sage: I = P*[x^2+y,y^2+x]
sage: x^2 in I
False
sage: x^2+y in I
True
sage: I.category()
Category of ring ideals in Multivariate Polynomial Ring in x, y over Rational Field

without facade. I think today it would be implemented using facades.

I don't want to cache my representations or make lattices unique. It is useful to have two objects representing the same lattice: one with a good basis and one with a bad basis (that's the secret and public key respectively in many crypto systems).

That's why I suggested CachedRepresentation rather than UniqueRepresentation. If you use CachedRepresentation than starting twice with the same basis yields identical lattices, but starting with different bases will yield non-identical lattices that may still be equal. Only UniqueRepresentation would imply a "comparison by identity".

Last edited 5 years ago by SimonKing (previous) (diff)

comment:9 in reply to: ↑ 8 Changed 5 years ago by SimonKing

Replying to SimonKing:

Your situation could be similar: You have a lattice L in RR^n, and the parent of the elements of L wouldn't be L but RR^n (but please not ZZ^n, since you need the embedding!).

Ahm, or actually it should be ZZ^n, since you have integer lattices. But this ZZ^n is a subset of RR^n and should not be confused with the fact that the lattice itself is isomorphic to ZZ^n.

comment:10 Changed 5 years ago by git

  • Commit changed from a13b4aad3e9578866922d01932e6abac02687718 to 2c8199ce1732d8766ab3fe9603697365638a8a9a

Branch pushed to git repo; I updated commit sha1. New commits:

2c8199clattices inherit from Parent, IntegerLattice is a Facade for ZZ^n

comment:11 follow-up: Changed 5 years ago by malb

Thanks Simon,

Facade seems to be exactly what I needed!

On the CachedRepresentation I think even that is too much. One could, for example, construct the same lattice twice and then run lattice reduction on one instance in order to get a good basis. The design is somewhat unusual as it changes the basis during the life-time of an object.

comment:12 Changed 5 years ago by git

  • Commit changed from 2c8199ce1732d8766ab3fe9603697365638a8a9a to 96e771e517233103b2df5ce9b350adc1c724c528

Branch pushed to git repo; I updated commit sha1. New commits:

96e771eadded HKZ reduction

comment:13 in reply to: ↑ 11 Changed 5 years ago by SimonKing

Replying to malb:

On the CachedRepresentation I think even that is too much. One could, for example, construct the same lattice twice and then run lattice reduction on one instance in order to get a good basis. The design is somewhat unusual as it changes the basis during the life-time of an object.

OK, it sounds like caching would be bad in such situation.

comment:14 Changed 5 years ago by malb

Okay, excellent. So - as far as I am concerned - our work here is done :)

comment:15 follow-up: Changed 5 years ago by darij

Are you guys sure that special characters (such as · and δ) don't break the PDF documentation? Just asking.

What exactly does the jacobi method do? Sage does have a Cholesky decomposition method, but that's different (yours is rational, which is why I'm curious). Any references or explanations? (They should also go into the docstring -- also, a doctest on something other than a scalar matrix would be nice...)

Finally, I'd suggest not using such a short and generic name for a class like Lattice which is not likely to be implemented in foreseeable future (shouldn't the inexactness of the reals prevent such class from being implementable?).

comment:16 Changed 5 years ago by git

  • Commit changed from 96e771e517233103b2df5ce9b350adc1c724c528 to 43d76e8bc29c84c72ab9ebbd1bd65a01d3fccb52

Branch pushed to git repo; I updated commit sha1. New commits:

43d76e8added lattices to reference manual and fixed pdf building errors

comment:17 in reply to: ↑ 15 Changed 5 years ago by malb

Replying to darij:

Are you guys sure that special characters (such as · and δ) don't break the PDF documentation? Just asking.

It didn't, but now it does. Thanks!

What exactly does the jacobi method do? Sage does have a Cholesky decomposition method, but that's different (yours is rational, which is why I'm curious). Any references or explanations? (They should also go into the docstring -- also, a doctest on something other than a scalar matrix would be nice...)

I cannot speak for that part of the code as it was taken on-board from the 2012 GSoC project. It seemed like the only non-trivial contribution and I didn't want to delete it. I never touched it. If no-one is comfortable with it, we can drop it though. I asked Daniel Krenn to comment (he was the mentor on that GSoC project)

Finally, I'd suggest not using such a short and generic name for a class like Lattice which is not likely to be implemented in foreseeable future (shouldn't the inexactness of the reals prevent such class from being implementable?).

I don't see the problem with the class itself, that's what namespaces are for, right? Lattice as the basic class for lattices (as discrete subgroups of RRn) seems about right. However, I do take your point with Lattice is in the global namespace (i.e. the constructor). Any recommendation?


New commits:

43d76e8added lattices to reference manual and fixed pdf building errors

New commits:

43d76e8added lattices to reference manual and fixed pdf building errors

comment:18 Changed 5 years ago by darij

Oh, if it's not in the global namespace, then it's fine. Otherwise, what about RealLattice?

comment:19 Changed 5 years ago by darij

  • Branch changed from u/malb/15976_integer_lattice to public/ticket/15976
  • Commit changed from 43d76e8bc29c84c72ab9ebbd1bd65a01d3fccb52 to fe8836f8d59facf7e8bde6542c68a6c5772e5fc3

*ignore this one*

Last edited 5 years ago by darij (previous) (diff)

comment:20 Changed 5 years ago by git

  • Commit changed from fe8836f8d59facf7e8bde6542c68a6c5772e5fc3 to d5c404c5d3a135ec9f078d0ea3c7cf23ddbf20a5

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7f5210dMerge branch 'u/malb/15976_integer_lattice' of git://trac.sagemath.org/sage into ila
d5c404cjacobi method documented (and now without cruft from other branch)

comment:21 Changed 5 years ago by darij

OK, so the method does do something like Cholesky decomposition, except that it never takes square roots and has some diagonal factors. (Don't get me wrong: this makes the method more useful, not wrong.) I've added documentation. Warning: branch change.

I fear this is all I can do for this ticket, though...

comment:22 Changed 5 years ago by git

  • Commit changed from d5c404c5d3a135ec9f078d0ea3c7cf23ddbf20a5 to f5e8e1661c9313bb6167d8da4b646df10ce7b422

Branch pushed to git repo; I updated commit sha1. New commits:

f5e8e16Lattice -> RealLattice

comment:23 follow-up: Changed 5 years ago by malb

I renamed Lattice to RealLattice

comment:24 in reply to: ↑ 23 Changed 5 years ago by dimpase

Replying to malb:

I renamed Lattice to RealLattice

bad choice, IMHO. People will want to have lattices in things like Cn

comment:25 Changed 5 years ago by malb

Suggestions? Lattice seems to be too general for many, RealLattice too specific for others. ComplexLattice doesn't really seem to make much sense because one normally thinks of a lattice as a discrete subgroup of Rn (at least in my neck of the woods).

comment:26 Changed 5 years ago by dimpase

How about VectorSpaceLattice ? (well, not all fields might be supported, but still).

comment:27 follow-up: Changed 5 years ago by malb

Wouldn't people confuse that with vector lattices? Or is that not a common notion? cf. http://www.stat.yale.edu/~pollard/Books/Asymptopia/old-Vectorlattice.pdf

I do have to admit that I also find it a bit awkward but that's clearly a question of taste.

comment:28 Changed 5 years ago by git

  • Commit changed from f5e8e1661c9313bb6167d8da4b646df10ce7b422 to e0f6e3c9dce8568e4d27201c35d7fbbfad1e1b88

Branch pushed to git repo; I updated commit sha1. New commits:

e0f6e3cfixed copyright notice

comment:29 in reply to: ↑ 27 Changed 5 years ago by dimpase

Replying to malb:

Wouldn't people confuse that with vector lattices? Or is that not a common notion? cf. http://www.stat.yale.edu/~pollard/Books/Asymptopia/old-Vectorlattice.pdf

I do have to admit that I also find it a bit awkward but that's clearly a question of taste.

hmm, OK, how about AdditiveTorsionFreeAbelianGroup ? This would avoid that other lattices all together...

comment:30 Changed 5 years ago by malb

now that's just mean … for now VectorSpaceLattice seems to be a winner.

comment:31 Changed 5 years ago by git

  • Commit changed from e0f6e3c9dce8568e4d27201c35d7fbbfad1e1b88 to f1686df7df460ed0f559d2747d84df26e992e016

Branch pushed to git repo; I updated commit sha1. New commits:

f1686dfremoved sage.lattices and mode sage.lattices.integer_lattice to sage.modules.free_module_integer

comment:32 Changed 5 years ago by git

  • Commit changed from f1686df7df460ed0f559d2747d84df26e992e016 to 34734a15420206c4bfb64fb85f619bed3d3177a4

Branch pushed to git repo; I updated commit sha1. New commits:

37b3baafixed documentation
34734a1guard shortest vector computation with sig_on/sig_off

comment:33 Changed 5 years ago by malb

The patch is a lot less invasive now, anyone up for reviewing it?

comment:34 Changed 5 years ago by git

  • Commit changed from 34734a15420206c4bfb64fb85f619bed3d3177a4 to eb352dbefccf698b3fd26e25b0c532ad5efc1e5f

Branch pushed to git repo; I updated commit sha1. New commits:

9872997Merge branch 'develop' of trac.sagemath.org:sage into integer_lattices
eb352dbMerge branch 'develop' of trac.sagemath.org:sage into integer_lattices

comment:35 Changed 5 years ago by git

  • Commit changed from eb352dbefccf698b3fd26e25b0c532ad5efc1e5f to 44d20d522b5a1db31ca1cfb1c5de4effe6558cb8

Branch pushed to git repo; I updated commit sha1. New commits:

44d20d5fixed incomplete merge

comment:36 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:37 Changed 5 years ago by git

  • Commit changed from 44d20d522b5a1db31ca1cfb1c5de4effe6558cb8 to a561d3691fe0cdfb824c6313fb254c7220c430b6

Branch pushed to git repo; I updated commit sha1. New commits:

ca9da0bcorrected whitespaces; rewrote long lines
7b8f9dccorrected whitespace errors, rewrote long lines (in fplll.pxi)
54d680bwhitespace-corrections; long-line rewritings; PEP8; ``...`` in docstrings
df2cfe6corrected whitespace errors; rewrote long lines; rewrote one "if"; ``...`` in doctests
d96702ewhitespace errors
135750ewhitespace errors, PEP8
545af88trailing whitespaces removed
a561d36changed sage.lattices to sage.modules in doctests (so they pass)

comment:38 follow-up: Changed 5 years ago by dkrenn

I've uploaded a couple of minor changes made during review (most of them are whitespace corrections, PEP8, rewriting of long lines, adding ... in documentation.

Here some further comments:

  • diff --git a/src/doc/common/conf.py b/src/doc/common/conf.py
    index 25dd9f0..ff9efe3 100644
    --- a/src/doc/common/conf.py
    +++ b/src/doc/common/conf.py
    @@ -296,6 +296,13 @@ latex_elements['preamble'] = r"""
     \DeclareUnicodeCharacter{2510}{+}
     \DeclareUnicodeCharacter{2514}{+}
     \DeclareUnicodeCharacter{2518}{+}
    +\DeclareUnicodeCharacter{03BC}{\mu}
    +\DeclareUnicodeCharacter{03B4}{\delta}
    +\DeclareUnicodeCharacter{03B7}{\eta}
    +\DeclareUnicodeCharacter{03BB}{\lambda}
    +\DeclareUnicodeCharacter{2266}{\le}
    +\DeclareUnicodeCharacter{221A}{\sqrt}
    

I'd appreciate if someone else can make a short review on this part, since I do not know what should be done. (It seems that the code works, but I just don't know if this is how it is done; probably yes).

  • changes in fplll.*: The changes look fine for me and the code seem to work. I have to say, I am not really familiar with the fplll interface, so maybe someone else can look at this code (but for me it is positive_review on this part).
  • diff --git a/src/sage/libs/fplll/fplll.pyx b/src/sage/libs/fplll/fplll.pyx
    index 59cd53e..b28f5c9 100644
    --- a/src/sage/libs/fplll/fplll.pyx
    +++ b/src/sage/libs/fplll/fplll.pyx
    @@ -18,6 +18,7 @@ AUTHORS:
    +#       Copyright (C) 2014 Martin Albrecht <martinralbecht@googlemailc.om>
                                                       ^^^^               ^^^^
    

Is this on purpose?

  • fplll.pyx: OUTPUT-blocks are missing (although, most of them will state "Nothing") (The developerguide does not say that those can be skipped if nothing is returned...)
  • fplll.pyx: Sometimes there are empty lines between two input-descriptions (in INPUT-block), sometimes not. This should be done in the same way everywhere.
  • fplll.pyx: def BKZ: In the INPUT-block you can find the following:
            - ``block_size`` - 0 < block size <= nrows
    
            - ``no_lll`` - 
            - ``bounded_lll`` -
    

The first line looks a bit weird, since this is a mixture of math and verbated text written plain. Maybe add ... or ... there? The last two don't have any description.

  • I am not sure which of the following one should prefer for default: 0: 0 or 0 or 0?

(I have a slight preference for 0). But this should be done in the same way everywhere.

  • matrix_integer_dense.pyx:
            - ``prune`` - The optional parameter ``prune`` can be set to any
               positive number to invoke the Volume Heuristic from [Schnorr and
               Horner, Eurocrypt '95]. This can significantly reduce the running
               time, and hence allow much bigger block size, but the quality of the
               reduction is of course not as good in general. Higher values of
               ``prune`` mean better quality, and slower running time. When
               ``prune`` == 0, pruning is disabled. Recommended usage: for
               ``block_size`` = 30, set 10 = ``prune`` = 15.
    

The last few lines (== 0, = 30, 10 = prune = 15) look a bit weird.

  • matrix_integer_dense.pyx:
            fpLLL SPECIFIC INPUTS:
    
            - ``precision`` - bit precision to use if ``fp=='rr'`` (default: 0 for automatic choice)
                                                 = here ^^^^^^^^ ?
    
  • in matrix_integer_dense.pyx: Sometimes there is OUTPUT: an integer. Shouldn't this be in separate lines?
  • A couple of times the descriptions in the INPUT-block end with a full-stop; most of the times not.
  • free_module_integer.py: Some missing OUTPUT-blocks
  • SCORE src/sage/libs/fplll/fplll.pyx: 89.5% (17 of 19)
    
    Missing documentation:
         * line 492: def HKZ(self)
    
    Missing doctests:
         * line 499: def shortest_vector(self, method=None)
    

Apart from those minor things, everything else looks good.

comment:39 Changed 5 years ago by git

  • Commit changed from a561d3691fe0cdfb824c6313fb254c7220c430b6 to 142e8da1f1b387a5a2ea2d278f29e91d97930aac

Branch pushed to git repo; I updated commit sha1. New commits:

142e8daMerge branch 'develop' into integer_lattices

comment:40 in reply to: ↑ 38 ; follow-up: Changed 5 years ago by malb

Replying to dkrenn:

I've uploaded a couple of minor changes made during review (most of them are whitespace corrections, PEP8, rewriting of long lines, adding ... in documentation.

Thanks!

Here some further comments:

  • diff --git a/src/doc/common/conf.py b/src/doc/common/conf.py
    index 25dd9f0..ff9efe3 100644
    --- a/src/doc/common/conf.py
    +++ b/src/doc/common/conf.py
    @@ -296,6 +296,13 @@ latex_elements['preamble'] = r"""
     \DeclareUnicodeCharacter{2510}{+}
     \DeclareUnicodeCharacter{2514}{+}
     \DeclareUnicodeCharacter{2518}{+}
    +\DeclareUnicodeCharacter{03BC}{\mu}
    +\DeclareUnicodeCharacter{03B4}{\delta}
    +\DeclareUnicodeCharacter{03B7}{\eta}
    +\DeclareUnicodeCharacter{03BB}{\lambda}
    +\DeclareUnicodeCharacter{2266}{\le}
    +\DeclareUnicodeCharacter{221A}{\sqrt}
    

I'd appreciate if someone else can make a short review on this part, since I do not know what should be done. (It seems that the code works, but I just don't know if this is how it is done; probably yes).

This essentially allows to write UTF-8 characters like δ directly, which makes the documentation easier to read.

  • diff --git a/src/sage/libs/fplll/fplll.pyx b/src/sage/libs/fplll/fplll.pyx
    index 59cd53e..b28f5c9 100644
    --- a/src/sage/libs/fplll/fplll.pyx
    +++ b/src/sage/libs/fplll/fplll.pyx
    @@ -18,6 +18,7 @@ AUTHORS:
    +#       Copyright (C) 2014 Martin Albrecht <martinralbecht@googlemailc.om>
                                                       ^^^^               ^^^^
    

Is this on purpose?

Fixed.

  • fplll.pyx: OUTPUT-blocks are missing (although, most of them will state "Nothing") (The developerguide does not say that those can be skipped if nothing is returned...)

I added those.

  • fplll.pyx: Sometimes there are empty lines between two input-descriptions (in INPUT-block), sometimes not. This should be done in the same way everywhere.

I should have fixed all of those.

  • fplll.pyx: def BKZ: In the INPUT-block you can find the following:
            - ``block_size`` - 0 < block size <= nrows
    
            - ``no_lll`` - 
            - ``bounded_lll`` -
    

The first line looks a bit weird, since this is a mixture of math and verbated text written plain. Maybe add ... or ... there? The last two don't have any description.

Fixed.

  • I am not sure which of the following one should prefer for default: 0: 0 or 0 or 0?

(I have a slight preference for 0). But this should be done in the same way everywhere.

I opted for 0 so that True etc. look the same?

  • matrix_integer_dense.pyx:
            - ``prune`` - The optional parameter ``prune`` can be set to any
               positive number to invoke the Volume Heuristic from [Schnorr and
               Horner, Eurocrypt '95]. This can significantly reduce the running
               time, and hence allow much bigger block size, but the quality of the
               reduction is of course not as good in general. Higher values of
               ``prune`` mean better quality, and slower running time. When
               ``prune`` == 0, pruning is disabled. Recommended usage: for
               ``block_size`` = 30, set 10 = ``prune`` = 15.
    

The last few lines (== 0, = 30, 10 = prune = 15) look a bit weird.

Fixed.

  • matrix_integer_dense.pyx:
            fpLLL SPECIFIC INPUTS:
    
            - ``precision`` - bit precision to use if ``fp=='rr'`` (default: 0 for automatic choice)
                                                 = here ^^^^^^^^ ?
    

I don't understand this point, fp='rr' is a valid parameter.

  • in matrix_integer_dense.pyx: Sometimes there is OUTPUT: an integer. Shouldn't this be in separate lines?

I fixed those.

  • A couple of times the descriptions in the INPUT-block end with a full-stop; most of the times not.

I tried to unify those.

  • free_module_integer.py: Some missing OUTPUT-blocks

Fixed.

  • SCORE src/sage/libs/fplll/fplll.pyx: 89.5% (17 of 19)
    
    Missing documentation:
         * line 492: def HKZ(self)
    
    Missing doctests:
         * line 499: def shortest_vector(self, method=None)
    

Fixed.

Apart from those minor things, everything else looks good.

comment:41 Changed 5 years ago by git

  • Commit changed from 142e8da1f1b387a5a2ea2d278f29e91d97930aac to 301e4e43b3523d46ae8042845a248daa47953cd8

Branch pushed to git repo; I updated commit sha1. New commits:

0388757addressed Daniel Krenn's review comments
301e4e4more doctest cleanup

comment:42 Changed 5 years ago by git

  • Commit changed from 301e4e43b3523d46ae8042845a248daa47953cd8 to d6151ee73c58fbc7da45ed151f47a84dc4cafe5b

Branch pushed to git repo; I updated commit sha1. New commits:

497accafixed doctest failure
d6151eeremoved IntegerLattice from global namespace

comment:43 Changed 5 years ago by malb

I figured I should make a conservative choice and removed IntegerLattice from the global name space. This way, the stakes of accepting this ticket are a lot lower.

comment:44 in reply to: ↑ 40 ; follow-up: Changed 5 years ago by dkrenn

Replying to malb:

  • matrix_integer_dense.pyx:
            fpLLL SPECIFIC INPUTS:
    
            - ``precision`` - bit precision to use if ``fp=='rr'`` (default: 0 for automatic choice)
                                                 = here ^^^^^^^^ ?
    

I don't understand this point, fp='rr' is a valid parameter.

Yes it is. Therefore I'd prefer fp='rr', since this parameter is specified like this and not testing for equality with ==.

comment:45 Changed 5 years ago by git

  • Commit changed from d6151ee73c58fbc7da45ed151f47a84dc4cafe5b to c44aac98058522aac15042e1d986422f5d818ae0

Branch pushed to git repo; I updated commit sha1. New commits:

c44aac9fp=='rr' → fp='rr'

comment:46 in reply to: ↑ 44 Changed 5 years ago by malb

Replying to dkrenn:

Yes it is. Therefore I'd prefer fp='rr', since this parameter is specified like this and not testing for equality with ==.

Ah, gotcha. Fixed. Thanks!

comment:47 Changed 5 years ago by git

  • Commit changed from c44aac98058522aac15042e1d986422f5d818ae0 to 8241fa60528b8c73f69ca6e0fa8d652ddb815f25

Branch pushed to git repo; I updated commit sha1. New commits:

8241fa6corrected trailing whitespaces

comment:48 Changed 5 years ago by dkrenn

Thanks for your changes. Look good.

There is one problem: the documentation does not build:

[modules  ] /local/data/krenn/sage-develop/local/lib/python2.7/site-packages/sage/modules/free_module_integer.py:docstring of sage.modules.free_module_integer:3: WARNING: Bullet list ends without a blank line; unexpected unindent.
[modules  ] /local/data/krenn/sage-develop/local/lib/python2.7/site-packages/sage/modules/free_module_integer.py:docstring of sage.modules.free_module_integer:6: WARNING: Block quote ends without a blank line; unexpected unindent.
Error building the documentation.
Traceback (most recent call last):
  File "/local/data/krenn/sage-develop/src/doc/common/builder.py", line 1477, in <module>
    getattr(get_builder(name), type)()
  File "/local/data/krenn/sage-develop/src/doc/common/builder.py", line 276, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/local/data/krenn/sage-develop/src/doc/common/builder.py", line 487, in _wrapper
    x.get(99999)
  File "/local/data/krenn/sage-develop/local/lib/python/multiprocessing/pool.py", line 554, in get
    raise self._value
OSError: [modules  ] /local/data/krenn/sage-develop/local/lib/python2.7/site-packages/sage/modules/free_module_integer.py:docstring of sage.modules.free_module_integer:3: WARNING: Bullet list ends without a blank line; unexpected unindent.

make: *** [doc-html] Fehler 1

comment:49 follow-up: Changed 5 years ago by malb

Thanks! I'm trying to fix it, but the error message doesn't seem very helpful:

OSError: [modules  ] /local/data/krenn/sage-develop/local/lib/python2.7/site-packages/sage/modules/free_module_integer.py:docstring of sage.modules.free_module_integer:3: WARNING: Bullet list ends without a blank line; unexpected unindent.

The error doesn't seem to actually be in line 3 of the file.

comment:50 in reply to: ↑ 49 Changed 5 years ago by dkrenn

Replying to malb:

Thanks! I'm trying to fix it, but the error message doesn't seem very helpful:

OSError: [modules  ] /local/data/krenn/sage-develop/local/lib/python2.7/site-packages/sage/modules/free_module_integer.py:docstring of sage.modules.free_module_integer:3: WARNING: Bullet list ends without a blank line; unexpected unindent.

The error doesn't seem to actually be in line 3 of the file.

That is true. I had this (and similar error messages) a couple of times and amost every time I had to solve it by a divide-and-conquer-comment-out procedure...

comment:51 Changed 5 years ago by git

  • Commit changed from 8241fa60528b8c73f69ca6e0fa8d652ddb815f25 to a69e50e7f56a513ecec65635ff414d635adbb86d

Branch pushed to git repo; I updated commit sha1. New commits:

a69e50efixed BKZ link

comment:52 Changed 5 years ago by dkrenn

Maybe one should also rewrite references like

[Schnorr and Horner, Eurocrypt '95]

into a true reference as in

This docstring is referencing [SC]_. Just remember that references
are global, so we can also reference to [Nat2000]_ in the ALGORITHM
block, even if it is in a separate file. However we would not
include the reference here since it would cause a conflict.

REFERENCES:

.. [SC] Conventions for coding in sage.
   http://www.sagemath.org/doc/developer/conventions.html.

(copied from the developer guide)

comment:53 Changed 5 years ago by dkrenn

  • Status changed from needs_review to needs_work

comment:54 Changed 5 years ago by git

  • Commit changed from a69e50e7f56a513ecec65635ff414d635adbb86d to 03ebecd8beb3486446bf13ff63b4d69fd72ca98d

Branch pushed to git repo; I updated commit sha1. New commits:

03ebecdfixed documentation

comment:55 Changed 5 years ago by git

  • Commit changed from 03ebecd8beb3486446bf13ff63b4d69fd72ca98d to ce5faa250fe5beacb9eb79b7e4b7a766ed5abff6

Branch pushed to git repo; I updated commit sha1. New commits:

ce5faa2more doc cleanup

comment:56 Changed 5 years ago by malb

  • Status changed from needs_work to needs_review

I think it got them all now.

comment:57 Changed 5 years ago by dkrenn

Everything looks good now. Doctests are still running...

comment:58 Changed 5 years ago by dkrenn

  • Reviewers set to Daniel Krenn
  • Status changed from needs_review to positive_review

comment:59 Changed 5 years ago by malb

Whooohoo! Thank you so much!

comment:60 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

Please merge in the latest beta and resolve the doctest failurues

sage -t --long src/sage/modules/free_module_integer.py
**********************************************************************
File "src/sage/modules/free_module_integer.py", line 437, in sage.modules.free_module_integer.FreeModule_submodule_with_basis_integer.BKZ
Failed example:
    L.LLL()
Expected:
    100 x 100 dense matrix over Integer Ring
Got:
    100 x 100 dense matrix over Integer Ring (use the '.str()' method to see the entries)

On a related note, how is the doctest runtime on 100x100 matrices... is this the smallest example that provides adequate test coverage?

comment:61 Changed 5 years ago by git

  • Commit changed from ce5faa250fe5beacb9eb79b7e4b7a766ed5abff6 to 95c1dd92891fb2405cb1f8e0384cef0305a2b9e1

Branch pushed to git repo; I updated commit sha1. New commits:

95c1dd9mark long doctest as #long and reduce lattice dimension in other

comment:62 Changed 5 years ago by malb

Running times are okay, but I reduced the dimension to 60 anyway. Also, I marked a long doctest as long (a voronoi cell computation).

sage: from sage.modules.free_module_integer import IntegerLattice
sage: A = sage.crypto.gen_lattice(type='random', n=1, m=100, q=2^60, seed=42)
sage: L = IntegerLattice(A, lll_reduce=False)
sage: min(v.norm().n() for v in L.reduced_basis)
4.17330740711759e15

sage: %time L.LLL()
CPU times: user 268 ms, sys: 0 ns, total: 268 ms
Wall time: 269 ms
100 x 100 dense matrix over Integer Ring

sage: %time L.BKZ(block_size=10)
CPU times: user 1.25 s, sys: 0 ns, total: 1.25 s
Wall time: 1.25 s
100 x 100 dense matrix over Integer Ring

However, doctests pass on my machine, which is strange.

$./sage -version
Sage Version 6.3.beta0, Release Date: 2014-05-10

New commits:

95c1dd9mark long doctest as #long and reduce lattice dimension in other
Last edited 5 years ago by malb (previous) (diff)

comment:63 Changed 5 years ago by vbraun

Latest beta = 6.3.beta1

comment:64 Changed 5 years ago by git

  • Commit changed from 95c1dd92891fb2405cb1f8e0384cef0305a2b9e1 to 4f6b44e9a1e3530409d4e9317e852a024093ee36

Branch pushed to git repo; I updated commit sha1. New commits:

30a99bfMerge branch 'develop' of trac.sagemath.org:sage into integer_lattices
4f6b44efixed doctest failures with latest Sage beta

comment:65 Changed 5 years ago by malb

Doctests fixed ... sorry, I missed beta1 somehow before.

Last edited 5 years ago by malb (previous) (diff)

comment:66 Changed 5 years ago by malb

  • Status changed from needs_work to needs_review

comment:67 Changed 5 years ago by dkrenn

  • Status changed from needs_review to positive_review

Reviewed changes.....positive.

comment:68 follow-up: Changed 5 years ago by tscrim

There's a couple of little things scattered throughout that I think should be fixed before this gets merged. For example, in the LLL definition, you have non-ascii characters where I think you should just use the latex equivalents. The reference should be:

.. [Ref] blah on first line that needs continuing on
   the second line

(you have one space less and would be slightly surprised the doc builds and has well-formatted output). You could likely benefit from raw string formatting:

def foo():
    r"""
    The r in front makes this a "raw" string, so the backslash isn't an
    escape character. So you can do things like this: `\ZZ` and `\alpha`.
    """
    pass

Bring stuff up to python3 compliance. I can go through and do these things tomorrow morning if you don't mind the tweaks (and/or don't do it while I sleep :P).

comment:69 Changed 5 years ago by dkrenn

  • Status changed from positive_review to needs_work

comment:70 in reply to: ↑ 68 Changed 5 years ago by malb

Replying to tscrim:

There's a couple of little things scattered throughout that I think should be fixed before this gets merged. For example, in the LLL definition, you have non-ascii characters where I think you should just use the latex equivalents.

I disagree, using UTF-8 makes it a lot more readable and compact. Changing it to TeX would be a step backward IMHO.

The reference should be:

.. [Ref] blah on first line that needs continuing on
   the second line

(you have one space less and would be slightly surprised the doc builds and has well-formatted output).

The documentation builds and - as far as I can tell - has well formated output. If you'd prefer it to be aligned for consistency, I'm not objecting.

You could likely benefit from raw string formatting:

def foo():
    r"""
    The r in front makes this a "raw" string, so the backslash isn't an
    escape character. So you can do things like this: `\ZZ` and `\alpha`.
    """
    pass

I know this exists, but I find `\\ZZ` more straight-forward. I don't think it needs to be changed, but if you prefer it differently, feel free to go ahead.

Bring stuff up to python3 compliance.

Python 3 compliance would be good :)

I can go through and do these things tomorrow morning if you don't mind the tweaks (and/or don't do it while I sleep :P).

Thanks.

comment:71 Changed 5 years ago by dkrenn

  • Work issues set to python3

comment:72 Changed 5 years ago by git

  • Commit changed from 4f6b44e9a1e3530409d4e9317e852a024093ee36 to 2317917181aa1721c02d24b8b6c0df906cb0adae

Branch pushed to git repo; I updated commit sha1. New commits:

f07b046Documentation cleanup and python 3.
2317917Some more documentation tweaks and added free_module_integer.py to doctree.

comment:73 Changed 5 years ago by tscrim

  • Branch changed from public/ticket/15976 to public/ticket/15976-latex
  • Commit changed from 2317917181aa1721c02d24b8b6c0df906cb0adae to 8271e3c0b885b0c1ca70e40538053ddf0dec7165
  • Reviewers changed from Daniel Krenn to Daniel Krenn, Travis Scrimshaw
  • Status changed from needs_work to needs_review
  • Work issues python3 deleted

Okay, I've made a bunch of fixes and tweaks. I've created a separate branch which changes the UTF to latex and adds fplll to the doc as well. IMO, the latex version looks better in the html doc (and in the pdf, you've made it so they are the same). However if you really prefer to keep it with the UTF, then you can switch the branch back and set a positive review on that one (after checking it of course).

PS - I remember that it used to be that the references would fail to build if they weren't aligned properly. Good to know it's more robust now.


New commits:

8271e3cAdded fplll to doc and changed utf to latex.

comment:74 Changed 5 years ago by malb

  • Status changed from needs_review to positive_review

looks okay, thanks.

comment:75 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

Conflicts with #16216

comment:76 Changed 5 years ago by git

  • Commit changed from 8271e3c0b885b0c1ca70e40538053ddf0dec7165 to 1eb090aa279265fefc535b73e002be07b816eb55

Branch pushed to git repo; I updated commit sha1. New commits:

f623de2generated changes from "== None" to "is None"
6a2e806manual fixup of the generated changes
f87a26fMerge branch 'develop' into u/wluebbe/ticket/16216b
564c73ctrac #16216: undo a mistake from the last merge
67546camerging #16216
1eb090afixed doctest failures

comment:77 Changed 5 years ago by malb

  • Status changed from needs_work to needs_review

merged

comment:78 Changed 5 years ago by vbraun

  • Branch changed from public/ticket/15976-latex to 1eb090aa279265fefc535b73e002be07b816eb55
  • Resolution set to fixed
  • Status changed from needs_review to closed

comment:79 Changed 5 years ago by vbraun

  • Commit 1eb090aa279265fefc535b73e002be07b816eb55 deleted

PDF docs fail:

! Package inputenc Error: Unicode char \u8:̣ not set up for use with LaTeX.

See the inputenc package documentation for explanation.
Type  H <return>  for immediate help.
 ...                                              
                                                  
l.24326 A lattice $(b_1, b_2, ..., b_d)$ is $(̣
                                                δ, η)$-LLL-reduced
? 
! Emergency stop.

I think there is a zero-width space or something like that before the delta. But really, why did you remove the original TeX codes?

comment:80 Changed 5 years ago by vbraun

  • Branch changed from 1eb090aa279265fefc535b73e002be07b816eb55 to public/ticket/15976-latex
  • Commit set to 1eb090aa279265fefc535b73e002be07b816eb55
  • Resolution fixed deleted
  • Status changed from closed to new

Last 10 new commits:

4f6b44efixed doctest failures with latest Sage beta
f07b046Documentation cleanup and python 3.
2317917Some more documentation tweaks and added free_module_integer.py to doctree.
8271e3cAdded fplll to doc and changed utf to latex.
f623de2generated changes from "== None" to "is None"
6a2e806manual fixup of the generated changes
f87a26fMerge branch 'develop' into u/wluebbe/ticket/16216b
564c73ctrac #16216: undo a mistake from the last merge
67546camerging #16216
1eb090afixed doctest failures

comment:81 Changed 5 years ago by vbraun

In fact, there is a http://www.fileformat.info/info/unicode/char/0323/index.htm before the delta (depending on your editor you see a dot below the delta)

comment:82 Changed 5 years ago by git

  • Commit changed from 1eb090aa279265fefc535b73e002be07b816eb55 to 6957074e911206b46fbfa7cb64bddc32d72d7f6c

Branch pushed to git repo; I updated commit sha1. New commits:

6957074fixed make doc-pdf

comment:83 Changed 5 years ago by malb

  • Status changed from new to needs_review

should be fixed now.

comment:84 Changed 5 years ago by malb

What's the policy on such "doctest failure" like fixes? Does someone have to review them or is it enough to check it again using the automatic tools checking such things?

comment:85 Changed 5 years ago by vbraun

Use your own judgement... but if you set it back to positive review you better be sure that it works ;-)

comment:86 Changed 5 years ago by malb

  • Status changed from needs_review to positive_review

living on the edge … it did work on my machine :)

comment:87 Changed 5 years ago by vbraun

  • Branch changed from public/ticket/15976-latex to 6957074e911206b46fbfa7cb64bddc32d72d7f6c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.