spielwiese. (Posts about lattice reduction.)https://spielwiese.fontein.de/tag/lattice-reduction.atom2019-11-17T10:45:12ZfelixNikolathe plll lattice reduction library.https://spielwiese.fontein.de/2014/07/16/the-plll-lattice-reduction-library/2014-07-16T08:27:53+02:002014-07-16T08:27:53+02:00felix<div><p>i’m very happy to announce that the <a href="https://en.wikipedia.org/wiki/Lattice_reduction">lattice reduction</a> library <a href="https://felix.fontein.de/plll/">plll</a> has finally been released as open source under the <a href="http://opensource.org/licenses/MIT">MIT license</a> by the <a href="https://www.uzh.ch">university of zurich</a>. during my recent years at the <a href="https://www.math.uzh.ch/">university of zurich</a>, i’ve been mainly working on this c++ library. it supports a wide range of <a href="https://en.wikipedia.org/wiki/Lattice_reduction">lattice reduction</a> algorithms and <a href="https://en.wikipedia.org/wiki/Shortest_vector_problem">svp</a> solvers, and makes heavy use of c++ templates and has support for <a href="https://en.wikipedia.org/wiki/C%2B%2B11">c++11</a>‘s <a href="https://en.wikipedia.org/wiki/C%2B%2B11#Rvalue_references_and_move_constructors">move operations</a>.</p>
<p>in 2011, i began implementing it since i wasn’t happy with some of the behavior of <a href="http://www.shoup.net/ntl/">ntl</a>‘s lattice reduction algorithms (mainly: in case of fatal numerical instability, they just terminate the program, and the library cannot be used in more than one thread at the same time). back then, ntl’s main competior <a href="http://perso.ens-lyon.fr/damien.stehle/fplll/">fplll</a> didn’t support <a href="https://en.wikipedia.org/wiki/Lattice_reduction">bkz</a> reduction, so i decided to try things out myself. after some time (years), my initial experiments grew into a full library supporting not only the more common <a href="https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm">lll</a> and bkz algorithms as well as <a href="https://en.wikipedia.org/wiki/Shortest_vector_problem">svp</a> solving by enumeration, but also several different algorithms for lattice reduction and svp solving which are described in literature but for which it is sometimes quite hard to find a working implementation of. though the implementations of these algorithms are still more on the experimental side, the basic algorithms such as lll, bkz, potentially combined with deep insertions, and enumeration, are well-tested over the years. (in fact, some large-scale lattice reduction experiments i did for these algorithms yielded some results in the <a href="http://www.latticechallenge.org/svp-challenge/halloffame.php">svp challenge’s hall of fame</a>).</p>
<p>in case you’re interested in <a href="https://felix.fontein.de/plll/">this library</a>, feel free to play around with it! in case you have any questions, encounter problems, or want to give feedback, feel free to contact me by <a href="mailto:felix@fontein.de">email</a>.</p></div>