The plll Lattice Reduction Library

Welcome to the homepage of the plll lattice reduction library. The plll library is a C++ library for lattice reduction, comparable to other such libraries as fplll and NTL.

The library was initially developed during several research projects at the Applied Algebra group at the University of Zurich from August 2011 on.

• Supports a wide range of lattice reduction algorithms:
  • several variants of LLL;
  • Schnorr-Euchner BKZ (by Schnorr and Euchner);
  • Simplified BKZ (by Hanrot, Pujol and Stehle);
  • Terminating BKZ (by Hanrot, Pujol and Stehle);
  • Primal-Dual BKZ (by Koy);
  • Slide Reduction (by Gama and Nguyen);
  • Improved Slide Reduction (by Schnorr);
  • Semi Block 2k Reduction (by Schnorr);
  • Sampling Reduction (by Buchmann and Ludwig).
• Supports a wide range of SVP solvers:
  • single-core and multi-core Kannan-Schnorr-Euchner enumeration;
  • Schnorr's new SVP solver;
  • Voronoi Cell computation;
  • several sieving algorithms.
• Supports a wide range of arithmetics:
  • native CPU integers and floating point arithmetic
  • GMP and MPFR arbitrary precision integer and floating point arithmetic;
  • rational arithmetic;
  • double-double and quad-double arithmetic (incomplete support).
• Supports a wide range of options:
  • several Deep Insertions configurations and variants;
  • different Gram-Schmidt orthogonalizations;
  • possibility to compute transformation matrices;
  • possibility to set up callback functions;
  • working on subranges of the lattice (using orthogonal projections).
• The library is threading-safe and can use several cores for enumeration.
• Support for C++11 move semantics.

More details can be found in the documentation, in particular in the secions Supported algorithms, Algorithm configuration and General configuration.

See the section Requisites for information on what is needed to compile the library. Here you can find all official versions of plll:

• Initial public release 1.0 (2014-07-14)

First, a (mostly) conforming C++ compiler (either C++03 or C++11/14) is needed. We have tested plll with the following compilers in both modes:

• GNU Compiler Collections (GCC);
• LLVM Clang.

In theory, it should also work fine with other conforming compilers.

An older version of plll also built with an older version of Oracle Solaris Studio on a UltraSparc machine. It might be possible that newer versions won't compile plll anymore since parts of the code have been rewritten after we had no longer access to a UltraSparc machine.

Besides a C++ compiler, the following libraries are needed to compile plll:

• GMP (forks such as MPIR should work as well);
• MPFR;
• the Boost libraries, in particular the thread, system and function libraries.

Optionally, plll will use the following library if it can find it:

• QD double-double/quad-double library.

Finally, plll uses CMake as a build system.

The documentation of the library's public interface can be found here. This documentation was created with the help of Doxygen, LaTeX, PGF/TikZ and Graphviz.

While plll is mainly a C++98/03 library, it is C++11/14 enabled in the sense that it has support for move operations and will use std::unique_ptr instead of std::auto_ptr in some situations internally. Even when compiled in C++11/14 mode, it will still use boost::thread and boost::function instead of std::thread and std::function so that the interface does not depend (except move semantics) whether the library is compiled in C++98/03 or C++11/14 mode. This might change in later versions, though.

• 2011–2014: development of the first version of the library at the University of Zurich.
• 2012 and 2013: during extensive tests of the plll library's LLL, BKZ and Deep Insertion code, several entries in the hall of fame of the SVP Challenge were added.
• July 2014: release as open source under the MIT license by the Applied Algebra group at the University of Zurich. (See also here.)

plll is licensed under the MIT license: