Re: [sage-devel] fplll 5.0 in sage
This is now https://trac.sagemath.org/ticket/21221 Cheers, Martin Jean-Pierre Flori writes: > Yes! > > Did you open a ticket for this? -- _pgp: https://keybase.io/martinralbrecht _www: https://martinralbrecht.wordpress.com _jab: martinralbre...@jabber.ccc.de _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] fplll 5.0 in sage
Yes! Did you open a ticket for this? -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] fplll 5.0 in sage
Sounds pretty great! > [X] Yes > [ ] No > [ ] Maybe Best, Johan -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
Re: [sage-devel] fplll 5.0 in sage
Hi, giving interfaces initially developped for Sage to upstream is the way to go. The benefits of free-software ecosystem should be two-ways, otherwise Sage is only predating other softwares. Moreover with such an approach, upstream will make it cover all features when they appear so that they are automatically exposed to Sage users, and they can ship Python bindings independently of Sage (which many mathematician consider as too big for their specific needs). In the concrete case of fpLLL, we already had the case where some developper reimplemented a feature of fpLLL just because it was not exposed by our partial (not up-to-date) interface, see https://trac.sagemath.org/ticket/15758 A common Python bindings is probably a better place to cut (for modularity) than between upstream binary and Sage Cython bindings (though i admint that in some specific cases, it may add a slowing Python layer). +1 for using fpylll and make it standard. Ciao, Thierry On Fri, Aug 05, 2016 at 12:32:53PM +0100, 'Martin R. Albrecht' via sage-devel wrote: > Hi Sage developers, > > *tl;dr* Fplll 5.0 is about to hit the streets. It’s a major improvement > over Fplll 4.* which we currently ship with Sage. To update we need to > change the user interface of the function `IntegerMatrix.BKZ`. I > suggest to drop Sage’s own interface to Fplll in favour of the official > Fpylll interface, which I propose to make a standard package. > > [ ] Yes > [ ] No > [ ] Maybe > > # Details # > > We are getting ready to release Fplll 5.0.0. Here are some highlights > from the changelog https://raw.githubusercontent.com/fplll/fplll/master/NEWS > > - fplll switched to more open development model on GitHub > with a bigger development community > > - public implementation of all techniques collectively known as BKZ 2.0. > BKZ in block size 80 is a reasonably easy computation now. > > - build system overhaul, automated tests, test coverage increase > > - Self-Dual BKZ and Slide reduction > > - faster, recursive enumeration implementation > > - Gaussian lattice sieving > > - optional support for doubledouble and quaddouble > > https://github.com/fplll/fplll > > If you care only about LLL then this release won’t change much for you, > because Sage doesn’t ship libqd. But if you care about stronger lattice > reduction this release makes a huge difference. > > # Sage Interface # > > (a) Sage’s public interface is through the functions `IntegerMatrix.LLL` and > `IntegerMatrix.BKZ` and a few functions on the integer lattice class. > > (b) These call some in `libs.fplll` > > The the interface for calling BKZ has changed and does not match Sage’s > interface (a). We could write a translation layer, but I’d prefer to > simply change it. Users will want to use the new interface. > > I also suggest to replace (b) completely with > > https://github.com/fplll/fpylll > > It’s a Cython interface to fplll + additional Python code which started > as a fork of Sage’s Cython interface. It’s much more flexible and > powerful than what Sage has to offer. For example, it (easily) allows to > implement BKZ and LLL variants in pure Python. Strong lattice reduction > is a major area of research for cryptographers at the moment and this > library aims to make experimentation for this easy. > > It is mainly written and maintained by me. Lattice-based cryptography > will be research area for the foreseeable future and this code is a key > component of this research for me, so I plan to maintain and improve it > over the next few years. I do commit to maintaining it in Sage, too. > > The code has tests which are run on every check in. > > Yes, No, Maybe? > > Cheers, > Martin > > PS: Here is some random benchmark: > > $ ./latticegen q 100 50 30 b > ~/test_lattice.txt > > new fplll > > $ time ./fplll -a bkz -s ../strategies/default.json -bkzautoabort -v -b 60 > ~/test_lattice.txt > /dev/null > Entering BKZ: > block size: 60, flags: 0x0021, max_loops: 0, max_time: 0.0, autoAbort: > (1., 5), > > End of BKZ loop0, time =12.832s, r_0 = 1.80e10, slope = -0.056809, > log2(nodes) = 28.142067 > End of BKZ loop1, time =25.072s, r_0 = 1.07e10, slope = -0.050003, > log2(nodes) = 29.120454 > End of BKZ loop2, time =36.836s, r_0 = 1.00e10, slope = -0.048468, > log2(nodes) = 29.623702 > End of BKZ loop3, time =48.944s, r_0 = 9.42e9, slope = -0.048443, > log2(nodes) = 29.991966 > End of BKZ loop4, time =58.176s, r_0 = 9.42e9, slope = -0.048230, > log2(nodes) = 30.207781 > End of BKZ loop5, time =67.904s, r_0 = 9.42e9, slope = -0.048134, > log2(nodes) = 30.414377 > End of BKZ loop6, time =78.040s, r_0 = 9.42e9, slope = -0.048500, > log2(nodes) = 30.611421 > End of BKZ loop7, time =87.780s, r_0 = 9.42e9, slope = -0.048197, > log2(nodes) = 30.784449 > End of BKZ loop8, time =96.468s, r_0 = 9.42e9, slope = -0.047948, > log2(nodes) = 30.910345 > End of BKZ loop
[sage-devel] fplll 5.0 in sage
Hi Sage developers, *tl;dr* Fplll 5.0 is about to hit the streets. It’s a major improvement over Fplll 4.* which we currently ship with Sage. To update we need to change the user interface of the function `IntegerMatrix.BKZ`. I suggest to drop Sage’s own interface to Fplll in favour of the official Fpylll interface, which I propose to make a standard package. [ ] Yes [ ] No [ ] Maybe # Details # We are getting ready to release Fplll 5.0.0. Here are some highlights from the changelog https://raw.githubusercontent.com/fplll/fplll/master/NEWS - fplll switched to more open development model on GitHub with a bigger development community - public implementation of all techniques collectively known as BKZ 2.0. BKZ in block size 80 is a reasonably easy computation now. - build system overhaul, automated tests, test coverage increase - Self-Dual BKZ and Slide reduction - faster, recursive enumeration implementation - Gaussian lattice sieving - optional support for doubledouble and quaddouble https://github.com/fplll/fplll If you care only about LLL then this release won’t change much for you, because Sage doesn’t ship libqd. But if you care about stronger lattice reduction this release makes a huge difference. # Sage Interface # (a) Sage’s public interface is through the functions `IntegerMatrix.LLL` and `IntegerMatrix.BKZ` and a few functions on the integer lattice class. (b) These call some in `libs.fplll` The the interface for calling BKZ has changed and does not match Sage’s interface (a). We could write a translation layer, but I’d prefer to simply change it. Users will want to use the new interface. I also suggest to replace (b) completely with https://github.com/fplll/fpylll It’s a Cython interface to fplll + additional Python code which started as a fork of Sage’s Cython interface. It’s much more flexible and powerful than what Sage has to offer. For example, it (easily) allows to implement BKZ and LLL variants in pure Python. Strong lattice reduction is a major area of research for cryptographers at the moment and this library aims to make experimentation for this easy. It is mainly written and maintained by me. Lattice-based cryptography will be research area for the foreseeable future and this code is a key component of this research for me, so I plan to maintain and improve it over the next few years. I do commit to maintaining it in Sage, too. The code has tests which are run on every check in. Yes, No, Maybe? Cheers, Martin PS: Here is some random benchmark: $ ./latticegen q 100 50 30 b > ~/test_lattice.txt new fplll $ time ./fplll -a bkz -s ../strategies/default.json -bkzautoabort -v -b 60 ~/test_lattice.txt > /dev/null Entering BKZ: block size: 60, flags: 0x0021, max_loops: 0, max_time: 0.0, autoAbort: (1., 5), End of BKZ loop0, time =12.832s, r_0 = 1.80e10, slope = -0.056809, log2(nodes) = 28.142067 End of BKZ loop1, time =25.072s, r_0 = 1.07e10, slope = -0.050003, log2(nodes) = 29.120454 End of BKZ loop2, time =36.836s, r_0 = 1.00e10, slope = -0.048468, log2(nodes) = 29.623702 End of BKZ loop3, time =48.944s, r_0 = 9.42e9, slope = -0.048443, log2(nodes) = 29.991966 End of BKZ loop4, time =58.176s, r_0 = 9.42e9, slope = -0.048230, log2(nodes) = 30.207781 End of BKZ loop5, time =67.904s, r_0 = 9.42e9, slope = -0.048134, log2(nodes) = 30.414377 End of BKZ loop6, time =78.040s, r_0 = 9.42e9, slope = -0.048500, log2(nodes) = 30.611421 End of BKZ loop7, time =87.780s, r_0 = 9.42e9, slope = -0.048197, log2(nodes) = 30.784449 End of BKZ loop8, time =96.468s, r_0 = 9.42e9, slope = -0.047948, log2(nodes) = 30.910345 End of BKZ loop9, time = 117.404s, r_0 = 9.42e9, slope = -0.048360, log2(nodes) = 31.053923 End of BKZ loop 10, time = 143.812s, r_0 = 9.42e9, slope = -0.048163, log2(nodes) = 31.180644 End of BKZ loop 11, time = 164.652s, r_0 = 9.42e9, slope = -0.047898, log2(nodes) = 31.286769 End of BKZ loop 12, time = 203.492s, r_0 = 9.20e9, slope = -0.048275, log2(nodes) = 31.392854 End of BKZ loop 13, time = 236.376s, r_0 = 9.20e9, slope = -0.047879, log2(nodes) = 31.501613 End of BKZ loop 14, time = 284.636s, r_0 = 9.20e9, slope = -0.048120, log2(nodes) = 31.608491 End of BKZ loop 15, time = 310.472s, r_0 = 9.20e9, slope = -0.047999, log2(nodes) = 31.696863 End of BKZ loop 16, time = 328.624s, r_0 = 9.20e9, slope = -0.048367, log2(nodes) = 31.795334 End of BKZ loop 17, time = 340.940s, r_0 = 9.20e9, slope = -0.048103, log2(nodes) = 31.876720 End of BKZ loop 18, time = 350.668s, r_0 = 9.20e9, slope = -0.048362, log2(nodes) = 31.940467 End of BKZ: success fplll 4.* in Sage: $ time fplll -a bkz -bkzautoabort -v -b 60 -bkzmaxloops 1 ~/test_lattice.txt -> killed after 80 minutes without finishing the first tour. -- _pgp: https://keybase.io/martinralbrecht _www: https://martinralbrecht.wordpress.com _jab:
