HPLLL Library

Software library for linear algebra and Euclidean lattice problems

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

Download: newest master master.zip  / GitHub release  / Older versions.

• Installing
• Data types: integers and floating-point numbers
• Matrices
• LLL reduction
• Finding integer relations
• Known issues

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

Installing

Current master branch developed with macOS 10.12 with the compilers

      # clang++-mp-5.0 5.0.2 (seems to give better performances by default) 
      # MacPorts gcc8 8.2.0_3
      ./configure    
      ./configure --enable-omp  [other options, see below]       

Mandatory libraries for hplll

- GNU MP (6.1.2): http://gmplib.org

- MPFR (4.0.1)): http://www.mpfr.org

- FPLLL (5.2.1, or master branch): https://github.com/dstehle/fplll

Optional (highly recommended) library for fplll and hplll, searched by default :

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

Optional library for hplll:

- NTL (used with 10.5.0): http://www.shoup.net/ntl

Installation

      ./autogen.sh
      ./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-qd, --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.

128 bits floating points:

Tested by default. See Shi Bai branch in fplll.

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>

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>, Z_NR<__int128_t> (draft, not in fplll)

      FP_NR<double>, FP_NR<long double>,  FP_NR<dpe_t>, FP_NR<ldpe_t> (draft, not in fplll),  FP_NR<mpfr_t>

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 A using main parameters

Possibilities include:

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

Example:

After installation, 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.

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:

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.

Higher dimensions may however be reached with low precision floating-point numbers if the numerical quality (especially the condition number) is better than in the worst case.

Finding integer relations

Algorithms are looking for an integer relation between real (floating-point) numbers given by a wrapped mpfr vector, with a priori given precision alpha:

      vector<FP_NR<mpfr_t> > fpv;

      mpfr_set_default_prec(alpha);

      fpv.resize(d);

A class of tuples may then be used for accessing the relation computation:

      template<class ZT, class FT, class MatrixFT> class FPTuple

for example with the constructor

      FPTuple(vector<FP_NR<mpfr_t> > fpv);

For constructing a class L of tuples, possibilities include:

      FPTuple<long, double, matrix<FP_NR<double> > > L(fpv);
      FPTuple<long, long double, matrix<FP_NR<long double> > > L(fpv);

      FPTuple<__int128_t, long double, matrix<FP_NR<long double> > > L(fpv);

      FPTuple<mpz_t, dpe_t, MatrixPE<double, dpe_t> > L(fpv);  

Template parameters:

Algorithms will in general use a lifting strategy. Large integers or high precision floating-point numbers are truncated, and LLL is applied recursively on bases with smaller entries (lifting).

    -- Integer template type ZT: LLL will run on Z_NR<ZT> bases

    -- Floating-point template type FT: LLL will use FP_NR<FT> floating-point numbers

    -- Floating-point matrix template type MatrixFT: associated matrix type:

      <ZT, FT, MatrixFT> 

      <ZT, double, matrix<FP_NR<double> > >    // HPLLL method : no column + exponent  

      <ZT, dpe_t, MatrixPE<double, dpe_t> >   // HPLLL method : with column + exponent  

Template parameter types must be chosen according to the dimention of the problem (see LLL required precision), to the size of the targeted relation, and to truncation choices when calling the relation computation.

Relation computation:

int relation(ZZ_mat<mpz_t> C, long alpha, \
            long confidence_gap = 60, long shift = 10, int truncate = -1, int lllmethod = FPLLL, \
            int sizemethod=DEF_REDUCTION, double delta = 0.99);

    -- Relation(s) will be returned in "C",

    -- The "confidence_gap" is a number of bits corresponding to the chance of having found a relation,

    -- The "shift" gives the lifting step in bits,

    -- The truncation to integers keeps "truncate" bits,

    -- LLL is computed using the "lllmethod": either FPLLL or HLLL,

    -- "sizemethod" (with HLLL) is either DEF_REDUCTION or SEYSEN_REDUCTION,

    -- "delta" is the LLL reduction strength parameter.

File/benchmark format:

Files given for the examples or in the directory tests/collection/relations give the input mpfr precision (in bits), the number of floating-point numbers, and list the latter numbers.

Small examples:

You main try to compile the file "relation.cc" in the directory examples using:

      make -f make_ex relation

and run

      relation < alpha.in 

The 8 numbers a,b,... in the file alpha.in satisfies 8a+7b+...+2f+h ≈ 0.

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.

Larger examples:

Credit to David H. Bailey, Jonathan M. Borwein, Jason Kimberley and Watson Ladd, "Computer discovery and analysis of large Poisson polynomials," Experimental Mathematics, 27 Aug 2016, vol. 26, pg. 349-363, doi and pdf. See also PSLQ timings therein.

With:

    FPTuple<long, double, matrix<FP_NR<double> > > L(fpv);
    L.relation(C, alpha, 30, 20, 40, FPLLL);

Huge examples:

With:

    FPTuple<__128_t, double, matrix<FP_NR<double> > > L(fpv);
    L.relation(C, alpha, 20, 10, 40, HLLL);

Heuristic codes:

Faster but not quite reliable for the moment. See relationstest.cc, relationstesthuge.cc and:

      template<class ZT, class FT, class MatrixFT> class FPTuple_f 

      int relation(ZZ_mat<mpz_t>& C, long alpha, \
                  long confidence_gap = 60, long shift = 200, long increment = 20, \
                  int lllmethod = FPLLL, int sizemethod = DEF_REDUCTION, double delta = 0.99);

Known issues

• No wrapper method (almost ready in wrapper.h).
• Only heuristic breaks are implemented when lack of floating-point precision: could lead to infinite loops in rare cases.