fplll

fplll contains implementations of several lattice algorithms. The implementation relies on floating-point orthogonalization, and LLL [LLL82] is central to the code, hence the name.

It includes implementations of floating-point LLL reduction algorithms [NS09,MSV09], offering different speed/guarantees ratios. It contains a 'wrapper' choosing the estimated best sequence of variants in order to provide a guaranteed output as fast as possible [S09]. In the case of the wrapper, the succession of variants is oblivious to the user.

It includes an implementation of the BKZ reduction algorithm [SE94], including the BKZ-2.0 [CN11] improvements (extreme enumeration pruning, pre-processing of blocks, early termination). Additionally, Slide reduction [GN08] and self dual BKZ [MW16] are supported.

It also includes a floating-point implementation of the Kannan-Fincke-Pohst algorithm [K83,FP85] that finds a shortest non-zero lattice vector. Finally, it contains a variant of the enumeration algorithm that computes a lattice vector closest to a given vector belonging to the real span of the lattice.

fplll is distributed under the GNU Lesser General Public License (either version 2.1 of the License, or, at your option, any later version) as published by the Free Software Foundation.

How to cite

@unpublished{fplll,
    author = {The {FPLLL} development team},
    title = {{fplll}, a lattice reduction library, {Version}: 5.5.0},
    year = 2023,
    note = {Available at \url{https://github.com/fplll/fplll}},
    url = {https://github.com/fplll/fplll}
}

Table of contents

• fplll
  • How to cite
• Table of contents
• Compilation
  • Installation from packages
    • Ubuntu and Debian
    • Conda
    • MacOS
    • Docker and AWS
  • Installation from source
    • Dependencies
      • Required, Optional.
    • Linux and MacOS
    • Windows 10
  • Check
  • Optimization
• How to use
  • Programs latticegen, fplll, llldiff.
  • How to use as a library
  • Multicore support
• Examples
• Alternative interfaces
• Credit
  • Maintainers, Contributors, Acknowledgments.
• Contributing
• New releases and bug reports
• Bibliography

Compilation

Installation from packages

fplll is available as a pre-built package for a variety of operating systems; these pre-built packages typically include all mandatory dependencies, and so these packages can be used to start running fplll quickly.

Below, we give some instructions on how to install these packaged variants of fplll.

Note that these packages will be up-to-date for the most recent version of fplll. However, if you want a feature that has recently been added to master (that is not yet in a release) then it is necessary to build from source. If this is the case, please see the Installation from Source section.

Ubuntu and Debian

fplll can be installed directly via Aptitude or Synaptic. Both of these package managers package fplll in the package fplll-tools. Therefore, to install this package using Aptitude, run the following command

sudo aptitude install fplll-tools

If you want to use Synaptic, then you will need to search for the fplll-tools package using the search bar.

Conda

fplll can be installed natively as a conda package using the following command

conda install fplll

MacOS

MacOS has a package for fplll inside HomeBrew. Assuming that you have HomeBrew installed, you may install fplll using the following command

brew install fplll

Docker and AWS

We now have Docker/AWS images for fplll too. They aren't on this repository, though; you can find them here

Installation from source

fplll can also be built from source. Below, we explicate some of the dependencies for building from source, as well as operating systems specific instructions.

Dependencies

Required

• GNU MP 4.2.0 or higher http://gmplib.org/ or MPIR 1.0.0 or higher http://mpir.org
• MPFR 2.3.0 or higher, COMPLETE INSTALLATION http://www.mpfr.org/
• autotools 2.61 or higher
• g++ 4.9.3 or higher

Optional

• QD 2.3.15 or higher (a C++/Fortran-90 double-double and quad-double package), compile and install the shared library (e.g. ./configure --enable-shared=yes). http://crd-legacy.lbl.gov/~dhbailey/mpdist/

NOTE: If you are intending to use fplll on Windows 10, then these packages should be installed after the Windows Subsystem for Linux has been installed and activated. Please go to the Windows 10 instructions for more information.

Linux and MacOS

You should download the source code from Github and then run

./autogen.sh

which generates the ./configure script used to configure fplll by calling the appropriate autotools command.

Then, to compile and install type

./configure
make
make install			# (as root)

If GMP, MPFR and/or MPIR are not in the $LD_LIBRARY_PATH, you have to point to the directories where the libraries are, with

./configure --with-gmp=path/to/gmp

or

./configure --with-mpfr=path/to/mpfr

The same philosophy applies to the (optional) QD library. If you want to use mpir instead of gmp, use --enable-mpir and --with-mpir=path/to/mpir.

You can remove the program binaries and object files from the source code directory by typing make clean. To also remove the files that ./configure created (so you can compile the package for a different kind of computer), type make distclean. By default, make install installs the package commands under /usr/local/bin, include files under /usr/local/include, etc. You can specify an installation directory name other than /usr/local by giving ./configure the option --prefix=dirname. Run ./configure --help for further details.

Windows 10

Windows 10 has the "Windows Subsystem for Linux"(WSL), which essentially allows you to use Linux features in Windows without the need for a dual-boot system or a virtual machine. To activate this, first go to Settings -> Update and security -> For developers and enable developer mode. (This may take a while.) Afterwards, open Powershell as an administrator and run

Enable-WindowsOptionalFeature -Online -FeatureName Microsoft-Windows-Subsystem-Linux

This will enable the WSL. Next, open the Windows Store and navigate to your favourite available Linux distribution - this may be installed as if it were a regular application. Afterwards, this system will act as a regular program, and so it can be opened however you like e.g. by opening command prompt and typing bash. With this Linux-like subsystem, installing fplll is then similar to above, except that most likely the package repository is not up to date, and various additional packages need to be installed first. To make sure you only install the most recent software, run:

sudo apt-get update

Then run sudo apt-get install <packages> for the (indirectly) required packages, such as make, autoconf, libtool, gcc, g++, libgmp-dev, libmpfr-dev and pkg-config. Finally, download the fplll source code, extract the contents, navigate to this folder in Bash (commonly found under /mnt/c/<local path> when stored somewhere on the C:\ drive), and run:

./autogen.sh
./configure
make 

The same comments as before apply for using e.g. make install or make distclean instead of make.

Note: to fix a potential error libfplll.so.5: cannot open shared object file: No such file or directory raised after trying to run fplll after a successful compilation, find the location of libfplll.so.5 (probably something like /../fplll/.libs/; run find -name libfplll.so.5 to find it) and run export LD_LIBRARY_PATH=<path>.

Check

Type

make check

Optimization

The default compilation flag is -O3. One may use the -march=native -O3 flag to optimize the binaries. See "this issue" for its impact on the enumeration speed.

How to use

Executable files fplll and latticegen are installed in the directory /usr/local/bin. (Note that the programs generated by make in the fplll/ directory are only wrappers to the programs in fplll/.libs/).

If you type make check, it will also generate the executable file llldiff, in fplll/.libs/.

latticegen

latticegen is a utility for generating matrices (rows form input lattice basis vectors).

The options are:

• r d b : generates a knapsack like matrix of dimension d x (d+1) and b bits (see, e.g., [S09]): the i-th vector starts with a random integer of bit-length <=b and the rest is the i-th canonical unit vector.
• s d b b2 : generates a d x d matrix of a form similar to that is involved when trying to find rational approximations to reals with the same small denomin