fplll 4.0

Overall description

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.

fplll contains several algorithms on lattices that rely on floating-point computations. This includes implementations of the floating-point LLL reduction algorithm, 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. In the case of the wrapper, the succession of variants is oblivious to the user. It also includes a rigorous floating-point implementation of the Kannan-Fincke-Pohst algorithm that finds a shortest non-zero lattice vector, and the BKZ reduction algorithm.

Dependencies

Absolutely needed:

If GMP and/or MPFR include and lib files are not in the default directories /usr/include and /usr/lib, you have to set the environment variables CFLAGS and LDFLAGS for instance through the configure command line

configure CPPFLAGS="-I/mpfrinclude -I/gmpinclude" LDFLAGS="-L/mpfrlib -L/gmplib"
or
configure CPPFLAGS="-I/mpfrinclude -I/gmpinclude $CPPFLAGD" LDFLAGS="-L/mpfrlib -L/gmplib $LDFLAGS"
if these variables already exist in your environment. This should be modified soon for using standard --with-gmp and --with-mpfr package specifications.

Installation

To install files 'cd' to the directory containing the package's source code and just type

 ./configure
 make 
 make install      # (as root)

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.

Check

'cd' to the src directory, and type
 make check
This tests the LLL wrapper given dim55_in as input. If the error message 'INVALID RESULT' is not printed, the self-test has succeeded.

How to use

Executable files fplll and latticegen are installed in the directory bin. If you type 'make check', it will also generate the file llldiff. (Note that the programs generated by make in the 'src/' directory are only wrappers to the programs in 'src/.libs/)

latticegen

latticegen is an utility for generating matrices (rows form input lattice bases).

The options are :

The matrix is printed in stdout.

Note that by default, the random bits always use the same seed, to ensure reproducibility. You can change the seed with the option

 -randseed <integer>
or use the current time (in seconds)
 -randseed time
If you use this option, it must be the first one on the command line.

fplll

fplll does LLL, BKZ or SVP on a matrix (considered as a set of row vectors) given in stdin or in a file as parameter.

The options are:

-a lll : LLL-reduction (default).
-a bkz : BKZ-reduction.
-a svp : print a shortest vector of the lattice.

-r <size>, -c <size> : ignored, provided for compatibility with previous
                       versions of fplll.

Options for LLL-reduction:

-d <delta> :     delta (default=0.99)
-e <eta> :       eta (default=0.51)
-l <lovasz> :    if !=0 Lovasz's condition. Otherwise, Siegel's condition (default: Lovasz)
-p <precision> : precision of the floating-point arithmetic, works 
                 only with -f mpfr.

-f mpfr : sets the floating-point type to MPFR (default if m=proved).
-f dpe : sets the floating-point type to DPE (default if m=heuristic/heuristicearly).
-f double : sets the floating-point type to double (default if m=fast/fastearly).
-f longdouble : sets the floating-point type to long double.
-z int : sets the integer type to int.
-z mpz : sets the integer type to mpz, the integer type of GMP (default).
-z double : sets the integer type to double.

-m wrapper : uses the wrapper. (default if z=mpz)
-m fast : uses the fast method, works only with -f double.
-m fastearly : uses the fast method with early reduction, works only 
               with -f double.
-m heuristic : uses the heuristic method.
-m heuristicearly : uses the heuristic method with early reduction.
-m proved : uses the proved version of the algorithm.

With the wrapper or the proved version, it is guaranteed that the basis is
LLL-reduced with delta'=2*delta-1 and eta'=2*eta-1/2. For instance, with the
default options, it is guaranteed that the basis is (0.98,0.52)-LLL-reduced.

Options for BKZ-reduction:

-b <blocksize>            Block size, mandatory, between 2 and the number of rows.
-f <float_type>           Same as LLL (-p is required if float_type=mpfr)
-p <precision>            Precision of the floating-point arithmetic with -f mpfr
-bkzmaxloops <loops>      Maximum number of full loops.
-bkzmaxtime <time>        Stop after time seconds (up to loop completion).
-bkzautoabort             Heuristic, stop when the average slope of log(||b_i*||)
                          does not decrease fast enough.

llldiff

llldiff compares two bases (b1,...,bd) and (c1,...c_d'): they are considered equal iff d=d' and for any i, bi = +- ci.

How to use as a library

At the beginning of your code, type:

#include <fplll.h>
using namespace fplll;

See the example file test.cpp in the src directory. To compile it, assuming fplll has been installed in /tmp/fplll:

bash-3.00$ g++ -static -I /tmp/fplll/include test.cpp -L /tmp/fplll/lib -lfplll -lmpfr -lgmp
bash-3.00$ ./a.out
[[4 3 7]
[3 0 1]
[3 5 3]]
[[3 0 1]
[2 2 -3]
[0 5 2]]
All types, functions and constants are wrapped in the fplll namespace, with the exception of the dpe type defined in dpe.h. Preprocessor definitions prefixed by FPLLL_ are reserved for internal use.

Functions

LLL

int lllReduction(ZZ_mat<mpz_t>& b, double delta = 0.99, double eta = 0.51, LLLMethod method = LM_WRAPPER, FloatType floatType = FT_DEFAULT, int precision = 0, int flags = LLL_DEFAULT)

LLL-reduces a basis of Z_NR<mpz_t>.

It is guaranteed that the output is (delta', eta')-LLL-reduced with delta'=2×delta-1, eta'=2×eta-1/2 provided that method=LM_WRAPPER/LM_PROVED, floatType=FT_DEFAULT and precision=0. For instance, with the default parameters, it is guaranteed that the output basis is (0.98, 0.52)-LLL-reduced.

Parameters:

b
Input basis. It is reduced in place.
delta
Relaxation factor in the Lovász condition. Must be greater than 1/4 and lower than 1.
eta
Relaxation factor in the size reduction. Must be greater that 1/2 and lower than sqrt(delta).
method
One of the following values:
LM_WRAPPERTries to reduce the matrix with a combination of the following methods with increasing precision. Then, runs the proved version with the default precision. floatType must be FT_DEFAULT and precision must be 0. The result is guaranteed (see above).
LM_PROVEDProved method. Uses integers to compute dot products. The result is guaranteed if floatType=FT_DEFAULT/FT_MPFR and precision=0 (see above).
LM_HEURISTICHeuristic method. Uses floating-point numbers to compute dot products. The result is not guaranteed. It is more efficient that the proved version when the coefficients of the input are large (the threshold depends on the floating-point type and precision).
LM_FASTSame as LM_HEURISTIC with floatType=FT_DOUBLE, with a special trick to handle larger inputs.
floatType
Possibles values are:
LM_WRAPPERLM_PROVEDLM_HEURISTICLM_FAST
FT_DEFAULTyesyes
same as FT_MPFR
yes
same as FT_DPE
yes
same as FT_DOUBLE
FT_DOUBLEnoyesyesyes
FT_DPEnoyesyesno
FT_MPFRnoyesyesno
precision
If floatType is not FP_MPFR, this parameter must be zero. If floatType is FP_MPFR,
  • if this parameter is zero, the precision of floating-point computation is the one required to ensure that the proved method returns a correct result (note that if the heuristic method is used with this precision, nothing is guaranteed);
  • if this parameter is larger than or equal to 53, it forces the precision in floating-point computations.
flags
Can be LLL_DEFAULT or a combination of the following values:
LLL_VERBOSEDisplays information on stderr.
LLL_EARLY_REDEnables early reduction. This might be faster on (nearly) lower triangular matrices. Currently, this flag is not compatible with the proved method.
LLL_SIEGELUses Siegel condition instead of Lovász condition.

Return value:

RED_SUCCESSSuccess.
RED_BABAI_FAILUREError.
RED_LLL_FAILUREError: infinite loop in LLL.
Any other valueError.

Even if an error occurs, it is guaranteed that b remains a basis of the same lattice.

int lllReduction(ZZ_mat<long>& b, double delta = 0.99, double eta = 0.51, LLLMethod method = LM_FAST, FloatType floatType = FT_DEFAULT, int precision = 0, int flags = LLL_DEFAULT)
LLL-reduces a basis of Z_NR<long>. There is no guarantee and the LM_WRAPPER method is not available.
int lllReduction(ZZ_mat<double>& b, double delta = 0.99, double eta = 0.51, LLLMethod method = LM_FAST, FloatType floatType = FT_DEFAULT, int precision = 0, int flags = LLL_DEFAULT)
LLL-reduces a basis of Z_NR<double>. There is no guarantee and the LM_WRAPPER method is not available.

BKZ

int bkzReduction(IntMatrix& b, int blockSize, int flags = BKZ_DEFAULT)

BKZ-reduces a basis of Integers.

Parameters:

b
Input basis. It is reduced in place.
blockSize
Controls the strength of the reduction (as low as LLL if blockSize=2, as high as HKZ when blockSize=b.getRows()).
flags
Can be BKZ_DEFAULT or a combination of the following values:
BKZ_VERBOSEDisplays information on stderr.
BKZ_NO_LLLAssumes that the input basis is already LLL-reduced (otherwise, an LLL-reduction is performed with the LLL wrapper to avoid numerical problems)

Return value:

RED_SUCCESSSuccess.
RED_BABAI_FAILUREError in the semi-reduction subroutine.
RED_LLL_FAILUREError: infinite loop in the LLL subroutine.
RED_ENUM_FAILUREError in the SVP subroutine.
RED_BKZ_FAILUREError in BKZ.
RED_BKZ_TIME_LIMITTime limit exceeded in BKZ.
RED_BKZ_LOOPS_LIMITMaximum number of loops exceeded in BKZ.
Any other valueError.

Even if an error occurs, it is guaranteed that b remains a basis of the same lattice.

int bkzReduction(IntMatrix& b, IntMatrix& u, int blockSize, int flags = BKZ_DEFAULT)
Same as above, but also computes the transform matrix u such that bnew = u × bold.
int bkzReduction(const BKZParam& param)

Same as above with more options.

Fields of BKZParam:

  struct BKZParam {
    BKZParam() : b(NULL), u(NULL), blockSize(0), delta(LLL_DEF_DELTA),
      floatType(FT_DEFAULT), precision(0), flags(BKZ_DEFAULT),
      maxLoops(0), maxTime(0) {}
    IntMatrix* b;
    IntMatrix* u;
    int blockSize;
    double delta;
    FloatType floatType;
    int precision;
    int flags;
    int maxLoops;
    double maxTime;
    vector<double> pruning;
  };
  
b
Pointer to the matrix to reduce in place.
u
Pointer to the transform matrix (can be null if not needed).
blockSize
Between 2 and b.getRows(), controls the strength of the reduction.
delta
Used by the LLL subroutine.
floatType
Internal data type for floating-point computations (FT_DEFAULT, FT_DOUBLE, FT_LONG_DOUBLE, FT_DPE or FT_MPFR). FT_DEFAULT is currently equivalent to FT_DOUBLE.
precision
Internal precision of floating-point computations when floatType = FT_MPFR.
flags
Can be BKZ_DEFAULT or a combination of the following values:
BKZ_VERBOSEDisplays information on stderr.
BKZ_NO_LLLAssumes that the input basis is already LLL-reduced (otherwise, an LLL-reduction is performed with the LLL wrapper to avoid numerical problems)
BKZ_MAX_LOOPSEnable parameter maxLoops.
BKZ_MAX_TIMEEnable parameter maxTime.
maxLoops
Forced stop after maxLoops loops (enabled by the BKZ_MAX_LOOPS flag).
maxTime
Forced stop after around maxTime seconds (enabled by the BKZ_MAX_TIME flag, the condition is checked only after each full loop).
pruning
Vector of size blockSize that enables heuristic speed-up of the enumeration subroutine. If not empty, it must contain blockSize values in the interval (0,1], starting with 1, in non-increasing order.

Return value: Same as above.

SVP

int shortestVector(IntMatrix& b, vector<Integer>& solCoord, SVPMethod method = SVPM_PROVED, int flags = SVP_DEFAULT)

Computes a shortest non-zero vector of a lattice. The basis must be LLL-reduced with delta = 0.99 and eta = 0.51. The result is guaranteed if method = SVPM_PROVED.

Parameters

b
LLL-reduced input basis.
solCoord
Output: coordinates of a shortest vector non-zero of L(b) in the basis b.
method
SVPM_PROVED (the result is guaranteed provided that the basis is (0.99,0.51)-LLL-reduced) or SVPM_FAST (nothing is guaranteed).
flags
SVP_DEFAULT or SVP_VERBOSE (displays information on stderr).

Return value:

RED_SUCCESSSuccess.
RED_ENUM_FAILUREError: no solution found.
Any other valueError.

Data types

Z_NR<Z>

Z_NR stores integers. This template provides a uniform interface for doing integer computations with several underlying types (long, double and mpz_t).

Methods:

Z_NR()
Default constructor. The initial value is undefined.
Z_NR(const Z_NR<Z>& x)
Copy constructor.
~Z_NR<Z>()
Destructor.
double get_d() const
Converts this object to a double. If it does not fit in a double, the result is undefined.
double get_d_2exp(long* expo) const
Computes expo such value 2^(expo-1) <= value < 2^expo and returns value / 2^expo. This means that expo = floor(log2(value)) - 1. If the value of this object is zero, returns 0 and sets expo = 0.
long get_si() const
Converts this object to a long. If it does not fit in a long, the result is undefined.
template<class F> void set_f(const FP_NR<F>& x)
Sets the value to x. When F=mpfr_t, x is rounded to the nearest integer and if the fractional part of x is 0.5, the even integer is chosen when. Otherwise, the rounding direction is undefined.
void set_str(const char* s)
Sets the value to s, signed integer in basis 10.
void operator=(const Z_NR<Z>& x)
void operator=(long x)
Sets the value to x.
int cmp(const Z_NR<Z>& x) const
3-way comparison. Returns a positive number if *this > x, a negative number if *this < x or zero is *this == x.
int sgn() const
Sign. Returns a positive number, a negative number or zero if the value of this object is respectively positive, negative or null.
inline bool operator<(const Z_NR<Z>& x) const
inline bool operator>(const Z_NR<Z>& x) const
inline bool operator<=(const Z_NR<Z>& x) const
inline bool operator>=(const Z_NR<Z>& x) const
inline bool operator==(const Z_NR<Z>& x) const
inline bool operator!=(const Z_NR<Z>& x) const
inline bool operator<(long x) const
inline bool operator>(long x) const
inline bool operator<=(long x) const
inline bool operator>=(long x) const
inline bool operator==(long x) const
inline bool operator!=(long x) const
Comparison operators.
void add(const Z_NR<Z>& x, const Z_NR<Z>& y)
void sub(const Z_NR<Z>& x, const Z_NR<Z>& y)
void mul(const Z_NR<Z>& x, const Z_NR<Z>& y)
void mul_si(const Z_NR<Z>& x, long y);
void abs(const Z_NR<Z>& x)

Sets the value of this object to x + y, x - y, x × y, x × y, or |x| (respectively).
void addmul(const Z_NR<Z>& x, const Z_NR<Z>& y)
Adds x × y to the current value.
void submul(const Z_NR<Z>& x, const Z_NR<Z>& y)
Subtracts x × y from the current value.
void swap(Z_NR<Z>& a)
Efficiently swaps the values of two Z_NR.
T& getData()
const T& getData() const
Returns the internal representation of the data.

Non-member functions:

template <class Z>
ostream& operator<<(ostream& os, const Z_NR<Z>& x)

Prints x on stream os.
template <class Z>
istream& operator>>(istream& is, Z_NR<Z>& x)

Reads x from stream is.

Containers:

typedef Z_NR<mpz_t> Integer;
typedef std::vector<Integer> IntVect;
typedef ZZ_mat<mpz_t> IntMatrix;

FP_NR<F>

FP_NR stores floating-point numbers. This template provides a uniform interface for doing floating-point computations with several underlying types (double, dpe_t and mpfr_t). For all functions, the rounding mode rnd is ignored unless F=mpfr_t.

Methods:

FP_NR()
Default constructor. The initial value is undefined.
FP_NR(const FP_NR<F>& x)
Copy constructor.
~FP_NR<F>()
Destructor.
double get_d() const
Converts this object to a double. If it does not fit in a double, the result is undefined.
long get_si() const
Converts this object to a long. The rounding direction is undefined. If it does not fit in a long, the result is undefined.
template<class Z> void set_z(const Z_NR<Z>& x, mp_rnd_t rnd = GMP_RNDN)
Sets the value to x.
void operator=(const FP_NR<F>& x)
void operator=(double x)
Sets the value to x.
int cmp(const FP_NR<F>& x) const
int cmp(double x) const
3-way comparison. Returns a positive number if *this > x, a negative number if *this < x or zero is *this == x.
int sgn() const
Sign. Returns a positive number, a negative number or zero if the value of this object is respectively positive, negative or null.
inline bool operator<(const FP_NR<F>& x) const
inline bool operator>(const FP_NR<F>& x) const
inline bool operator<=(const FP_NR<F>& x) const
inline bool operator>=(const FP_NR<F>& x) const
inline bool operator<(double x) const
inline bool operator>(double x) const
inline bool operator<=(double x) const
inline bool operator>=(double x) const
Comparison operators.
void add(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)
void sub(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)
void neg(const FP_NR<F>& x)
void mul(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)
void mul_2si(const FP_NR<F>& x, int c);
void div(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)
void sqrt(const FP_NR<F>& x, mp_rnd_t rnd = GMP_RNDN)
void pow_si(const FP_NR<F>& x, long c, mp_rnd_t rnd = GMP_RNDN)
void exponential(const FP_NR<F>& x, mp_rnd_t rnd = GMP_RNDN)
void log(const FP_NR<F>& x, mp_rnd_t rnd = GMP_RNDN)
void abs(const FP_NR<F>& x)
void rnd(const FP_NR<F>& x);
void floor(const FP_NR<F>& x);

Sets the value of this object to x + y, x - y, -x, x × y, x × 2c, x / y, square root of x, xc, exponential of x, natural logarithm of x, |x|, x rounded to the nearest integer, largest integer not greater than x (respectively).
void addmul(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)
Adds x × y to the current value.
void submul(const FP_NR<F>& x, const FP_NR<F>& y, mp_rnd_t rnd = GMP_RNDN)
Subtracts x × y from the current value.
int zero_p() const
Returns non-zero if the current value is zero, 0 otherwise.
void set_nan()
value := NaN.
int is_nan() const
Returns non-zero if the current value is NaN, 0 otherwise.
void swap(FP_NR<F>& x)
Efficiently swaps the values of two FP_NR.
T& getData()
const T& getData() const
Returns the internal representation of the data.

Static members:

static unsigned int getprec()
Returns the current precision for new FP_NR<F> objects.
static inline unsigned int setprec(unsigned int prec)
Sets the precision of new FP_NR<F> objects. Returns the previous value. This has no effect is F != mpfr_t.

Non-member functions:

template <class F>
ostream& operator<<(ostream& os, const FP_NR<F>& x)

Prints x on stream os.

Containers:

typedef FP_NR<mpfr_t> Float;
typedef std::vector<Float> FloatVect;
typedef FP_mat<mpfr_t> FloatMatrix;

Matrix<T>

Methods:

Matrix()
Creates an empty matrix (0 × 0).
Matrix(int rows, int cols)
Creates a matrix of dimensions rows × cols. All elements are initialized with the default constructor of T.
void clear()
Sets number of rows and the number of columns to 0.
void resize(int rows, int cols)
Sets the dimensions of the matrix, preserving as much as possible of the content. The content of new cells is undefined.
void setRows(int rows)
Sets the number of rows (content is not erased except for deleted rows).
void setCols(int cols)
Sets the number of columns (content is not erased except for deleted columns).
template<class U> void fill(U value)
Fills the matrix with a given value.
void swap(Matrix& m)
Efficiently swaps two matrices.
int getRows() const
Returns the number of rows.
int getCols() const
Returns the number of columns.
T& operator()(int i, int j)
const T& operator()(int i, int j)
Returns a reference to a coefficient of the matrix.
MatrixRow<T> operator[](int i)
const MatrixRow<T> operator[](int i) const
Returns a MatrixRow object pointing to the i-th row of the matrix.

Non-member functions:

template<class T> ostream& operator<<(ostream& os, const Matrix<T>& m)
Prints matrix m on stream os.
template<class T> istream& operator>>(istream& is, Matrix<T>& m)
Reads matrix m from stream is.

Note: a call to clear, resize, setRows, setCols or swap invalidates all references returned by operator() and MatrixRow objects returned by operator[].

MatrixRow<T>

MatrixRow stores a reference to a row of a Matrix. It supports a subset of operations available on vectors.

Methods:

T& operator[](int i)
const T& operator[](int i) const
Returns a reference to the i-th element of this row.
int size() const
Returns the number of columns.

Non-member functions:

template<class T> ostream& operator<<(ostream& os, const MatrixRow<T>& mr)
Prints mr on stream os.

ZZ_mat<ZT>

Base class: Matrix<Z_NR<ZT>>

Matrix of integers. Same constructors as Matrix.

FP_mat<FT>

Base class: Matrix<FP_NR<FT>>

Matrix of floating-point nubmers. Same constructors as Matrix.

See also

Documentation of std::vector

Examples

1)
./latticegen r 10 1000 | ./fplll

2)
If the file 'matrix' contains 
[[ 10 11]
[11 12]]

Then 
./fplll matrix
produces
[[0 1 ]
[1 0 ]
]

3) Random generator
./latticegen -randseed 1234 r 10 1000 | ./fplll
./latticegen -randseed time u 10 16 | ./fplll

4) Solving SVP
./latticegen r 30 3000 | ./fplll -a svp

Developers

Current developer:
Damien Stehle, damien.stehle@gmail.com

Former developers:
David Cade, david.cade@ens.fr
Xavier Pujol, xavier.pujol@ens-lyon.org

Acknowledgements

Patrick Pelissier and Paul Zimmermann for dpe.

Martin Albrecht, Sylvain Chevillard, Christoph Lauter and Gilles Villard for the "configure/make/make install" packaging.

Martin Albrecht for the incorporation into SAGE.

Timothy Abbott, Michael Abshoff, Martin Albrecht, Bill Allombert, John Cannon, Sylvain Chevillard, Julien Clement, Andreas Enge, Jean-Pierre Flori, Laurent Fousse, Guillaume Hanrot, Jens Hermans, Jerry James, Christoph Lauter, Andrew Novocin, Willem Jan Palenstijn, Patrick Pelissier, Michael Schneider, Thiemo Seufer, Allan Steel, Gilles Villard and Paul Zimmermann for their support and for many suggestions that helped debugging and improving this code.

New releases and bug reports

New releases will be announced at the URL: http://perso.ens-lyon.fr/damien.stehle/fplll/

Bug reports may be sent at: