IntegerLattice class - Githubissues

malb commented 10 years ago

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

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.

Component: linear algebra

Author: Martin Albrecht

Branch: 6957074

Reviewer: Daniel Krenn, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/15976

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from eb352db to 44d20d5

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 44d20d5 to a561d36

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

dkrenn commented 10 years ago

comment:38

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

142e8da Merge branch 'develop' into integer_lattices

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from a561d36 to 142e8da

malb commented 10 years ago

comment:40

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 142e8da to 301e4e4

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 301e4e4 to d6151ee

malb commented 10 years ago

comment:43

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.

dkrenn commented 10 years ago

comment:44

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from d6151ee to c44aac9

malb commented 10 years ago

comment:46

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!

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

8241fa6 corrected trailing whitespaces

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from c44aac9 to 8241fa6

dkrenn commented 10 years ago

comment:48

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

malb commented 10 years ago

comment:49

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.

dkrenn commented 10 years ago

comment:50

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

a69e50e fixed BKZ link

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 8241fa6 to a69e50e

dkrenn commented 10 years ago

comment:52

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)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

03ebecd fixed documentation

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from a69e50e to 03ebecd

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

ce5faa2 more doc cleanup

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 03ebecd to ce5faa2

malb commented 10 years ago

comment:56

I think it got them all now.

dkrenn commented 10 years ago

comment:57

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

dkrenn commented 10 years ago

Reviewer: Daniel Krenn

malb commented 10 years ago

comment:59

Whooohoo! Thank you so much!

vbraun commented 10 years ago

comment:60

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?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from ce5faa2 to 95c1dd9

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

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

malb commented 10 years ago

comment:62

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

vbraun commented 10 years ago

comment:63

Latest beta = 6.3.beta1

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 95c1dd9 to 4f6b44e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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`

malb commented 10 years ago

comment:65

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

dkrenn commented 10 years ago

comment:67

Reviewed changes.....positive.

tscrim commented 10 years ago

comment:68

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

malb commented 10 years ago

comment:70

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.

dkrenn commented 10 years ago

Work Issues: python3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 4f6b44e to 2317917

tscrim commented 10 years ago

comment:73

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.

tscrim commented 10 years ago

Changed commit from 2317917 to 8271e3c

tscrim commented 10 years ago

Changed branch from public/ticket/15976 to public/ticket/15976-latex

tscrim commented 10 years ago

Changed reviewer from Daniel Krenn to Daniel Krenn, Travis Scrimshaw

sagemath / sage

IntegerLattice class #15976