fplll - Man Page
fplll – does LLL, BKZ, HKZ or SVP on a matrix
fplll [options] [file]
fplll(1) does LLL, BKZ, HKZ or SVP on a matrix (considered as a set of row vectors) given in stdin or in a file as parameter.
- -a [lll|bkz|hkz|svp|sdb|sld|cvp]
lll: LLL-reduce the input matrix (default)
bkz: BKZ-reduce the input matrix
hkz: HKZ-reduce the input matrix
svp: compute a shortest non-zero vector of the lattice
sdb: reduce the input matrix using the self dual BKZ variant
sld: slide reduce the input matrix
cvp: compute the vector in the input lattice closest to an input vector
hlll: HLLL-reduce the input matrix
Enable verbose mode
Does not apply initial LLL-reduction. In the case of bkz, hkz and svp, by default, the input basis is LLL-reduced before anything else. This option allows to remove that initial LLL-reduction (note that other calls to LLL-reduction may occur during the execution). In the case of hlll, verify if the input basis is HLLL-reduced.
Options for Lll-Reduction
With the wrapper or the proved version, it is guaranteed that the basis is LLL-reduced with δ'=2×δ-1 and η'=2×η-1/2. For instance, with the default options, it is guaranteed that the basis is (0.98,0.52)-LLL-reduced.
- -d delta, -delta delta
- -e eta, -eta eta
θ (default=0.51). See P. Q. Nguyen and D. Stehle. An LLL Algorithm with Quadratic Complexity. SIAM J. Comput. 39(3): 874–903 (2009) for the definition of (δ,η)-LLL-reduced bases. -l lovasz If lovasz != 0, Lovasz’)s condition. Otherwise, Siegel’)s condition (default: Lovasz). See A. Akhavi. Random lattices, threshold phenomena and efficient reduction algorithms. Theor. Comput. Sci. 287(2): 359–385 (2002) for the definition of Siegel condition.
- -f [mpfr|dd|qd|dp|double|longdouble]
Floating-point type in LLL.
mpfr: Sets the floating-point type to MPFR (default if -m proved).
dd: Sets the floating-point type to double-double.
qd: Sets the floating-point type to quad-double.
dpe: Sets the floating-point type to DPE (default if -m heuristic).
double: Sets the floating-point type to double (default if -m fast).
longdouble: Sets the floating-point type to long double.
- -p precision
Precision of the floating-point arithmetic, works only with -f mpfr.
- -z [mpz|int|long|double]
Integer type in LLL
mpz: Sets the integer type to mpz, the integer type of GMP (default).
int: Sets the integer type to int.
long: Same as int.
double: Sets the integer type to double.
- -m [wrapper|fast|heuristic|proved]
wrapper: Uses the wrapper (default if -z mpz).
fast: Uses the fast method, works only with -f double.
heuristic: Uses the heuristic method.
proved: Uses the proved version of the algorithm.
Enable early reduction.
Options for Bkz-Reduction
- -b block_size
Size of BKZ blocks, mandatory, between 2 and the number of vectors. -f float_type Same as for LLL (-p is required if -f mpfr).
- -bkzmaxloops loops
Maximum number of full loop iterations.
- -bkzmaxtime time
Stops after time seconds (up to completion of the current loop iteration).
Stops when the average slope of the log ||b_i*||’)s does not decrease fast enough.
Without any of the last three options, BKZ runs until no block has been updated for a full loop iteration.
- -s filename.json
Use strategies for preprocessing and pruning parameter (strategies/default.json provided). Experimental.
- -bkzghbound factor
Multiplies the Gaussian heuristic by factor (of float type) to set the enumeration radius of the SVP calls.
Restricts the LLL call before considering a block to vector indices within that block.
- -bkzdumpgso file_name
Dumps the log of the Gram-Schmidt vectors (log ||b_i*||’)s) in specified file
- -of [b|bk|c|s|t|u|uk|v|vk]
Output formats. A combination of these option is allowed (e.g., -of bkut).
(empty; -of ): Prints new line (if -a [lll|bkz]).
b: Prints the basis (if -a [lll|bkz], this value by default).
bk: Prints the basis (if -a [lll|bkz], format compatible with sage).
c: Prints the closest vector (if -a cvp, this value by default).
s: Prints the closest vector (if -a svp, this value by default).
s: Prints status (if -a [lll|bkz|cvp|svp]).
u: Prints unimodular matrix (if -a [lll|bkz]).
uk: Prints unimodular matrix (if -a [lll|bkz], format compatible with sage).
u: Prints inverse of u (if -a lll).
uk: Prints inverse of u (if -a lll, format compatible with sage).
Options for Hlll-Reduction
- -t theta, -theta theta
θ (default=0.001). See I. Morel, D. Stehle and G. Villard. H-LLL: using Householder inside LLL. ISSAC 2009: 271–278 for the definition of (δ,η,θ)-HLLL-reduced bases.
- -c c
An arbitrary double constant > 0 for HLLL during the size-reduction; only used if fplll(1) is compiled with -DHOUSEHOLDER_USE_SIZE_REDUCTION_TEST (default=0.1)