Opened 5 years ago
Last modified 5 years ago
#21221 closed enhancement
update fplll to version 5.x — at Version 45
Reported by:  malb  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  packages: standard  Keywords:  
Cc:  tmonteil, jpflori, cpernet, jdemeyer  Merged in:  
Authors:  Martin Albrecht  Reviewers:  JeanPierre Flori, Thierry Monteil 
Report Upstream:  N/A  Work issues:  
Branch:  public/fplll5 (Commits, GitHub, GitLab)  Commit:  d194317e800984cdda95a99d4b33d43c88496410 
Dependencies:  #17635  Stopgaps: 
Description (last modified by )
Once fplll 5.0.0 is out we should upgrade:
 upgrade the SPKG
 add fpylll
 drop the current custom fplll interface
See https://groups.google.com/forum/#!topic/sagedevel/v_g81diO2pU for discussion
SPKGS
Change History (45)
comment:1 Changed 5 years ago by
 Cc tmonteil added
comment:2 Changed 5 years ago by
 Cc jpflori added
comment:3 Changed 5 years ago by
 Branch set to u/malb/t21221fplll5
 Commit set to 7b0a9f1d0b0870c6e855d2109264a8b7e90e1baf
comment:4 Changed 5 years ago by
 Description modified (diff)
comment:5 Changed 5 years ago by
 Commit changed from 7b0a9f1d0b0870c6e855d2109264a8b7e90e1baf to d3df34187889563414c98d405681c51ca6cd1035
comment:6 Changed 5 years ago by
Everything should be in place now. Waiting for https://github.com/fplll/fplll/pull/189 being merged to cut a new release. Then this ticket should be good to go.
comment:7 Changed 5 years ago by
 Commit changed from d3df34187889563414c98d405681c51ca6cd1035 to 7bd03e0a1d843df29f1c71654a3bd1a39410921e
Branch pushed to git repo; I updated commit sha1. New commits:
7bd03e0  fplll 5.0.2

comment:8 Changed 5 years ago by
 Description modified (diff)
 Status changed from new to needs_review
Should be good to go now.
comment:9 Changed 5 years ago by
Changes look good to me.
But fplll
fails to build on a linux/POWER7:
[fplll5.0.2] In file included from bkz_param.cpp:4:0: [fplll5.0.2] io/json.hpp: In constructor 'nlohmann::basic_json<ObjectType, Arra yType, StringType, BooleanType, NumberIntegerType, NumberUnsignedType, NumberFlo atType, AllocatorType>::basic_json() [with ObjectType = std::map; ArrayType = st d::vector; StringType = std::basic_string<char>; BooleanType = bool; NumberInteg erType = long int; NumberUnsignedType = long unsigned int; NumberFloatType = dou ble; AllocatorType = std::allocator]': [fplll5.0.2] io/json.hpp:1062:5: error: conversion from 'nlohmann::basic_json<> ::value_t' to nonscalar type 'nlohmann::basic_json<>::type_data_t' requested [fplll5.0.2] basic_json() = default; [fplll5.0.2] ^ [fplll5.0.2] bkz_param.cpp: In function 'std::vector<fplll::Strategy> fplll::lo ad_strategies_json(const string&)': [fplll5.0.2] bkz_param.cpp:79:8: note: synthesized method 'nlohmann::basic_json <ObjectType, ArrayType, StringType, BooleanType, NumberIntegerType, NumberUnsign edType, NumberFloatType, AllocatorType>::basic_json() [with ObjectType = std::ma p; ArrayType = std::vector; StringType = std::basic_string<char>; BooleanType = bool; NumberIntegerType = long int; NumberUnsignedType = long unsigned int; Numb erFloatType = double; AllocatorType = std::allocator]' first required here [fplll5.0.2] json js;
comment:10 Changed 5 years ago by
comment:11 Changed 5 years ago by
 Milestone set to sage7.4
 Status changed from needs_review to needs_work
I'm indeed using GCC 4.8, but as reported there it also make clang choke and a more recent version of json probably makes the problem disappear as the involved types have been suppressed/modified.
comment:12 Changed 5 years ago by
Thanks for tracking it down. Can you try with the new json.hpp
from https://github.com/nlohmann/json/blob/develop/src/json.hpp so check if it fixes your problem? I'd then update on my end.
Just dump json.hpp
in fplll/fplll/io
.
comment:13 Changed 5 years ago by
With the latest json.hpp
it just errors out without trying saying that the compiler (GCC 4.8) is unsupported. Nice.
comment:14 Changed 5 years ago by
FYI, forcing json.hpp
to give GCC 4.8.3 a try, it compiles seemingly fine.
comment:15 Changed 5 years ago by
Hi, so to clarify: if we update json.hpp
and drop its GCC 4.8 check then it seems to compile on your linux/POWER7 box?
comment:16 Changed 5 years ago by
Yes exactly.
comment:17 Changed 5 years ago by
Just note it does not check for 4.8 but for >= 4.9.
comment:18 Changed 5 years ago by
 Commit changed from 7bd03e0a1d843df29f1c71654a3bd1a39410921e to 83a78f0ea53991c5ada939e50a95b0530d4bc8d4
Branch pushed to git repo; I updated commit sha1. New commits:
83a78f0  fpylll depends on sagelib

comment:19 Changed 5 years ago by
 Commit changed from 83a78f0ea53991c5ada939e50a95b0530d4bc8d4 to f986fe12472ccd88c79a7691cf2235fe4ca2bb0b
Branch pushed to git repo; I updated commit sha1. New commits:
f986fe1  update to new fplll/fpylll upstream releases

comment:20 Changed 5 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
comment:21 Changed 5 years ago by
Updated to new upstream versions, now supporting GCC 4.8. Thanks.
comment:22 Changed 5 years ago by
 Description modified (diff)
 Reviewers set to JeanPierre Flori
(I fixed the links in the ticket description.)
It seems the new Linbox from #17635 (closed) fails to build on top of this:
[linbox1.4.2] #include <fplll/dpe.h>
comment:24 Changed 5 years ago by
At the moment we can just add a Linbox patch here to include from the nr
subdir.
comment:25 Changed 5 years ago by
Unfortunately, that's not enough:
[linbox1.4.2] ../../linbox/algorithms/lattice.inl: In function 'void LinBox::ll lReduceInBase(LinBox::BlasMatrix<_Field>&, LinBox::BlasMatrix<_Field>&, const Li nBox::latticeMethod::latticeFPLLL&)': [linbox1.4.2] ../../linbox/algorithms/lattice.inl:342:35: error: 'class fplll:: ZZ_mat<__mpz_struct [1]>' has no member named 'Set' [linbox1.4.2] B.Set((int)i,(int)j,x); [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:349:5: error: 'proved' is not a member of 'fplll' [linbox1.4.2] fplll::proved<ZT,double> lllMethod(&B,meth.getPrecision(), [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:349:21: error: expected prima ryexpression before ',' token [linbox1.4.2] fplll::proved<ZT,double> lllMethod(&B,meth.getPrecision(), [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:349:22: error: expected prima ryexpression before 'double' [linbox1.4.2] fplll::proved<ZT,double> lllMethod(&B,meth.getPrecision(), [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:349:22: error: expected ';' b efore 'double' [linbox1.4.2] ../../linbox/algorithms/lattice.inl:351:5: error: 'lllMethod' was not declared in this scope [linbox1.4.2] lllMethod.LLL(); [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:356:5: error: 'wrapper' is not a member of 'fplll' ... [linbox1.4.2] ../../linbox/algorithms/lattice.inl:351:5: error: 'lllMethod' was not declared in this scope [linbox1.4.2] lllMethod.LLL(); [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:356:5: error: 'wrapper' is not a member of 'fplll' [linbox1.4.2] fplll::wrapper lllMethod(&B,meth.getPrecision(), [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:356:20: error: expected ';' before 'lllMethod' [linbox1.4.2] fplll::wrapper lllMethod(&B,meth.getPrecision(), [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:358:5: error: 'lllMethod' was not declared in this scope [linbox1.4.2] lllMethod.LLL(); [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:363:5: error: 'heuristic' is not a member of 'fplll' [linbox1.4.2] fplll::heuristic<ZT,double> lllMethod(&B,meth.getPrecision(), [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:363:24: error: expected primaryexpression before ',' token [linbox1.4.2] fplll::heuristic<ZT,double> lllMethod(&B,meth.getPrecision(), [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:363:25: error: expected primaryexpression before 'double' [linbox1.4.2] fplll::heuristic<ZT,double> lllMethod(&B,meth.getPrecision(), [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:363:25: error: expected ';' before 'double' [linbox1.4.2] ../../linbox/algorithms/lattice.inl:366:5: error: 'lllMethod' was not declared in this scope [linbox1.4.2] lllMethod.LLL(); [linbox1.4.2] ^ [linbox1.4.2] ../../linbox/algorithms/lattice.inl:376:23: error: 'class fplll::ZZ_mat<__mpz_struct [1]>' has no member named 'Get' [linbox1.4.2] H.setEntry(i,j, B.Get(i,j) );
comment:26 followup: ↓ 27 Changed 5 years ago by
If fixing this really requires a lot of work in Linbox, we could just disable fplll in Linbox waiting for a Linbox fix... if that's an option.
comment:27 in reply to: ↑ 26 Changed 5 years ago by
Replying to jpflori:
we could just disable fplll in Linbox waiting for a Linbox fix... if that's an option.
This sounds like the most reasonable choice. I don't think any linbox dependency on fplll is actually exposed to sage at the moment. The hook was kept for the future.
comment:28 Changed 5 years ago by
 Branch changed from u/malb/t21221fplll5 to public/fplll5
 Commit changed from f986fe12472ccd88c79a7691cf2235fe4ca2bb0b to cc8a95f7624eac7c17ac123aebb4ac64e4ef2ab2
 Dependencies set to #17635
 Status changed from needs_review to positive_review
With this strategy everything looks ok. Let the patchbots (or Volker?) do their testing jobs.
Last 10 new commits:
98cc68c  Only try relevant extension for OS when loading libSingular.

399f051  Add cddlib as a dependency and make gfanlib building explicit

797c539  Improve the cleaning

75e383a  use Singular.pc almost everywhere

a0f55ea  Singular.pc is now used everywhere. plural.pyx doesn't need givaro or readline or m anymore.

55447da  Do not build (a second time) libfactory when building Singular.

e5c10ae  Cleaner removal of files.

29077a7  Use wildcards for singular and letterplace in module_list.py.

f366df4  Merge branch 'singular4' into fplll5

cc8a95f  Let Linbox build by disabling its fplll linking.

comment:29 Changed 5 years ago by
Oops, it seems I pushed a wrong branch. I'll do a force push in a few seconds, sorry about that...
comment:30 Changed 5 years ago by
 Commit changed from cc8a95f7624eac7c17ac123aebb4ac64e4ef2ab2 to 3f2d20c8c232770e63442b38e818e7b50133bd85
 Status changed from positive_review to needs_review
comment:31 Changed 5 years ago by
Sorry for the mess, here's a clean branch where I only merged trac/develop
and disabled fplll linking wihtin linbox.
comment:32 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:33 Changed 5 years ago by
 Reviewers changed from JeanPierre Flori to JeanPierre Flori, Thierry Monteil
 Status changed from positive_review to needs_info
I started the tests before the last changes of JeanPierre, but i got doctests failure on 32bit system, which i guess will still be here after applying the last two commits too.
sage t long warnlong 124.3 src/sage/modules/free_module_integer.py ********************************************************************** File "src/sage/modules/free_module_integer.py", line 78, in sage.modules.free_module_integer.IntegerLattice Failed example: IntegerLattice(A) Expected: Free module of degree 10 and rank 10 over Integer Ring User basis matrix: [ 0 1 2 0 1 2 1 0 1 1] [ 0 1 0 3 0 0 0 0 3 1] [ 1 1 1 0 3 0 0 1 2 2] [1 2 1 1 2 2 1 1 0 1] [ 1 0 4 2 0 1 2 1 0 0] [ 2 3 0 1 1 0 2 3 0 0] [2 3 2 0 0 1 1 1 3 2] [3 0 1 0 2 1 2 1 1 1] [ 1 4 1 1 2 2 1 0 3 1] [1 1 0 3 1 2 2 3 1 0] Got: Free module of degree 10 and rank 10 over Integer Ring User basis matrix: [ 0 1 2 0 1 2 1 0 1 1] [ 1 2 1 1 2 2 1 1 0 1] [ 0 2 2 2 1 2 1 0 1 2] [ 0 1 0 3 0 0 0 0 3 1] [ 1 0 4 2 0 1 2 1 0 0] [ 2 3 0 1 1 0 2 3 0 0] [3 2 3 2 2 1 0 0 0 2] [3 0 1 0 2 1 2 1 1 1] [ 1 4 1 1 2 2 1 0 3 1] [1 1 0 3 1 2 2 3 1 0] ********************************************************************** File "src/sage/modules/free_module_integer.py", line 95, in sage.modules.free_module_integer.IntegerLattice Failed example: sage.crypto.gen_lattice(type='modular', m=10, seed=42, dual=True, lattice=True) Expected: Free module of degree 10 and rank 10 over Integer Ring User basis matrix: [ 0 1 2 0 1 2 1 0 1 1] [ 0 1 0 3 0 0 0 0 3 1] [ 1 1 1 0 3 0 0 1 2 2] [1 2 1 1 2 2 1 1 0 1] [ 1 0 4 2 0 1 2 1 0 0] [ 2 3 0 1 1 0 2 3 0 0] [2 3 2 0 0 1 1 1 3 2] [3 0 1 0 2 1 2 1 1 1] [ 1 4 1 1 2 2 1 0 3 1] [1 1 0 3 1 2 2 3 1 0] Got: Free module of degree 10 and rank 10 over Integer Ring User basis matrix: [ 0 1 2 0 1 2 1 0 1 1] [ 1 2 1 1 2 2 1 1 0 1] [ 0 2 2 2 1 2 1 0 1 2] [ 0 1 0 3 0 0 0 0 3 1] [ 1 0 4 2 0 1 2 1 0 0] [ 2 3 0 1 1 0 2 3 0 0] [3 2 3 2 2 1 0 0 0 2] [3 0 1 0 2 1 2 1 1 1] [ 1 4 1 1 2 2 1 0 3 1] [1 1 0 3 1 2 2 3 1 0] ********************************************************************** File "src/sage/modules/free_module_integer.py", line 203, in sage.modules.free_module_integer.FreeModule_submodule_with_basis_integer Failed example: L = IntegerLattice(sage.crypto.gen_lattice(type='modular', m=10, seed=42, dual=True)); L Expected: Free module of degree 10 and rank 10 over Integer Ring User basis matrix: [ 0 1 2 0 1 2 1 0 1 1] [ 0 1 0 3 0 0 0 0 3 1] [ 1 1 1 0 3 0 0 1 2 2] [1 2 1 1 2 2 1 1 0 1] [ 1 0 4 2 0 1 2 1 0 0] [ 2 3 0 1 1 0 2 3 0 0] [2 3 2 0 0 1 1 1 3 2] [3 0 1 0 2 1 2 1 1 1] [ 1 4 1 1 2 2 1 0 3 1] [1 1 0 3 1 2 2 3 1 0] Got: Free module of degree 10 and rank 10 over Integer Ring User basis matrix: [ 0 1 2 0 1 2 1 0 1 1] [ 1 2 1 1 2 2 1 1 0 1] [ 0 2 2 2 1 2 1 0 1 2] [ 0 1 0 3 0 0 0 0 3 1] [ 1 0 4 2 0 1 2 1 0 0] [ 2 3 0 1 1 0 2 3 0 0] [3 2 3 2 2 1 0 0 0 2] [3 0 1 0 2 1 2 1 1 1] [ 1 4 1 1 2 2 1 0 3 1] [1 1 0 3 1 2 2 3 1 0] ********************************************************************** File "src/sage/modules/free_module_integer.py", line 513, in sage.modules.free_module_integer.FreeModule_submodule_with_basis_integer.HKZ Failed example: L.reduced_basis[0] Expected: (1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0) Got: (1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 2, 0, 0, 1, 1) **********************************************************************
Concerning src/sage/matrix/matrix_integer_dense.pyx
i have a Timed out (and interrupt failed)
without further explanations, i will run the tests by hand one by one.
I put it in "need info" not "need work" because i have to test the very last commit on a fresh install to confirm the issue, this might take some time since the VM is a bit slow.
comment:34 Changed 5 years ago by
Looks like you're getting a different LLL reduced basis. Mhh, no idea why 32 bit systems might be different, we might have to wait to see what the patchbots report.
comment:35 followup: ↓ 36 Changed 5 years ago by
Will the patchbots do anything if this is not positive_review?
comment:36 in reply to: ↑ 35 Changed 5 years ago by
 Cc jdemeyer added
 Status changed from needs_info to needs_review
On my fresh retry, i got the same failures (but no problem for src/sage/matrix/matrix_integer_dense.pyx
which were probably due to some optional pkgs).
Replying to malb:
Looks like you're getting a different LLL reduced basis. Mhh, no idea why 32 bit systems might be different, we might have to wait to see what the patchbots report.
I do not know either, especially since LLL is deterministic, so perhaps is there some nonconstantlength variable in the floatingpoint part of the code ?
Usually, the arch is sufficient to separate such behaviours (e.g. on my 64bit daily laptop, the tests are OK), and we can make specific tests for them.
But before settling down a #32bit
doctest with those values, we should check that the bases are indeed LLLreduced (it could be an explicit part of the test by the way).
For double checking, note that apart from my patchbot (actually a qemulated Pentium III), arando is the other running 32bit arch, which is run by Jeroen, so we could ask him to tell that patchbot to focus on that ticket.
Replying to jpflori:
Will the patchbots do anything if this is not positive_review?
Yes, since the patchbots are more a tool to help reviewing than to help releasing (for which the buildbot helps). Actually, being in needs_review
gives you more chance to get some patchbots looking at your code (so let me put the ticket to needs_review
, just to motivate some of those): https://github.com/sagemath/sagepatchbot/blob/master/sage_patchbot/patchbot.py#L420 Note that you can force the retest with the ?kick
trick : https://patchbot.sagemath.org/ticket/21221/?kick (this is why there is retry: True
now, i clicked on that link yesterday).
comment:37 Changed 5 years ago by
I can reproduce it in a 32bit virtual machine:
sage: from sage.modules.free_module_integer import IntegerLattice sage: A = sage.crypto.gen_lattice(type='modular', m=10, seed=42, dual=True) sage: copy(A).LLL(algorithm="fpLLL:proved", fp="rr")[3] (1, 2, 1, 1, 2, 2, 1, 1, 0, 1) sage: copy(A).LLL(algorithm="fpLLL:proved", fp="fp")[3] (0, 1, 0, 3, 0, 0, 0, 0, 3, 1)
On a 64bit system:
sage: copy(A).LLL(algorithm="fpLLL:proved", fp="fp")[3] (1, 2, 1, 1, 2, 2, 1, 1, 0, 1) sage: copy(A).LLL(algorithm="fpLLL:proved", fp="rr")[3] (1, 2, 1, 1, 2, 2, 1, 1, 0, 1)
Note that the last outputs differ. In either case the output is LLL reduced (I'm not in favour of adding that test to the doctest though, since LLLreducedness is not the main point there, thus it would be a bit distracting).
A cheap workaround is to simply pick a different seed for the doctest.
comment:38 Changed 5 years ago by
 Commit changed from 3f2d20c8c232770e63442b38e818e7b50133bd85 to c4fa878505265cd2a45a58f182b99e41d0530c64
Branch pushed to git repo; I updated commit sha1. New commits:
c4fa878  unify 32bit and 64bit doctest outputs

comment:39 Changed 5 years ago by
This seems to have done the trick.
comment:40 Changed 5 years ago by
Maybe we should still document that even with the same seed, the LLL reduction, although deterministic, might give different results on 32 and 64 platforms (different roundng for floats?) ?
comment:41 Changed 5 years ago by
 Commit changed from c4fa878505265cd2a45a58f182b99e41d0530c64 to 1a15357fb2e19e014bb313f514aad7528a4c89e3
Branch pushed to git repo; I updated commit sha1. New commits:
1a15357  add warning about different LLL answers

comment:42 Changed 5 years ago by
 Status changed from needs_review to positive_review
Good to go for me.
comment:43 Changed 5 years ago by
Waiting for Volker's run report. But in sageongentoo, I couldn't get the test suite for fpylll
to run successfully when it was built using sagelib
. I decided to hard disable it until I figure if it's broken on my side only or it is for everyone. Actually the fpylll
tarball that is linked in this ticket doesn't include the test suite or does it?
comment:44 Changed 5 years ago by
 Commit changed from 1a15357fb2e19e014bb313f514aad7528a4c89e3 to d194317e800984cdda95a99d4b33d43c88496410
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
d194317  fpylll 0.2.2dev

comment:45 Changed 5 years ago by
 Description modified (diff)
New commits:
fplll 5.0.1 & drop sage.libs.fplll
add fpylll
A.LLL() and A.BKZ() using fpylll