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