HPLLL Library

Chantier


Next: 

Software library for linear algebra and Euclidean lattice problems

hplll is an experimental C++ library, companion to fplll.

Download: hplll-0.1.1.tar.gz (June 20, 2016 17:00) / Older versions.

Problem and bug reports may be sent to gilles.villard@ens-lyon.fr


Next: , Up: Top

Installing

Mandatory libraries for hplll

- GNU MP 4.2.0, or higher: http://gmplib.org

- MPFR 2.3.0, or higher: http://www.mpfr.org

- FPLLL 4.0.0, or higher: https://github.com/dstehle/fplll

Optional library for fplll:

- QD 2.3.17, or higher: http://crd-legacy.lbl.gov/~dhbailey/mpdist, see fplll options.

Optional library for hplll:

- NTL 6.1.0, or higher (http://www.shoup.net/ntl).

Installation

      ./configure
      make
      make install    

OpenMP option:

      ./configure --enable-omp

If gmp, mpfr or hplll are installed under non-standard directories you can specify their locations by using configure with the option --with-gmp, --with-mpfr, --with-fplll. For ntl also (optional), you can use --with-ntl. By default, make install installs files under /usr/local, you can specify another installation directory by giving ./configure the option --prefix=dirname. Run ./configure --help for further details.

Another example:

      ./configure --with-gmp=/local/gmpdir/  --with-fplll=/fpllldir   --prefix=$HOME/soft
      make
      make install   

Check

      make check 

An additional check, not included by default, is a bit more time consuming:

      cd tests
      make relationstesthuge
      ./relationstesthuge

Related to the API

      using namespace hplll

      #include <hplll.h>

 


Next: , Previous: Installing, Up: Top

Data types

The interfaces and data types Z_NR<.> for integers and FP_NR<.> for floating-point numbers are inherited from fplll, and can be used with several ground types:

      Z_NR<long>, Z_NR<mpz_t>, draft implementation of Z_NR<__int128_t>

      FP_NR<double>, FP_NR>long double>,  FP_NR<dpe_t>, FP_NR<ldpe_t> (non fplll),  FP_NR<mpfr_t>

 


Next: , Previous: Data types, Up: Top

Matrices

The fplll class ZZ_mat is used for lattice bases.

The classes

      template<class T> class matrix
      template<class T, class DPET> class MatrixPE

are used internally in hplll codes, and as template parameters for lattice classes.

Nota bene. fplll lattice bases are formed by rows of matrices, for the moment in hplll the bases are formed by columns of matrices. Transposition is available, for example:

      ZZ_mat<long> A,B;
      A.resize(d,n);
      B.resize(n,d);
      transpose(B,A);    // B:=A^T

Generation of bases:

The fplll utility latticegen and associated library functions can be used for generating special lattice bases.

The function

      void command_line_basis(ZZ_mat<mpz_t>& A, int& n, int& d, double& delta, int argc, char *argv[])

can be included in a code for constructing special bases at running time:

      ZZ_mat<mpz_t> A;
      int n,d;
      double delta;

      command_line_basis(A, n, d, delta, argc, argv);  // Constructs B using main parameters

Possibilities include:

      main -type r -d 40 -bits 244      // Knapsack (d+1) x d matrix
           -type a -d 40 -alpha 1.4     // Ajtai d x d matrix
           -type al -d 240              // Seysen tests d x d bases 
           ...

Example:

You main try to compile the file "gen.cc" and run "gen" in the directory examples using:

      make -f make_ex gen;
      gen -type r -d 8 -bits 40
      gen -type al -d 20

Note that you may have to modify the make file "make_ex" according to your software installations (especially if not standard as root) before compiling for finding include files and libraries.

 


Next: , Previous: Matrices, Up: Top

LLL reduction

Construction:

A lattice is constructed using the class

      template<class ZT, class FT, class MatrixZT, class MatrixFT> class Lattice

One of the constructors is:

      Lattice(ZZ_mat<ZT> A, bool forU=NO_TRANSFORM, int reduction_method=DEF_REDUCTION, int long_flag = WITH_LONG)

      Lattice<.> B(A);

      forU = NO_TRANSFORM or TRANSFORM   // Possible computes the unimodular transformation matrix 
      reduction_method= DEF_REDUCTION or SEYSEN_REDUCTION
      long_flag = WITH_LONG or NO_LONG   // Heuristic optimization during size reduction  

Possibilities for the construction include:

      // mpz_t or any integer type such as long or __int128_t

      ZZ_mat<mpz_t> A;   

      // With dense matrices of floating-point numbers

      Lattice<mpz_t, double, matrix<Z_NR<mpz_t> >, matrix<FP_NR<double> > > B(A);
      Lattice<mpz_t, long double, matrix<Z_NR<mpz_t> >, matrix<FP_NR<long double> > > B(A);

      // With column dpe_t matrices à la fplll (floating-point vectors and a common exponent) 

      Lattice<mpz_t, dpe_t, matrix<Z_NR<mpz_t> >, MatrixPE<double, dpe_t> > B(A);
    

Basis reduction:

      int hlll(double delta);

         Ex: B.hlll(0.99)  // LLL reduction

      ZZ_mat<ZT> getbase();

         Ex: B.getbase();  // Returns the current state of the basis

      ZZ_mat<ZT> getU();

         Ex: B.getU();  // Returns the transform if known 

Example:

You main try to compile the file "gcd.cc" and run "gcd" in the directory examples using:

      make -f make_ex gcd;
      gcd

Note that you may have to modify the make file "make_ex" according to your software installations (especially if not standard as root) before compiling for finding include files and libraries.

Peformances:

Since in particular Householder orthogonalization induces a higher overhead than Cholesky one, fplll is recommended and should be faster for bases of small and medium dimensions:

-type r -d x -bits y
Knapsack
i7-3840QM CPU @ 2.80GHz
d=8, 2000 bits d=8, 2 105 bits d=40, 1600 bits d=100, 104 bits d=128, 104 bits d=140, 104 bits d=160, 1.6 104 bits
FPLLL wrapper 4 ms 3.4 s 0.35 s 55 s 126 s 174 s 9.2 mn
HPLLL 11 ms 4 s 0.66 s 63 s 136 s 177 s 8.4 mn

-type a -d x -alpha y
Ajtai
i7-3840QM CPU @ 2.80GHz
d=8, 2.0 d=8, 4.0 d=20, 2.8 d=60, 1.4 d=100, 0.8
FPLLL wrapper 1 ms 1.2 s 14.4 s 8.4 s 2.7 s
HPLLL 2.2 ms 1.6 s 18.6 s 11.4 s 3.2 s

hplll reduction may be faster than fplll one as soon as the dimension is greater than 160-170. Indeed, for any given floating-point precision used during the reduction, if fplll can reduce bases of dimension as large as d, then hplll should be able reduced bases of dimension at least 2d. When the dimension increases, the fplll wrapper gradually uses more precision.

-type r -d x -bits y
Knapsack
CPU E5-2695 v3 @ 2.30GHz
d=200, 20000 bits d=240, 24000 bits d=280, 28000 bits
FPLLL wrapper 40 mn 3h02 7h34
HPLLL 31 mn 1h11 2h20

 


Next: , Previous: LLL, Up: Top

Finding integer relations

Soon.

 


Previous: Integer relations, Up: Top

Known issues

 


Valid XHTML 1.0 Strict