Opened 7 years ago

Closed 7 years ago

# IntegerLattice class

Reported by: Owned by: malb major sage-6.3 linear algebra Martin Albrecht Daniel Krenn, Travis Scrimshaw N/A 6957074

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

### comment:1 Changed 7 years ago by malb

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

New commits:

 ​6bad3f6 first draft of IntegerLattice class ​f9b4bdd modern interface to fpLLL

### comment:2 Changed 7 years ago by git

• Commit changed from f9b4bdd650679c3569cbf01bf1c3cbfc8b66474e to 9a76b85a9836117c3efb97e474b292481f0f67ec

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

 ​9a76b85 documentation changes

### comment:3 Changed 7 years ago by git

• Commit changed from 9a76b85a9836117c3efb97e474b292481f0f67ec to ab6ec77d9bda25e73b96ae81a7f88532b0e17e77

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

 ​ab6ec77 actually use fpLLL in IntegerLattice.shortest_vector

### comment:4 Changed 7 years ago by git

• Commit changed from ab6ec77d9bda25e73b96ae81a7f88532b0e17e77 to a13b4aad3e9578866922d01932e6abac02687718

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

 ​a13b4aa added more of a class hierarchy

### comment:5 Changed 7 years ago by malb

• Status changed from new to needs_review

### comment:6 follow-up: ↓ 7 Changed 7 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 7 years ago by SimonKing (previous) (diff)

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

Hi Simon,

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: ↓ 9 Changed 7 years ago by SimonKing

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()])


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


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 7 years ago by SimonKing (previous) (diff)

### comment:9 in reply to: ↑ 8 Changed 7 years ago by 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 7 years ago by git

• Commit changed from a13b4aad3e9578866922d01932e6abac02687718 to 2c8199ce1732d8766ab3fe9603697365638a8a9a

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

 ​2c8199c lattices inherit from Parent, IntegerLattice is a Facade for ZZ^n

### comment:11 follow-up: ↓ 13 Changed 7 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 7 years ago by git

• Commit changed from 2c8199ce1732d8766ab3fe9603697365638a8a9a to 96e771e517233103b2df5ce9b350adc1c724c528

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

 ​96e771e added HKZ reduction

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

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 7 years ago by malb

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

### comment:15 follow-up: ↓ 17 Changed 7 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 7 years ago by git

• Commit changed from 96e771e517233103b2df5ce9b350adc1c724c528 to 43d76e8bc29c84c72ab9ebbd1bd65a01d3fccb52

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

 ​43d76e8 added lattices to reference manual and fixed pdf building errors

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

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:

 ​43d76e8 added lattices to reference manual and fixed pdf building errors

New commits:

 ​43d76e8 added lattices to reference manual and fixed pdf building errors

### comment:18 Changed 7 years ago by darij

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

### comment:19 Changed 7 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 7 years ago by darij (previous) (diff)

### comment:20 Changed 7 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:

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

### comment:21 Changed 7 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 7 years ago by git

• Commit changed from d5c404c5d3a135ec9f078d0ea3c7cf23ddbf20a5 to f5e8e1661c9313bb6167d8da4b646df10ce7b422

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

 ​f5e8e16 Lattice -> RealLattice

### comment:23 follow-up: ↓ 24 Changed 7 years ago by malb

I renamed Lattice to RealLattice

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

I renamed Lattice to RealLattice

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

### comment:25 Changed 7 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 7 years ago by dimpase

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

### comment:27 follow-up: ↓ 29 Changed 7 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 7 years ago by git

• Commit changed from f5e8e1661c9313bb6167d8da4b646df10ce7b422 to e0f6e3c9dce8568e4d27201c35d7fbbfad1e1b88

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

 ​e0f6e3c fixed copyright notice

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

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 7 years ago by malb

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

### comment:31 Changed 7 years ago by git

• Commit changed from e0f6e3c9dce8568e4d27201c35d7fbbfad1e1b88 to f1686df7df460ed0f559d2747d84df26e992e016

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

 ​f1686df removed sage.lattices and mode sage.lattices.integer_lattice to sage.modules.free_module_integer

### comment:32 Changed 7 years ago by git

• Commit changed from f1686df7df460ed0f559d2747d84df26e992e016 to 34734a15420206c4bfb64fb85f619bed3d3177a4

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

 ​37b3baa fixed documentation ​34734a1 guard shortest vector computation with sig_on/sig_off

### comment:33 Changed 7 years ago by malb

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

### comment:34 Changed 7 years ago by git

• Commit changed from 34734a15420206c4bfb64fb85f619bed3d3177a4 to eb352dbefccf698b3fd26e25b0c532ad5efc1e5f

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

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

### comment:35 Changed 7 years ago by git

• Commit changed from eb352dbefccf698b3fd26e25b0c532ad5efc1e5f to 44d20d522b5a1db31ca1cfb1c5de4effe6558cb8

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

 ​44d20d5 fixed incomplete merge

### comment:36 Changed 7 years ago by vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

### comment:37 Changed 7 years ago by git

• Commit changed from 44d20d522b5a1db31ca1cfb1c5de4effe6558cb8 to a561d3691fe0cdfb824c6313fb254c7220c430b6

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

 ​ca9da0b corrected whitespaces; rewrote long lines ​7b8f9dc corrected whitespace errors, rewrote long lines (in fplll.pxi) ​54d680b whitespace-corrections; long-line rewritings; PEP8; ... in docstrings ​df2cfe6 corrected whitespace errors; rewrote long lines; rewrote one "if"; ... in doctests ​d96702e whitespace errors ​135750e whitespace errors, PEP8 ​545af88 trailing whitespaces removed ​a561d36 changed sage.lattices to sage.modules in doctests (so they pass)

### comment:38 follow-up: ↓ 40 Changed 7 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.

• 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:
^^^^               ^^^^


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 7 years ago by git

• Commit changed from a561d3691fe0cdfb824c6313fb254c7220c430b6 to 142e8da1f1b387a5a2ea2d278f29e91d97930aac

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

 ​142e8da Merge branch 'develop' into integer_lattices

### comment:40 in reply to: ↑ 38 ; follow-up: ↓ 44 Changed 7 years ago by malb

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!

• 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:
^^^^               ^^^^


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

• 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 7 years ago by git

• Commit changed from 142e8da1f1b387a5a2ea2d278f29e91d97930aac to 301e4e43b3523d46ae8042845a248daa47953cd8

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

 ​0388757 addressed Daniel Krenn's review comments ​301e4e4 more doctest cleanup

### comment:42 Changed 7 years ago by git

• Commit changed from 301e4e43b3523d46ae8042845a248daa47953cd8 to d6151ee73c58fbc7da45ed151f47a84dc4cafe5b

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

 ​497acca fixed doctest failure ​d6151ee removed IntegerLattice from global namespace

### comment:43 Changed 7 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: ↓ 46 Changed 7 years ago by dkrenn

• 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 7 years ago by git

• Commit changed from d6151ee73c58fbc7da45ed151f47a84dc4cafe5b to c44aac98058522aac15042e1d986422f5d818ae0

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

 ​c44aac9 fp=='rr' → fp='rr'

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

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 7 years ago by git

• Commit changed from c44aac98058522aac15042e1d986422f5d818ae0 to 8241fa60528b8c73f69ca6e0fa8d652ddb815f25

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

 ​8241fa6 corrected trailing whitespaces

### comment:48 Changed 7 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: ↓ 50 Changed 7 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 7 years ago by dkrenn

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 7 years ago by git

• Commit changed from 8241fa60528b8c73f69ca6e0fa8d652ddb815f25 to a69e50e7f56a513ecec65635ff414d635adbb86d

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

 ​a69e50e fixed BKZ link

### comment:52 Changed 7 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 7 years ago by dkrenn

• Status changed from needs_review to needs_work

### comment:54 Changed 7 years ago by git

• Commit changed from a69e50e7f56a513ecec65635ff414d635adbb86d to 03ebecd8beb3486446bf13ff63b4d69fd72ca98d

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

 ​03ebecd fixed documentation

### comment:55 Changed 7 years ago by git

• Commit changed from 03ebecd8beb3486446bf13ff63b4d69fd72ca98d to ce5faa250fe5beacb9eb79b7e4b7a766ed5abff6

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

 ​ce5faa2 more doc cleanup

### comment:56 Changed 7 years ago by malb

• Status changed from needs_work to needs_review

I think it got them all now.

### comment:57 Changed 7 years ago by dkrenn

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

### comment:58 Changed 7 years ago by dkrenn

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

### comment:59 Changed 7 years ago by malb

Whooohoo! Thank you so much!

### comment:60 Changed 7 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 7 years ago by git

• Commit changed from ce5faa250fe5beacb9eb79b7e4b7a766ed5abff6 to 95c1dd92891fb2405cb1f8e0384cef0305a2b9e1

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

 ​95c1dd9 mark long doctest as #long and reduce lattice dimension in other

### comment:62 Changed 7 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:  ​95c1dd9 mark long doctest as #long and reduce lattice dimension in other Last edited 7 years ago by malb (previous) (diff) ### comment:63 Changed 7 years ago by vbraun Latest beta = 6.3.beta1 ### comment:64 Changed 7 years ago by git • Commit changed from 95c1dd92891fb2405cb1f8e0384cef0305a2b9e1 to 4f6b44e9a1e3530409d4e9317e852a024093ee36 Branch pushed to git repo; I updated commit sha1. New commits:  ​30a99bf Merge branch 'develop' of trac.sagemath.org:sage into integer_lattices ​4f6b44e fixed doctest failures with latest Sage beta ### comment:65 Changed 7 years ago by malb Doctests fixed ... sorry, I missed beta1 somehow before. Last edited 7 years ago by malb (previous) (diff) ### comment:66 Changed 7 years ago by malb • Status changed from needs_work to needs_review ### comment:67 Changed 7 years ago by dkrenn • Status changed from needs_review to positive_review Reviewed changes.....positive. ### comment:68 follow-up: ↓ 70 Changed 7 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 7 years ago by dkrenn • Status changed from positive_review to needs_work ### comment:70 in reply to: ↑ 68 Changed 7 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 7 years ago by dkrenn • Work issues set to python3 ### comment:72 Changed 7 years ago by git • Commit changed from 4f6b44e9a1e3530409d4e9317e852a024093ee36 to 2317917181aa1721c02d24b8b6c0df906cb0adae Branch pushed to git repo; I updated commit sha1. New commits:  ​f07b046 Documentation cleanup and python 3. ​2317917 Some more documentation tweaks and added free_module_integer.py to doctree. ### comment:73 Changed 7 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:  ​8271e3c Added fplll to doc and changed utf to latex. ### comment:74 Changed 7 years ago by malb • Status changed from needs_review to positive_review looks okay, thanks. ### comment:75 Changed 7 years ago by vbraun • Status changed from positive_review to needs_work Conflicts with #16216 ### comment:76 Changed 7 years ago by git • Commit changed from 8271e3c0b885b0c1ca70e40538053ddf0dec7165 to 1eb090aa279265fefc535b73e002be07b816eb55 Branch pushed to git repo; I updated commit sha1. New commits:  ​f623de2 generated changes from "== None" to "is None" ​6a2e806 manual fixup of the generated changes ​f87a26f Merge branch 'develop' into u/wluebbe/ticket/16216b ​564c73c trac #16216: undo a mistake from the last merge ​67546ca merging #16216 ​1eb090a fixed doctest failures ### comment:77 Changed 7 years ago by malb • Status changed from needs_work to needs_review merged ### comment:78 Changed 7 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 7 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 7 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:

 ​4f6b44e fixed doctest failures with latest Sage beta ​f07b046 Documentation cleanup and python 3. ​2317917 Some more documentation tweaks and added free_module_integer.py to doctree. ​8271e3c Added fplll to doc and changed utf to latex. ​f623de2 generated changes from "== None" to "is None" ​6a2e806 manual fixup of the generated changes ​f87a26f Merge branch 'develop' into u/wluebbe/ticket/16216b ​564c73c trac #16216: undo a mistake from the last merge ​67546ca merging #16216 ​1eb090a fixed doctest failures

### comment:81 Changed 7 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 7 years ago by git

• Commit changed from 1eb090aa279265fefc535b73e002be07b816eb55 to 6957074e911206b46fbfa7cb64bddc32d72d7f6c

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

 ​6957074 fixed make doc-pdf

### comment:83 Changed 7 years ago by malb

• Status changed from new to needs_review

should be fixed now.

### comment:84 Changed 7 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 7 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 7 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 7 years ago by vbraun

• Branch changed from public/ticket/15976-latex to 6957074e911206b46fbfa7cb64bddc32d72d7f6c
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:88 Changed 11 months ago by dimpase

• Commit 6957074e911206b46fbfa7cb64bddc32d72d7f6c deleted

there is a strange rounding going on in

hv = [QQ(round(elmt, 6)) for elmt in hv]


Can anyone explain it? A careless change there initiated #29866, but still why 6, and not 42 - or better, something input-dependent?

### comment:89 follow-up: ↓ 90 Changed 11 months ago by malb

This is in diamond_cut in diamond_cutting.py, right? Maybe the underlying software uses single precision floats and this is meant to approximate that?

### comment:90 in reply to: ↑ 89 Changed 11 months ago by dimpase

This is in diamond_cut in diamond_cutting.py, right?

yes

Maybe the underlying software uses single precision floats and this is meant to approximate that?

No, since ages (libppl interface was added in 2011 or 2012, I gather - although it could have taken more time for it to become default) Polyhedron() uses ppl as backend, if given rational data, so it's exact. I thought that line does some clever rounding to speed things up, but still I can't imagine a maths statement which could make it rigorous.

Should we just drop the rounding?

### comment:91 Changed 11 months ago by dimpase

It's actually quite strange - you first convert your data to float(), and then build a polyhedron with coodinates obtained by rounding these floats and converting them into QQ.

It's a miracle to me that it (mostly) works.

Last edited 11 months ago by dimpase (previous) (diff)
Note: See TracTickets for help on using tickets.