On Friday, August 5, 2016 at 12:32:58 PM UTC+1, Martin Albrecht 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. > > [X ] 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.0000, 5), > > End of BKZ loop 0, time = 12.832s, r_0 = 1.80e10, slope = -0.056809, > log2(nodes) = 28.142067 > End of BKZ loop 1, time = 25.072s, r_0 = 1.07e10, slope = -0.050003, > log2(nodes) = 29.120454 > End of BKZ loop 2, time = 36.836s, r_0 = 1.00e10, slope = -0.048468, > log2(nodes) = 29.623702 > End of BKZ loop 3, time = 48.944s, r_0 = 9.42e9, slope = -0.048443, > log2(nodes) = 29.991966 > End of BKZ loop 4, time = 58.176s, r_0 = 9.42e9, slope = -0.048230, > log2(nodes) = 30.207781 > End of BKZ loop 5, time = 67.904s, r_0 = 9.42e9, slope = -0.048134, > log2(nodes) = 30.414377 > End of BKZ loop 6, time = 78.040s, r_0 = 9.42e9, slope = -0.048500, > log2(nodes) = 30.611421 > End of BKZ loop 7, time = 87.780s, r_0 = 9.42e9, slope = -0.048197, > log2(nodes) = 30.784449 > End of BKZ loop 8, time = 96.468s, r_0 = 9.42e9, slope = -0.047948, > log2(nodes) = 30.910345 > End of BKZ loop 9, 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: martinr...@jabber.ccc.de <javascript:> > _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.
