Opened 5 years ago
Closed 5 years ago
#15976 closed enhancement (fixed)
IntegerLattice class
Reported by:  malb  Owned by:  

Priority:  major  Milestone:  sage6.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 ZZ^{n}.
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
 Branch set to u/malb/15976_integer_lattice
 Commit set to f9b4bdd650679c3569cbf01bf1c3cbfc8b66474e
comment:2 Changed 5 years ago by
 Commit changed from f9b4bdd650679c3569cbf01bf1c3cbfc8b66474e to 9a76b85a9836117c3efb97e474b292481f0f67ec
Branch pushed to git repo; I updated commit sha1. New commits:
9a76b85  documentation changes

comment:3 Changed 5 years ago by
 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 5 years ago by
 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 5 years ago by
 Status changed from new to needs_review
comment:6 followup: ↓ 7 Changed 5 years ago by
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 subcategory 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 finealmost. 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'twell, 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, nonintegral 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): ...
comment:7 in reply to: ↑ 6 ; followup: ↓ 8 Changed 5 years ago by
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 fromElement
(or ratherModuleElement
, 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 attributeIntegerLattice.Element
.Next, if you decide to inherit from
Parent
and assign.Element
, you should doself._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'twell, 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 Z^{n}. 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 Z^{n}? 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 leastCachedRepresentation
for lattices? It seems strange to me to have a functionLattice
that does nothing more than hand the arguments to theIntegerLattice
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 ; followup: ↓ 9 Changed 5 years ago by
Replying to malb:
However, the next complaint is that elements created by
some_element()
do not live in the lattice but in Z^{n}. 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 Z^{n}?
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 nonidentical lattices that may still be equal. Only UniqueRepresentation
would imply a "comparison by identity".
comment:9 in reply to: ↑ 8 Changed 5 years ago by
Replying to SimonKing:
Your situation could be similar: You have a lattice
L
inRR^n
, and the parent of the elements ofL
wouldn't beL
butRR^n
(but please notZZ^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
 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 followup: ↓ 13 Changed 5 years ago by
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 lifetime of an object.
comment:12 Changed 5 years ago by
 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 5 years ago by
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 lifetime of an object.
OK, it sounds like caching would be bad in such situation.
comment:14 Changed 5 years ago by
Okay, excellent. So  as far as I am concerned  our work here is done :)
comment:15 followup: ↓ 17 Changed 5 years ago by
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
 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 5 years ago by
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 onboard from the 2012 GSoC project. It seemed like the only nontrivial contribution and I didn't want to delete it. I never touched it. If noone 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 RR^{n}) 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 5 years ago by
Oh, if it's not in the global namespace, then it's fine. Otherwise, what about RealLattice
?
comment:19 Changed 5 years ago by
 Branch changed from u/malb/15976_integer_lattice to public/ticket/15976
 Commit changed from 43d76e8bc29c84c72ab9ebbd1bd65a01d3fccb52 to fe8836f8d59facf7e8bde6542c68a6c5772e5fc3
*ignore this one*
comment:20 Changed 5 years ago by
 Commit changed from fe8836f8d59facf7e8bde6542c68a6c5772e5fc3 to d5c404c5d3a135ec9f078d0ea3c7cf23ddbf20a5
comment:21 Changed 5 years ago by
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
 Commit changed from d5c404c5d3a135ec9f078d0ea3c7cf23ddbf20a5 to f5e8e1661c9313bb6167d8da4b646df10ce7b422
Branch pushed to git repo; I updated commit sha1. New commits:
f5e8e16  Lattice > RealLattice

comment:23 followup: ↓ 24 Changed 5 years ago by
I renamed Lattice
to RealLattice
comment:24 in reply to: ↑ 23 Changed 5 years ago by
Replying to malb:
I renamed
Lattice
toRealLattice
bad choice, IMHO. People will want to have lattices in things like C^{n }
comment:25 Changed 5 years ago by
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 R^{n} (at least in my neck of the woods).
comment:26 Changed 5 years ago by
How about VectorSpaceLattice
? (well, not all fields might be supported, but still).
comment:27 followup: ↓ 29 Changed 5 years ago by
Wouldn't people confuse that with vector lattices? Or is that not a common notion? cf. http://www.stat.yale.edu/~pollard/Books/Asymptopia/oldVectorlattice.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
 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 5 years ago by
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/oldVectorlattice.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
now that's just mean … for now VectorSpaceLattice
seems to be a winner.
comment:31 Changed 5 years ago by
 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 5 years ago by
 Commit changed from f1686df7df460ed0f559d2747d84df26e992e016 to 34734a15420206c4bfb64fb85f619bed3d3177a4
comment:33 Changed 5 years ago by
The patch is a lot less invasive now, anyone up for reviewing it?
comment:34 Changed 5 years ago by
 Commit changed from 34734a15420206c4bfb64fb85f619bed3d3177a4 to eb352dbefccf698b3fd26e25b0c532ad5efc1e5f
comment:35 Changed 5 years ago by
 Commit changed from eb352dbefccf698b3fd26e25b0c532ad5efc1e5f to 44d20d522b5a1db31ca1cfb1c5de4effe6558cb8
Branch pushed to git repo; I updated commit sha1. New commits:
44d20d5  fixed incomplete merge

comment:36 Changed 5 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:37 Changed 5 years ago by
 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  whitespacecorrections; longline 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 followup: ↓ 40 Changed 5 years ago by
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: OUTPUTblocks 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 inputdescriptions (in INPUTblock), sometimes not. This should be done in the same way everywhere.
 fplll.pyx: def BKZ: In the INPUTblock 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
or0
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 INPUTblock end with a fullstop; most of the times not.
 free_module_integer.py: Some missing OUTPUTblocks

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
 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 ; followup: ↓ 44 Changed 5 years ago by
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 UTF8 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: OUTPUTblocks 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 inputdescriptions (in INPUTblock), sometimes not. This should be done in the same way everywhere.
I should have fixed all of those.
 fplll.pyx: def BKZ: In the INPUTblock 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
or0
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 INPUTblock end with a fullstop; most of the times not.
I tried to unify those.
 free_module_integer.py: Some missing OUTPUTblocks
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
 Commit changed from 142e8da1f1b387a5a2ea2d278f29e91d97930aac to 301e4e43b3523d46ae8042845a248daa47953cd8
comment:42 Changed 5 years ago by
 Commit changed from 301e4e43b3523d46ae8042845a248daa47953cd8 to d6151ee73c58fbc7da45ed151f47a84dc4cafe5b
comment:43 Changed 5 years ago by
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 ; followup: ↓ 46 Changed 5 years ago by
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
 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 5 years ago by
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
 Commit changed from c44aac98058522aac15042e1d986422f5d818ae0 to 8241fa60528b8c73f69ca6e0fa8d652ddb815f25
Branch pushed to git repo; I updated commit sha1. New commits:
8241fa6  corrected trailing whitespaces

comment:48 Changed 5 years ago by
Thanks for your changes. Look good.
There is one problem: the documentation does not build:
[modules ] /local/data/krenn/sagedevelop/local/lib/python2.7/sitepackages/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/sagedevelop/local/lib/python2.7/sitepackages/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/sagedevelop/src/doc/common/builder.py", line 1477, in <module> getattr(get_builder(name), type)() File "/local/data/krenn/sagedevelop/src/doc/common/builder.py", line 276, in _wrapper getattr(get_builder(document), 'inventory')(*args, **kwds) File "/local/data/krenn/sagedevelop/src/doc/common/builder.py", line 487, in _wrapper x.get(99999) File "/local/data/krenn/sagedevelop/local/lib/python/multiprocessing/pool.py", line 554, in get raise self._value OSError: [modules ] /local/data/krenn/sagedevelop/local/lib/python2.7/sitepackages/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: *** [dochtml] Fehler 1
comment:49 followup: ↓ 50 Changed 5 years ago by
Thanks! I'm trying to fix it, but the error message doesn't seem very helpful:
OSError: [modules ] /local/data/krenn/sagedevelop/local/lib/python2.7/sitepackages/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
Replying to malb:
Thanks! I'm trying to fix it, but the error message doesn't seem very helpful:
OSError: [modules ] /local/data/krenn/sagedevelop/local/lib/python2.7/sitepackages/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 divideandconquercommentout procedure...
comment:51 Changed 5 years ago by
 Commit changed from 8241fa60528b8c73f69ca6e0fa8d652ddb815f25 to a69e50e7f56a513ecec65635ff414d635adbb86d
Branch pushed to git repo; I updated commit sha1. New commits:
a69e50e  fixed BKZ link

comment:52 Changed 5 years ago by
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
 Status changed from needs_review to needs_work
comment:54 Changed 5 years ago by
 Commit changed from a69e50e7f56a513ecec65635ff414d635adbb86d to 03ebecd8beb3486446bf13ff63b4d69fd72ca98d
Branch pushed to git repo; I updated commit sha1. New commits:
03ebecd  fixed documentation

comment:55 Changed 5 years ago by
 Commit changed from 03ebecd8beb3486446bf13ff63b4d69fd72ca98d to ce5faa250fe5beacb9eb79b7e4b7a766ed5abff6
Branch pushed to git repo; I updated commit sha1. New commits:
ce5faa2  more doc cleanup

comment:56 Changed 5 years ago by
 Status changed from needs_work to needs_review
I think it got them all now.
comment:57 Changed 5 years ago by
Everything looks good now. Doctests are still running...
comment:58 Changed 5 years ago by
 Reviewers set to Daniel Krenn
 Status changed from needs_review to positive_review
comment:59 Changed 5 years ago by
Whooohoo! Thank you so much!
comment:60 Changed 5 years ago by
 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
 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 5 years ago by
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: 20140510
New commits:
95c1dd9  mark long doctest as #long and reduce lattice dimension in other

comment:63 Changed 5 years ago by
Latest beta = 6.3.beta1
comment:64 Changed 5 years ago by
 Commit changed from 95c1dd92891fb2405cb1f8e0384cef0305a2b9e1 to 4f6b44e9a1e3530409d4e9317e852a024093ee36
comment:65 Changed 5 years ago by
Doctests fixed ... sorry, I missed beta1 somehow before.
comment:66 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:67 Changed 5 years ago by
 Status changed from needs_review to positive_review
Reviewed changes.....positive.
comment:68 followup: ↓ 70 Changed 5 years ago by
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 nonascii 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 wellformatted 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
 Status changed from positive_review to needs_work
comment:70 in reply to: ↑ 68 Changed 5 years ago by
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 nonascii characters where I think you should just use the latex equivalents.
I disagree, using UTF8 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 wellformatted 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 straightforward. 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
 Work issues set to python3
comment:72 Changed 5 years ago by
 Commit changed from 4f6b44e9a1e3530409d4e9317e852a024093ee36 to 2317917181aa1721c02d24b8b6c0df906cb0adae
comment:73 Changed 5 years ago by
 Branch changed from public/ticket/15976 to public/ticket/15976latex
 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 5 years ago by
 Status changed from needs_review to positive_review
looks okay, thanks.
comment:75 Changed 5 years ago by
 Status changed from positive_review to needs_work
Conflicts with #16216
comment:76 Changed 5 years ago by
 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:78 Changed 5 years ago by
 Branch changed from public/ticket/15976latex to 1eb090aa279265fefc535b73e002be07b816eb55
 Resolution set to fixed
 Status changed from needs_review to closed
comment:79 Changed 5 years ago by
 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 $(̣ δ, η)$LLLreduced ? ! Emergency stop.
I think there is a zerowidth 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
 Branch changed from 1eb090aa279265fefc535b73e002be07b816eb55 to public/ticket/15976latex
 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 5 years ago by
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
 Commit changed from 1eb090aa279265fefc535b73e002be07b816eb55 to 6957074e911206b46fbfa7cb64bddc32d72d7f6c
Branch pushed to git repo; I updated commit sha1. New commits:
6957074  fixed make docpdf

comment:84 Changed 5 years ago by
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
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
 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
 Branch changed from public/ticket/15976latex to 6957074e911206b46fbfa7cb64bddc32d72d7f6c
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
first draft of IntegerLattice class
modern interface to fpLLL