- Overall description
- Dependencies
- Installation
- Check
- How to use
- How to use as a library
- Expamles
- Developers
- How to cite
- Acknowledgments
- New releases and bug reports
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.
- Absolutely needed:
- GNU MP 4.2.0 or higher http://gmplib.org/
- MPFR 2.3.0 or higher, COMPLETE INSTALLATION http://www.mpfr.org/
- autotools 2.61 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/]
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. The same philosophy applies to the (optional) QD library.
You should downloaded 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)
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.
'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.
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 is an utility for generating matrices (rows form input lattice bases).
The options are :
- r
d
b
: generates a knapsack style matrix of dimension d,d+1 and b bits. - s
d
b
b2
: generates a simdioph matrix. - u
d
b
: generates an uniform matrix. - n
d
b
q
: generates an ntru like matrix. - N
d
b
q
: generates an ntru like matrix. - a
d
f
: generates an ajtai style matrix. - A
d
: generates an ajtai style matrix. Also requires d coefficients.
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 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
, -csize
: 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 dd : sets the floating-point type to double-double.
-
-f qd : sets the floating-point type to quad-double.
-
-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.
- -bpre
blocksize
Pre-processing block size. Between 2 and the block size. - -bkzlinearpruning
level
Enables linear pruning in enumeration, such that the last level steps drop with slope -1/blockSize - -bkzdumgso
file_name
Dumps the log(||b_i*||)'s in specified file.
llldiff compares two bases (b1,...,bd) and (c1,...c_d'): they are considered equal iff d=d' and for any i, bi = +- ci.
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.
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_WRAPPER Tries 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_PROVED Proved method. Uses integers to compute dot products. The result is guaranteed if floatType=FT_DEFAULT/FT_MPFR and precision=0 (see above). LM_HEURISTIC Heuristic 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_FAST Same as LM_HEURISTIC with floatType=FT_DOUBLE, with a special trick to handle larger inputs. floatType
- Possibles values are:
LM_WRAPPER LM_PROVED LM_HEURISTIC LM_FAST FT_DEFAULT yes yes
same as FT_MPFRyes
same as FT_DPEyes
same as FT_DOUBLEFT_DOUBLE no yes yes yes FT_DD no yes yes no FT_QD no yes yes no FT_DPE no yes yes no FT_MPFR no yes yes no 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_VERBOSE Displays information on stderr. LLL_EARLY_RED Enables early reduction. This might be faster on (nearly) lower triangular matrices. Currently, this flag is not compatible with the proved method. LLL_SIEGEL Uses Siegel condition instead of Lovász condition.
Return value:
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)Even if an error occurs, it is guaranteed that
RED_SUCCESS Success. RED_BABAI_FAILURE Error. RED_LLL_FAILURE Error: infinite loop in LLL. Any other value Error. b
remains a basis of the same lattice.
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.
int bkzReduction(IntMatrix& b, int blockSize, int flags = BKZ_DEFAULT)
BKZ-reduces a basis of Integers. Parameters:
Return value:
| ||||||||||||||||||||
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; }; Return value: Same as above. |
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
Return value:
|
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 stores floating-point numbers. This template provides a uniform interface for doing floating-point computations with several underlying types (double, dpe_t, dd, qd 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;
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 stores a reference to a row of a Matrix. It supports a subset of operations available on vectors.
Methods:
template<class T> ostream& operator<<(ostream& os, const MatrixRow<T>& mr) Prints mr on stream os. |
Base class: Matrix<Z_NR<ZT>>
Matrix of integers. Same constructors as Matrix.
Base class: Matrix<FP_NR<FT>>
Matrix of floating-point nubmers. Same constructors as Matrix.
1. Reduction
./latticegen r 10 1000 | ./fplll
2. Fileinput for Reduction
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
Current developer:
Martin Albrecht, martinralbrecht@googlemail.com
Damien Stehle, damien.stehle@gmail.com
Former developers:
David Cade, david.cade@ens.fr
Xavier Pujol, xavier.pujol@ens-lyon.org
@unpublished{fplll,
Note = {Available at \url{http://perso.ens-lyon.fr/damien.stehle}},
Title = {{fplll-4.0}, a floating-point {LLL} implementation},
Author = {Albrecht, M. and Cad{\'e}, D. and Pujol, X. and Stehl{\'e}, D.}
}
Patrick Pelissier and Paul Zimmermann for dpe.
David H. Bailey for QD.
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 will be announced at the URL:
http://perso.ens-lyon.fr/damien.stehle/fplll/
Bug reports may be sent at:
damien.stehle@gmail.com
or create an issue.