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

- 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).

./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

make check

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

cd tests make relationstesthuge ./relationstesthuge

using namespace hplll #include <hplll.h>

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>

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

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 ...

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.

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);

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

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.

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:

Knapsack i7-3840QM CPU @ 2.80GHz |
d=8, 2000 bits | d=8, 2 10^{5} bits |
d=40, 1600 bits | d=100, 10^{4} bits |
d=128, 10^{4} bits |
d=140, 10^{4} bits |
d=160, 1.6 10^{4} 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 |

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.

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 |

Soon.

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