plll
1.0

Provides an interface to the lattice reduction algorithms of the plll
library.
More...
#include <plll.hpp>
Classes  
class  GramSchmidtInformer 
Provides information on the GramSchmidt coefficients. More...  
struct  Statistics 
Describes lattice basis reduction statistics. More...  
class  stop_enumeration 
This exception should be thrown by callback functions to stop enumeration and return the currently found vector to the caller. More...  
class  stop_reduction 
This exception should be thrown by callback functions to stop reduction and return the current state of reduction to the caller. More...  
Public Types  
Configuration enums.  
enum  Arithmetic { A_Rational, A_Real, A_LongDouble, A_Double, A_DoubleDouble, A_QuadDouble, A_Default = A_LongDouble } 
Specifies which arithmetic to use for GramSchmidt orthogonalization. More...  
enum  Integers { I_Auto, I_ArbitraryPrecision, I_LongInt, I_Default = I_Auto } 
Specifies which arithmetic to use for integer operations. More...  
enum  GramSchmidt { G_Classic, G_ClassicInteger, G_Givens, G_NumStable, G_Default = G_NumStable } 
Specifies which GramSchmidt orthogonalization is used. More...  
enum  Transform { T_Normal, T_Inverse } 
Specifies which transformation matrix is computed. More...  
enum  LLLMode { LLL_Classic, LLL_Unprojected, LLL_Siegel, LLL_Default = LLL_Classic } 
Specifies which LLL condition is used. More...  
enum  BKZMode { BKZ_SchnorrEuchner, BKZ_Simplified, BKZ_HanrotPujolStehleHKZ, BKZ_HanrotPujolStehleSVP, BKZ_PrimalDual, BKZ_SlideReduction, BKZ_ImprovedSlideReduction, BKZ_ImprovedSlideReduction2, BKZ_ImprovedSlideReduction3, BKZ_SemiBlock2k, BKZ_SamplingReduction , BKZ_Default = BKZ_SchnorrEuchner } 
Specifies which BKZ algorithm is used. More...  
enum  SVPMode { SVP_KannanSchnorrEuchner, SVP_ParallelKannanSchnorrEuchner, SVP_SchnorrFast, SVP_VoronoiCellSVP, SVP_ListSieve, SVP_ListSieveBirthday, SVP_GaussSieve, SVP_Default = SVP_ParallelKannanSchnorrEuchner } 
Specifies which SVP solver is used. More...  
enum  DIMethod { DI_None, DI_Classic, DI_MinimizePotential1, DI_MinimizePotential2, DI_Default = DI_None } 
Specifies which Deep Insertion mode is used. More...  
enum  DIChoice { DIC_First, DIC_Block, DIC_FirstBlock, DIC_All, DIC_Default = DIC_All } 
Specifies which Deep Insertion choice is used. More...  
enum  DIMode { DIM_BeforeSR, DIM_AfterSR, DIM_Both, DIM_Default = DIM_Both } 
Specifies which Deep Insertions mode is used. More...  
enum  VerboseOutputLevel { VOL_None, VOL_Warnings, VOL_Informative, VOL_Full } 
Specifies the verbosity output level. More...  
enum  VerboseLevel { VL_Error, VL_Warning, VL_Information, VL_Chatter } 
Specifies a warning level for a specific output message. More...  
Callback function types.  
typedef boost::function< void(const linalg::math_matrix < arithmetic::Integer > &)>  CallbackFunction 
A generic callback function. More...  
typedef boost::function< void(const linalg::math_matrix < arithmetic::NInt< long int > > &)>  CallbackFunction_LI 
A generic callback function for long int lattices. More...  
typedef boost::function< void(const linalg::math_matrix < arithmetic::Integer > &, unsigned, const arithmetic::Integer &)>  MinCallbackFunction 
A callback function for newly found shortest vectors. More...  
typedef boost::function< void(const linalg::math_matrix < arithmetic::NInt< long int > > &, unsigned, const arithmetic::NInt< long int > &)>  MinCallbackFunction_LI 
A callback function for newly found shortest vectors for long int lattices. More...  
typedef boost::function< void(const linalg::math_matrix < arithmetic::Integer > &basis, int p, const linalg::math_rowvector < arithmetic::Integer > &vec)>  EnumCallbackFunction 
A callback function for newly found shortest vectors during enumerations, or more generally SVP solving. More...  
typedef boost::function< void(const linalg::math_matrix < arithmetic::NInt< long int > > &basis, int p, const linalg::math_rowvector < arithmetic::NInt< long int > > &vec)>  EnumCallbackFunction_LI 
A callback function for newly found shortest vectors during enumerations, or more generally SVP solving. This callback is for long int lattices. More...  
typedef boost::function< bool(const linalg::math_matrix < arithmetic::Integer > &, arithmetic::RealContext &, arithmetic::Real &T)>  AnnealCallbackFunction 
A callback function for Simulated Annealing. More...  
typedef boost::function< bool(const linalg::math_matrix < arithmetic::Integer > &, int k, arithmetic::RealContext &, arithmetic::RandomNumberGenerator &, arithmetic::Real &T, GramSchmidtInformer *)>  LLL_AnnealFunction 
A annealing function for LLL. More...  
typedef boost::function< bool(const linalg::math_matrix < arithmetic::Integer > &, int k, int windowsize, linalg::math_rowvector < arithmetic::Integer > &lincomb, arithmetic::RealContext &, arithmetic::RandomNumberGenerator &, arithmetic::Real &T, GramSchmidtInformer *)>  BKZ_AnnealFunction 
A annealing function for BKZ. More...  
typedef boost::function< void(VerboseLevel, const std::string &)>  VerboseFunction 
A verbose output callback function. More...  
Public Member Functions  
LatticeReduction ()  
Creates a default LatticeReduction object with default settings.  
LatticeReduction (const linalg::math_matrix< arithmetic::Integer > &lattice)  
Creates a LatticeReduction object with default settings, and sets the lattice basis to the given matrix. More...  
template<typename IType >  
LatticeReduction (const linalg::math_matrix< arithmetic::NInt< IType > > &lattice)  
Creates a LatticeReduction object with default settings, and sets the lattice basis to the given matrix. More...  
~LatticeReduction ()  
Destroys the LatticeReduction object.  
Lattice setting and retrieving functions.  
void  setLattice (const linalg::math_matrix< arithmetic::Integer > &lattice) 
Sets the current lattice of the LatticeReduction object to the lattice given by the current matrix. More...  
template<typename IType >  
void  setLattice (const linalg::math_matrix< arithmetic::NInt< IType > > &lattice) 
Sets the current lattice of the LatticeReduction object to the lattice given by the current matrix. More...  
const linalg::math_matrix < arithmetic::Integer > &  getLattice () const 
Returns the current lattice generating set as a matrix. More...  
Lattice information functions.  
unsigned  rank () const 
Returns the current rank, i.e. the number of generating vectors. More...  
unsigned  dimension () const 
Returns the dimension of the ambient space in which the lattice exists. More...  
Arithmetic configuration functions.  
void  setArithmetic (Arithmetic) 
Sets which arithmetic will be used for GramSchmidt orthogonalizations. More...  
Arithmetic  getArithmetic () const 
Returns the currently set arithmetic for GramSchmidt orthogonalizations. More...  
bool  ensurePrecision (unsigned long) 
Ensures a minimal floating point precision (if possible). More...  
void  setIntegers (Integers) 
Sets which integer arithmetic will be used for all lattice operations. More...  
Integers  getIntegers () const 
Returns the currently set integer arithmetic. More...  
GramSchmidt orthogonalization configuration functions.  
void  setGramSchmidt (GramSchmidt) 
Sets which GramSchmidt orthogonalization method will be used. More...  
void  setGramSchmidtRestart (bool) 
Sets that the current GramSchmidt method should use restarts. More...  
GramSchmidt  getGramSchmidt () const 
Returns the currently used GramSchmidt orthogonalization method. More...  
bool  getGramSchmidtRestart () const 
Returns whether restarts are used for the current GramSchmidt orthogonalization method. More...  
GramSchmidt orthogonalization querying functions.  
void  forceGSRebuild (bool makeSureAllComputed=false) 
Forces the GramSchmidt coefficients to be rebuild. More...  
double  getGSCoefficientD (unsigned, unsigned) const 
Returns the (i, j) GramSchmidt coefficient as a double . More...  
long double  getGSCoefficientLD (unsigned, unsigned) const 
Returns the (i, j) GramSchmidt coefficient as a long double . More...  
arithmetic::Real  getGSCoefficientR (unsigned, unsigned) const 
Returns the (i, j) GramSchmidt coefficient as a arithmetic::Real number. More...  
arithmetic::Real  getGSCoefficientR (unsigned, unsigned, const arithmetic::RealContext &) const 
Returns the (i, j) GramSchmidt coefficient as a arithmetic::Real number. More...  
double  getGSSqNormD (unsigned) const 
Returns the squared norm of the ith GramSchmidt orthogonalized basis vector as a double . More...  
long double  getGSSqNormLD (unsigned) const 
Returns the squared norm of the ith GramSchmidt orthogonalized basis vector as a long double . More...  
arithmetic::Real  getGSSqNormR (unsigned) const 
Returns the squared norm of the ith GramSchmidt orthogonalized basis vector as a arithmetic::Real number. More...  
arithmetic::Real  getGSSqNormR (unsigned, const arithmetic::RealContext &) const 
Returns the squared norm of the ith GramSchmidt orthogonalized basis vector as a arithmetic::Real number. More...  
Modifying functions.  
void  modFlip (unsigned) 
Flips the signs of the given basis vector. More...  
void  modSwap (unsigned, unsigned) 
Swaps two given basis vectors. More...  
void  modAdd (unsigned i, unsigned j, const arithmetic::Integer &m) 
Adds m times the i th basis vector to the j th basis vector. More...  
Transformation recording related functions.  
void  enableTransform (Transform=T_Normal) 
Enables that from this point on, a transformation matrix is recorded. More...  
void  disableTransform () 
Disables recording of a transformation matrix. More...  
bool  isTransformationRecorded () const 
Queries whether a transformation matrix is recorded. More...  
Transform  getTransformationMode () const 
Queries whether transformation matrix (normal or inverse) is recorded. More...  
const linalg::math_matrix < arithmetic::Integer > *  getTransformation () const 
Queries the current transformation matrix. More...  
SVP mode related functions.  
void  setSVPMode (SVPMode) 
Sets the current SVP solver.  
SVPMode  getSVPMode () const 
Retrieves the current SVP solver.  
Multithreading related functions.  
void  setMaximalCoreUsage (unsigned) 
Setups the maximal number of cores which will be used by the plll library. More...  
unsigned  getMaximalCoreUsage () 
Returns the current maximal number of cores used. More...  
Callback related functions.  
void  setCallbackFunction (const CallbackFunction &, const CallbackFunction_LI &=CallbackFunction_LI()) 
Sets a callback function. More...  
void  setCallbackFunction (const CallbackFunction_LI &) 
Sets a callback function. More...  
void  setCallbackInterval (double=60.0 *5.0) 
Sets the callback interval for the callback function. More...  
std::pair< CallbackFunction, CallbackFunction_LI >  getCallbackFunction () const 
Retrieves the currently set callback function. More...  
double  getCallbackInterval () const 
Retrieves the current (minimal) callback interval. More...  
void  setMinCallbackFunction (const MinCallbackFunction &, const MinCallbackFunction_LI &=MinCallbackFunction_LI()) 
Sets a minimum callback function which will be called as soon as a new shortest vector is found during reduction. More...  
void  setMinCallbackFunction (const MinCallbackFunction_LI &) 
Sets a minimum callback function which will be called as soon as a new shortest vector is found during reduction. More...  
std::pair< MinCallbackFunction, MinCallbackFunction_LI >  getMinCallbackFunction () const 
Retrieves the currently set minimum callback function. More...  
void  setEnumCallbackFunction (const EnumCallbackFunction &, const EnumCallbackFunction_LI &=EnumCallbackFunction_LI()) 
Sets a enumeration callback function which will be used if a new shortest vector is found during an enumeration. More...  
void  setEnumCallbackFunction (const EnumCallbackFunction_LI &) 
Sets a enumeration callback function which will be used if a new shortest vector is found during an enumeration. More...  
std::pair < EnumCallbackFunction, EnumCallbackFunction_LI >  getEnumCallbackFunction () 
Retrieves the current enumeration callback function. More...  
Simulated Annealing related functions.  
void  setDefaultAnnealing () 
Sets the default annealing functions. More...  
void  setDefaultAnnealingLLL () 
Sets the defalut LLL annealing function. More...  
void  setDefaultAnnealingBKZ () 
Sets the defalut BKZ annealing function. More...  
void  setAnnealing (const AnnealCallbackFunction &, const LLL_AnnealFunction &, const BKZ_AnnealFunction &) 
Sets annealing functions for both LLL and BKZ.  
void  setAnnealingLLL (const AnnealCallbackFunction &, const LLL_AnnealFunction &) 
Sets annealing functions for LLL. More...  
void  setAnnealingBKZ (const AnnealCallbackFunction &, const BKZ_AnnealFunction &) 
Sets annealing functions for BKZ. More...  
void  disableAnnealing () 
Disable annealing for both LLL and BKZ. More...  
void  disableAnnealingLLL () 
Disable annealing for LLL. More...  
void  disableAnnealingBKZ () 
Disable annealing for LLL. More...  
bool  isAnnealingLLLEnabled () const 
Tests whether annealing for LLL is enabled.  
bool  isAnnealingBKZEnabled () const 
Tests whether annealing for BKZ is enabled.  
Deep Insertions related functions.  
void  setDeepInsertionMethod (DIMethod, DIMode=DIM_Default) 
Sets the Deep Insertions method and optionally also the mode. More...  
void  setDeepInsertionMode (DIMode) 
Sets the Deep Insertions mode. More...  
void  setDeepInsertionChoice (DIChoice, unsigned=1) 
Sets the Deep Insertion choice and block size, which by default is 1. More...  
DIMethod  getDeepInsertionMethod () const 
Retrieves the current Deep Insertions method. More...  
DIMode  getDeepInsertionMode () const 
Retrieves the current Deep Insertions mode. More...  
DIChoice  getDeepInsertionChoice () const 
Retrieves the current Deep Insertions choice. More...  
unsigned  getDeepInsertionBlocksize () const 
Retrieves the current Deep Insertions choice block size parameter. More...  
Range related functions.  
void  setRange (unsigned begin, unsigned end=std::numeric_limits< unsigned >::max()) 
Retricts all algorithms to the range [begin, end]. More...  
std::pair< unsigned, unsigned >  getRange () const 
Retrieves the current range. More...  
Lattice functions.  
void  sort (bool projected=false) 
Sorts the vectors by their norm. More...  
void  sizereduction () 
Applies only size reduction to the vectors. More...  
void  lll (double alpha=0.99, LLLMode mode=LLL_Classic) 
Applies LLL with given reduction parameter alpha ( ) and mode mode . More...  
void  bkz (double alpha=0.99, unsigned blocksize=20, BKZMode mode=BKZ_SchnorrEuchner) 
Applies BKZ (or one of its variants) with given reduction parameter alpha ( ), block size blocksize and mode mode . More...  
void  hkz (bool dual=false) 
Computes a HermiteKorkineZolotarev reduced basis. More...  
void  svp (bool make_basis=true, bool extreme=false, bool dual=false) 
Computes a shortest vector of the lattice and inserts it at the beginning. More...  
Lattice reduction testing functions.  
bool  isSizeReduced () const 
Tests whether the given lattice is size reduced.  
bool  isLLLBasis (double alpha=0.99, LLLMode mode=LLL_Classic) const 
Tests whether the given lattice basis is LLL reduced with respect to the given reduction parameter alpha ( ) and mode mode . More...  
bool  isBKZBasis (double alpha=0.99, unsigned blocksize=20, BKZMode mode=BKZ_SchnorrEuchner) const 
Tests whether the given lattice basis is BKZ reduced with respect to the given reduction parameter alpha ( ), the given block size blocksize and mode mode . More...  
bool  isHKZBasis (bool dual=false) const 
Tests whether the given lattice basis (or its reversed dual, in case dual is true ) is HKZ reduced. More...  
bool  isSVPBasis (bool dual=false) const 
Tests whether the given lattice basis (or its reversed dual, in case dual is true ) has a shortest vector at the first index. More...  
Statistics related functions.  
const Statistics &  getStatistics () const 
Retrieves the current statistics object.  
void  resetStatistics () 
Resets the current statistics object.  
Verbosity related functions.  
void  setVerbose (VerboseOutputLevel level, const VerboseFunction &=0) 
Sets the verbose output level to level . More...  
VerboseOutputLevel  getVerboseOutputLevel () 
Retrieves the current verbose output level. More...  
const VerboseFunction &  getVerboseFunction () 
Retrieves the current verbose output function. More...  
Provides an interface to the lattice reduction algorithms of the plll
library.
This class provides an interface to all lattice reduction algorithms of the plll
library. It is possible to configure the algorithms using the interface and execute them. The lattice can be set and retrieved, and also callback functions can be set up.
typedef boost::function<bool(const linalg::math_matrix<arithmetic::Integer> &, arithmetic::RealContext &, arithmetic::Real & T)> plll::LatticeReduction::AnnealCallbackFunction 
A callback function for Simulated Annealing.
It will be given the current basis and current temperature. It should modify the temperature T
, and return true
if another annealing round should be started or false
if the algorithm should terminate.
If the given temperature T
was negative when this function was called, then this call was done before the first annealing round and after the first LLL reduction.
typedef boost::function<bool (const linalg::math_matrix<arithmetic::Integer> &, int k, int windowsize, linalg::math_rowvector<arithmetic::Integer> & lincomb, arithmetic::RealContext &, arithmetic::RandomNumberGenerator &, arithmetic::Real & T, GramSchmidtInformer *)> plll::LatticeReduction::BKZ_AnnealFunction 
A annealing function for BKZ.
It receives the current basis, the current index, the current window size, a linear combination comb
of the basis vectors k
, k+1
, ... of the currently shortest vector found (by SVP solving), a arithmetic::Real
context, a random number generator, the current temparature T
, as well as a GramSchmidt informer object.
It can return true
to indicate that the vector given by the linear combination lincomb
should be inserted, or false
to not insert a vector. Note that the function can freely modify the linear combination.
typedef boost::function<void(const linalg::math_matrix<arithmetic::Integer> &)> plll::LatticeReduction::CallbackFunction 
A generic callback function.
The current lattice will be passed as an argument and shall not be modified. The function can throw an exception of type stop_reduction
to abort reduction.
typedef boost::function<void(const linalg::math_matrix<arithmetic::NInt<long int> > &)> plll::LatticeReduction::CallbackFunction_LI 
A generic callback function for long int
lattices.
The current lattice will be passed as an argument and shall not be modified. The function can throw an exception of type stop_reduction
to abort reduction.
typedef boost::function<void(const linalg::math_matrix<arithmetic::Integer> & basis, int p, const linalg::math_rowvector<arithmetic::Integer> & vec)> plll::LatticeReduction::EnumCallbackFunction 
A callback function for newly found shortest vectors during enumerations, or more generally SVP solving.
The basis is given as an argument together with an index and a vector with coefficients, such that the shortest vector is a linear combination of the basis vectors p
, p + 1
, ... with the coefficients given in vec
.
The function can throw an exception of type stop_enumeration
to stop enumeration (and return the currently found vector), or of type stop_reduction
to abort reduction.
typedef boost::function<void(const linalg::math_matrix<arithmetic::NInt<long int> > & basis, int p, const linalg::math_rowvector<arithmetic::NInt<long int> > & vec)> plll::LatticeReduction::EnumCallbackFunction_LI 
A callback function for newly found shortest vectors during enumerations, or more generally SVP solving. This callback is for long int
lattices.
The basis is given as an argument together with an index and a vector with coefficients, such that the shortest vector is a linear combination of the basis vectors p
, p + 1
, ... with the coefficients given in vec
.
The function can throw an exception of type stop_enumeration
to stop enumeration (and return the currently found vector), or of type stop_reduction
to abort reduction.
typedef boost::function<bool(const linalg::math_matrix<arithmetic::Integer> &, int k, arithmetic::RealContext &, arithmetic::RandomNumberGenerator &, arithmetic::Real & T, GramSchmidtInformer *)> plll::LatticeReduction::LLL_AnnealFunction 
A annealing function for LLL.
It receives the current basis, the current index, a arithmetic::Real
context, a random number generator, the current temparature T
, as well as a GramSchmidt informer object. It can return true
to indicate that basis vector k
should be swapped with basis vector k  1
, or false
to indicate that nothing should be done.
typedef boost::function<void(const linalg::math_matrix<arithmetic::Integer> &, unsigned, const arithmetic::Integer &)> plll::LatticeReduction::MinCallbackFunction 
A callback function for newly found shortest vectors.
The basis is given as an argument together with an index to the shortest vector in that base (encourntered so far). The function can throw an exception of type stop_reduction
to abort reduction.
typedef boost::function<void(const linalg::math_matrix<arithmetic::NInt<long int> > &, unsigned, const arithmetic::NInt<long int> &)> plll::LatticeReduction::MinCallbackFunction_LI 
A callback function for newly found shortest vectors for long int
lattices.
The basis is given as an argument together with an index to the shortest vector in that base (encourntered so far). The function can throw an exception of type stop_reduction
to abort reduction.
typedef boost::function<void(VerboseLevel, const std::string &)> plll::LatticeReduction::VerboseFunction 
A verbose output callback function.
Given a verbose level (of type VerboseLevel
) and a message, should somehow inform the caller about the content of the message.
Specifies which arithmetic to use for GramSchmidt orthogonalization.
Specifies which arithmetic should be used by the plll
library for GramSchmidt orthogonalizations. The choice of arithmetics might vary depending on the platform, but except for "Fast Compile" scenarios, at least rational, real, long double and double arithmetic is supported.
Enumerator  

A_Rational 
Rational arithmetic, i.e. a pair of 
A_Real 
MPFRbased 
A_LongDouble 
The system's native This is the default setting for 
A_Double 
The system's native 
A_DoubleDouble 
Uses two native Support for this arithmetic depends on the libqd library by Yozo Hida. It apparently does not work on UltraSparc CPUs. 
A_QuadDouble 
Uses four native Support for this arithmetic depends on the libqd library by Yozo Hida. It apparently does not work on UltraSparc CPUs. 
A_Default 
Alias for the default arithmetic, i.e. for 
Specifies which BKZ algorithm is used.
Specifies which BKZ algorithm is used by the plll
library. Note that BKZ is somewhat misleading here, since most of these algorithms are known under completely different names. What all these algorithms have in common that they compute KorkineZolotarev or at least SVP bases for certain blocks of (projected) basis vectors, or their dual.
Enumerator  

BKZ_SchnorrEuchner 
The classical SchnorrEuchner BKZ algorithm, as described in Section 6 of [15] by C.P. Schnorr and M. Euchner. This is the default setting for

BKZ_Simplified 
A simplified version of the BKZ algorithm, as described by G. Hanrot, X. Pujol and D. Stehle in [8].

BKZ_HanrotPujolStehleHKZ 
A "Terminating BKZ" variant of the simplified version of the BKZ algorithm, as described by G. Hanrot, X. Pujol and D. Stehle in [8]. This version computes HermiteKorkineZolotarev (HKZ) bases for every block.

BKZ_HanrotPujolStehleSVP 
A "Terminating BKZ" variant of the simplified version of the BKZ algorithm, as described by G. Hanrot, X. Pujol and D. Stehle in [8]. This version computes Shortest Vector (SVP) bases for every block.

BKZ_PrimalDual 
The primaldual BKZ algorithm by H. Koy, as described in Section 3 of [17]

BKZ_SlideReduction 
The slide reduction algorithm, as described by N. Gama and P. Q. Nguyen in [5].

BKZ_ImprovedSlideReduction 
A improved and accelerated version of Slide Reduction, as described in [18] by C.P. Schnorr (Section 3).

BKZ_ImprovedSlideReduction2 
A improved and accelerated version of Slide Reduction, as described in [18] by C.P. Schnorr (Section 3). This variant uses a larger dual SVP enumeration and a single primal SVP enumeration.

BKZ_ImprovedSlideReduction3 
A improved and accelerated version of Slide Reduction, as described in [18] by C.P. Schnorr (Section 3). This variant uses a single larger primal SVP enumeration and one dual SVP enumeration.

BKZ_SemiBlock2k 
The semi block 2kreduction, as described by C.P. Schnorr in Section 2 of [17].

BKZ_SamplingReduction 
The Sampling Reduction, as described by J. A. Buchmann and C. Ludwig in [2].

BKZ_Default 
Alias for the default BKZ variant, i.e. for 
Specifies which Deep Insertion choice is used.
Specifies which vectors are considered for Deep Insertions by the plll
library.
Specifies which Deep Insertion mode is used.
Specifies which Deep Insertion mode is used by the plll
library. Note that Deep Insertions are not supported directly by all LLL and BKZ algorithms, but will be used by recursive LLL and BKZ calls.
The idea of Deep Insertions is that while usual LLL only swaps adjacent vectors, Deep Insertions also compares the current vectors with more previous vectors to decide where it could be inserted.
Enumerator  

DI_None 
Disable Deep Insertions. This is the default setting for 
DI_Classic 
Uses classic Deep Insertions as described by C.P. Schnorr and M. Euchner in [15]. 
DI_MinimizePotential1 
Uses potential minimizing Deep Insertions (PotLLL) as described by F. Fontein, M. Schneider and U. Wagner in [3] and [4]. 
DI_MinimizePotential2 
Uses a variant of the potential minimizing Deep Insertions (PotLLL2) as described by F. Fontein, M. Schneider and U. Wagner in [4]. See "PotLLL2" in Section 3.1. 
DI_Default 
Alias for the default Deep Insertions mode, i.e. for 
Specifies which Deep Insertions mode is used.
Specifies which kind Deep Insertions mode is used, i.e. whether the insertions are done before and/or after size reduction.
Specifies which GramSchmidt orthogonalization is used.
Specifies which GramSchmidt orthogonalization should be used by the plll
library. Always available are classic GS, classic GS with integer arithmetic, and numerically stable GS. For floatingpoint arithmetic, also Givens rotations can be used for GS orthogonalization.
Enumerator  

G_Classic 
"Classical" GramSchmidt orthogonalization. Uses formulae to update GramSchmidt coefficients on swaps, transformations etc., which can introduce additional error with floating point arithmetic. 
G_ClassicInteger 
Integerbased GramSchmidt orthogonalization. Internally uses arbitrary precision integers respectively rational numbers. Slow, but always accurate. 
G_Givens 
Uses Givens rotations to compute GramSchmidt orthogonalization. Only available for floatingpoint arithmetic (i.e. everything but 
G_NumStable 
Uses numerically stable GramSchmidt orthogonalization as described by P. Q. Nguyen and D. Stehle in [12]. This arithmetic is more resilient against approximation errors than other approaches. Instead of updating GS coefficients for swaps, transformations etc., these are recomputed to ensure maximal precision. This is the default setting for 
G_Default 
Alias for the default GramSchmidt orthogonalization, i.e. for 
Specifies which arithmetic to use for integer operations.
Specifies which arithmetic should be used by the plll
library for integer operations. Besides GMPbased arbitrary precision integers, it also provides support for systemdependent long int
integers and for an automatic decision mode which uses arbitrary precision integers if necessary and system integers otherwise.
Enumerator  

I_Auto 
Decides based on the input whether to use arbitrary precision integer arithmetic or systemdependent integer arithmetic. This decision is analyzed from time to time, and arithmetic is changed when necessary. This is the default setting for 
I_ArbitraryPrecision 
Uses 
I_LongInt 
Uses 
I_Default 
Alias for the default integer arithmetic, i.e. for 
Specifies which LLL condition is used.
Specifies which LLL condition is used by the plll
library. One can choose between the original condition introduced by Lenstra, Lenstra and LovĂˇsz, a "unprojected" variant comparing the norms in the ambient space, and the Siegel condition.
Enumerator  

LLL_Classic 
The original condition by Lenstra, Lenstra and LovĂˇsz, called the LovĂˇsz condition, which compares the projected lengths of two adjacent vectors, where the vectors are projected onto the orthogonal complement of all previous vectors. In terms of the GramSchmidt orthogonalization of the basis , this condition can be expressed as . This is the default setting for

LLL_Unprojected 
A simpler condition, which compares the unprojected lengths of two adjacent. In terms of the basis , this condition can be expressed as .

LLL_Siegel 
A simpler condition, which allows to prove the same bounds on the output quality, called the Siegel condition. Note that the LovĂˇsz condition implies the Siegel condition. In terms of the GramSchmidt orthogonalization of the basis , this condition can be expressed as .

LLL_Default 
Alias for the default LLL condition, i.e. for 
Specifies which SVP solver is used.
Specifies which SVP solver is used by the plll
library. For small enough dimensions, always a simple (but efficient) enumeration variant is used, except for the highest level reduction, where always the selected solver is used.
Enumerator  

SVP_KannanSchnorrEuchner 
A variant of the KannanSchnorrEuchner enumeration algorithm [15] with various improvements; see, for example, Appendix B of [7]. 
SVP_ParallelKannanSchnorrEuchner 
A parallelized variant of the KannanSchnorrEuchner enumeration algorithm [15] with various improvements. The parallelization uses multiple cores. There is almost no communication between cores, except if a shorter vector is found by one, or if one core runs out of work and asks others to split their workload. This is the default setting for 
SVP_SchnorrFast 
A (single threaded) version of Schnorr's new SVP solver, as described in [19] by C.P. Schnorr. This implementation is still experimental.

SVP_VoronoiCellSVP 
A deterministic SVP solver which first computes the voronoi cell of the lattice. While being deterministic and asymptotically faster than enumeration, in practice this algorithm is only usable for very low dimensions, say at most 10, where enumeration is still much faster. This algorithm was described by D. Micciancio and P. Voulgaris in [11].

SVP_ListSieve 
The probabilistic list sieve SVP solver. It was described by D. Micciancio and P. Voulgaris in Section 3.1 of [10]. This implementation is still experimental.

SVP_ListSieveBirthday 
The probabilistic list sieve (with birthday paradox exploitation) SVP solver. It was described by X. Pujol and D. Stehle in the paper [14]. This implementation is still experimental.

SVP_GaussSieve 
The probabilistic Gauss sieve SVP solver. It was described by D. Micciancio and P. Voulgaris in Section 3.2 of [10]. Our implementation is similar to one by P. Voulgaris.

SVP_Default 
Alias for the default SVP solver, i.e. for 
Specifies which transformation matrix is computed.
Specifies which kind of transformation matrix is computed by the plll
library, if computation of transformation matrices is requested.
Specifies a warning level for a specific output message.
Specifies the level of a specific output message. This is used to inform a VerboseFunction
callback function which level the given message has.
Specifies the verbosity output level.
Specifies the verbosity output level of the plll
library. It can be configured between no output, and full output. Note that by outputting, it is meant that the specified VerboseFunction
is called (or its default, which uses std::cerr
).
Enumerator  

VOL_None 
Outputs nothing. 
VOL_Warnings 
Outputs only warnings and errors. 
VOL_Informative 
Outputs warnings, errors and informative messages. 
VOL_Full 
Outputs everything. 
plll::LatticeReduction::LatticeReduction  (  const linalg::math_matrix< arithmetic::Integer > &  lattice  ) 
Creates a LatticeReduction
object with default settings, and sets the lattice basis to the given matrix.
lattice  The matrix whose rows to take as a generating system for the lattice. 
plll::LatticeReduction::LatticeReduction  (  const linalg::math_matrix< arithmetic::NInt< IType > > &  lattice  ) 
Creates a LatticeReduction
object with default settings, and sets the lattice basis to the given matrix.
lattice  The matrix whose rows to take as a generating system for the lattice. 
IType  A native CPU integer type. Must be int , long int or long long . 
void plll::LatticeReduction::bkz  (  double  alpha = 0.99 , 
unsigned  blocksize = 20 , 

BKZMode  mode = BKZ_SchnorrEuchner 

) 
Applies BKZ (or one of its variants) with given reduction parameter alpha
( ), block size blocksize
and mode mode
.
By default, the reduction parameter is 0.99, the block size is 20 and the mode is BKZ_SchnorrEuchner
.
Note that often 0.99 completely suffices as a reduction parameter, and that the default alpha
used by Lenstra, Lenstra and LovĂˇsz is 0.75.
unsigned plll::LatticeReduction::dimension  (  )  const 
Returns the dimension of the ambient space in which the lattice exists.
When there is no linear dependence among the vectors, dimension()
is never less than rank()
.
void plll::LatticeReduction::disableAnnealing  (  ) 
Disable annealing for both LLL and BKZ.
void plll::LatticeReduction::disableAnnealingBKZ  (  ) 
Disable annealing for LLL.
void plll::LatticeReduction::disableAnnealingLLL  (  ) 
Disable annealing for LLL.
void plll::LatticeReduction::disableTransform  (  ) 
Disables recording of a transformation matrix.
Enables that from this point on, a transformation matrix is recorded.
The argument allows to chose which transformation matrix is created; by default, a normal one is created, such that if denotes the basis at this point, at a later point and the transformation matrix at that point, then .
bool plll::LatticeReduction::ensurePrecision  (  unsigned  long  ) 
Ensures a minimal floating point precision (if possible).
For variable precision floating point arithmetic (i.e. A_Real
), ensures that the given minimum precision is used. Returns true
if the precision can be set, or false
if it cannot.
void plll::LatticeReduction::forceGSRebuild  (  bool  makeSureAllComputed = false  ) 
Forces the GramSchmidt coefficients to be rebuild.
If the argument makeSureAllComputed
is set to true
, all GramSchmidt coefficients are build now and not when they are needed.
This can be called when no algorithm is currently running.
Arithmetic plll::LatticeReduction::getArithmetic  (  )  const 
Returns the currently set arithmetic for GramSchmidt orthogonalizations.
std::pair<CallbackFunction, CallbackFunction_LI> plll::LatticeReduction::getCallbackFunction  (  )  const 
Retrieves the currently set callback function.
double plll::LatticeReduction::getCallbackInterval  (  )  const 
Retrieves the current (minimal) callback interval.
unsigned plll::LatticeReduction::getDeepInsertionBlocksize  (  )  const 
Retrieves the current Deep Insertions choice block size parameter.
DIChoice plll::LatticeReduction::getDeepInsertionChoice  (  )  const 
Retrieves the current Deep Insertions choice.
DIMethod plll::LatticeReduction::getDeepInsertionMethod  (  )  const 
Retrieves the current Deep Insertions method.
DIMode plll::LatticeReduction::getDeepInsertionMode  (  )  const 
Retrieves the current Deep Insertions mode.
std::pair<EnumCallbackFunction, EnumCallbackFunction_LI> plll::LatticeReduction::getEnumCallbackFunction  (  ) 
Retrieves the current enumeration callback function.
GramSchmidt plll::LatticeReduction::getGramSchmidt  (  )  const 
Returns the currently used GramSchmidt orthogonalization method.
bool plll::LatticeReduction::getGramSchmidtRestart  (  )  const 
Returns whether restarts are used for the current GramSchmidt orthogonalization method.
double plll::LatticeReduction::getGSCoefficientD  (  unsigned  , 
unsigned  
)  const 
Returns the (i, j) GramSchmidt coefficient as a double
.
This can be called when no algorithm is currently running.
long double plll::LatticeReduction::getGSCoefficientLD  (  unsigned  , 
unsigned  
)  const 
Returns the (i, j) GramSchmidt coefficient as a long double
.
This can be called when no algorithm is currently running.
arithmetic::Real plll::LatticeReduction::getGSCoefficientR  (  unsigned  , 
unsigned  
)  const 
Returns the (i, j) GramSchmidt coefficient as a arithmetic::Real
number.
This can be called when no algorithm is currently running.
arithmetic::Real plll::LatticeReduction::getGSCoefficientR  (  unsigned  , 
unsigned  ,  
const arithmetic::RealContext &  
)  const 
Returns the (i, j) GramSchmidt coefficient as a arithmetic::Real
number.
This can be called when no algorithm is currently running. Uses the default arithmetic::RealContext
.
double plll::LatticeReduction::getGSSqNormD  (  unsigned  )  const 
Returns the squared norm of the ith GramSchmidt orthogonalized basis vector as a double
.
This can be called when no algorithm is currently running.
long double plll::LatticeReduction::getGSSqNormLD  (  unsigned  )  const 
Returns the squared norm of the ith GramSchmidt orthogonalized basis vector as a long double
.
This can be called when no algorithm is currently running.
arithmetic::Real plll::LatticeReduction::getGSSqNormR  (  unsigned  )  const 
Returns the squared norm of the ith GramSchmidt orthogonalized basis vector as a arithmetic::Real
number.
This can be called when no algorithm is currently running.
arithmetic::Real plll::LatticeReduction::getGSSqNormR  (  unsigned  , 
const arithmetic::RealContext &  
)  const 
Returns the squared norm of the ith GramSchmidt orthogonalized basis vector as a arithmetic::Real
number.
This can be called when no algorithm is currently running. Uses the default arithmetic::RealContext
.
Integers plll::LatticeReduction::getIntegers  (  )  const 
Returns the currently set integer arithmetic.
const linalg::math_matrix<arithmetic::Integer>& plll::LatticeReduction::getLattice  (  )  const 
Returns the current lattice generating set as a matrix.
The rows of the matrix are the vectors.
unsigned plll::LatticeReduction::getMaximalCoreUsage  (  ) 
Returns the current maximal number of cores used.
std::pair<MinCallbackFunction, MinCallbackFunction_LI> plll::LatticeReduction::getMinCallbackFunction  (  )  const 
Retrieves the currently set minimum callback function.
std::pair<unsigned, unsigned> plll::LatticeReduction::getRange  (  )  const 
Retrieves the current range.
const linalg::math_matrix<arithmetic::Integer>* plll::LatticeReduction::getTransformation  (  )  const 
Queries the current transformation matrix.
If none is recorded, NULL
is returned.
Transform plll::LatticeReduction::getTransformationMode  (  )  const 
Queries whether transformation matrix (normal or inverse) is recorded.
const VerboseFunction& plll::LatticeReduction::getVerboseFunction  (  ) 
Retrieves the current verbose output function.
VerboseOutputLevel plll::LatticeReduction::getVerboseOutputLevel  (  ) 
Retrieves the current verbose output level.
void plll::LatticeReduction::hkz  (  bool  dual = false  ) 
Computes a HermiteKorkineZolotarev reduced basis.
This is one of the strongest reduction method known and cannot be computed efficiently. It will be computed by calls to the SVP solver if a lattice of rank is given.
In case dual
is set to true
, a HKZ basis will be computed of the reversed dual of the current lattice.
bool plll::LatticeReduction::isBKZBasis  (  double  alpha = 0.99 , 
unsigned  blocksize = 20 , 

BKZMode  mode = BKZ_SchnorrEuchner 

)  const 
Tests whether the given lattice basis is BKZ reduced with respect to the given reduction parameter alpha
( ), the given block size blocksize
and mode mode
.
bool plll::LatticeReduction::isHKZBasis  (  bool  dual = false  )  const 
Tests whether the given lattice basis (or its reversed dual, in case dual
is true
) is HKZ reduced.
bool plll::LatticeReduction::isLLLBasis  (  double  alpha = 0.99 , 
LLLMode  mode = LLL_Classic 

)  const 
Tests whether the given lattice basis is LLL reduced with respect to the given reduction parameter alpha
( ) and mode mode
.
bool plll::LatticeReduction::isSVPBasis  (  bool  dual = false  )  const 
Tests whether the given lattice basis (or its reversed dual, in case dual
is true
) has a shortest vector at the first index.
bool plll::LatticeReduction::isTransformationRecorded  (  )  const 
Queries whether a transformation matrix is recorded.
void plll::LatticeReduction::lll  (  double  alpha = 0.99 , 
LLLMode  mode = LLL_Classic 

) 
Applies LLL with given reduction parameter alpha
( ) and mode mode
.
By default, the reduction parameter is 0.99 and the mode is LLL_Classic
.
Note that often 0.99 completely suffices as a reduction parameter, and that the default alpha
used by Lenstra, Lenstra and LovĂˇsz is 0.75.
void plll::LatticeReduction::modAdd  (  unsigned  i, 
unsigned  j,  
const arithmetic::Integer &  m  
) 
Adds m
times the i
th basis vector to the j
th basis vector.
This can be called when no algorithm is currently running.
void plll::LatticeReduction::modFlip  (  unsigned  ) 
Flips the signs of the given basis vector.
This can be called when no algorithm is currently running.
void plll::LatticeReduction::modSwap  (  unsigned  , 
unsigned  
) 
Swaps two given basis vectors.
This can be called when no algorithm is currently running.
unsigned plll::LatticeReduction::rank  (  )  const 
Returns the current rank, i.e. the number of generating vectors.
After calling LLL or another reduction algorithm (not sort
etc.), this equals the rank of the lattice since the vectors are in fact a basis.
void plll::LatticeReduction::setAnnealingBKZ  (  const AnnealCallbackFunction &  , 
const BKZ_AnnealFunction &  
) 
Sets annealing functions for BKZ.
void plll::LatticeReduction::setAnnealingLLL  (  const AnnealCallbackFunction &  , 
const LLL_AnnealFunction &  
) 
Sets annealing functions for LLL.
void plll::LatticeReduction::setArithmetic  (  Arithmetic  ) 
Sets which arithmetic will be used for GramSchmidt orthogonalizations.
void plll::LatticeReduction::setCallbackFunction  (  const CallbackFunction &  , 
const CallbackFunction_LI &  = CallbackFunction_LI() 

) 
Sets a callback function.
The callback function will be called in regular intervals during calls to reduction algorithms. These intervals are garuanteed minimal waiting times between calls; there is no upper bound; if for example an enumeration is running, this function will only be called when the enumeration eventually finishes.
CallbackFunction
callback function is set and the integer arithmetic is set to I_LongInt
or I_Auto
(and long int
lattices are processed), the lattice must be converted for every call.void plll::LatticeReduction::setCallbackFunction  (  const CallbackFunction_LI &  ) 
Sets a callback function.
The callback function will be called in regular intervals during calls to reduction algorithms. These intervals are garuanteed minimal waiting times between calls; there is no upper bound; if for example an enumeration is running, this function will only be called when the enumeration eventually finishes.
I_ArbitraryPrecision
or I_Auto
(and arithmetic::Integer
lattices are processed), the lattice must be converted for every call.void plll::LatticeReduction::setCallbackInterval  (  double  = 60.0 *5.0  ) 
Sets the callback interval for the callback function.
By default, the interval is every 5 minutes. The value can be set in seconds, where fractional multiples are allowed.
void plll::LatticeReduction::setDeepInsertionChoice  (  DIChoice  , 
unsigned  = 1 

) 
Sets the Deep Insertion choice and block size, which by default is 1.
void plll::LatticeReduction::setDeepInsertionMethod  (  DIMethod  , 
DIMode  = DIM_Default 

) 
Sets the Deep Insertions method and optionally also the mode.
The default for the mode is DIM_Default
.
void plll::LatticeReduction::setDeepInsertionMode  (  DIMode  ) 
Sets the Deep Insertions mode.
void plll::LatticeReduction::setDefaultAnnealing  (  ) 
Sets the default annealing functions.
This is equivalent to a call both to setDefaultAnnealingLLL()
and setDefaultAnnealingBKZ()
.
void plll::LatticeReduction::setDefaultAnnealingBKZ  (  ) 
Sets the defalut BKZ annealing function.
void plll::LatticeReduction::setDefaultAnnealingLLL  (  ) 
Sets the defalut LLL annealing function.
void plll::LatticeReduction::setEnumCallbackFunction  (  const EnumCallbackFunction &  , 
const EnumCallbackFunction_LI &  = EnumCallbackFunction_LI() 

) 
Sets a enumeration callback function which will be used if a new shortest vector is found during an enumeration.
Note that the found vector might be much longer than vectors found during previous enumerations or during previous calls of a MinCallbackFunction
; it will only be shorter than the vectors found during the current enumeration.
EnumCallbackFunction
callback function is set and the integer arithmetic is set to I_LongInt
or I_Auto
(and long int
lattices are processed), the lattice must be converted for every call.void plll::LatticeReduction::setEnumCallbackFunction  (  const EnumCallbackFunction_LI &  ) 
Sets a enumeration callback function which will be used if a new shortest vector is found during an enumeration.
Note that the found vector might be much longer than vectors found during previous enumerations or during previous calls of a MinCallbackFunction
; it will only be shorter than the vectors found during the current enumeration.
I_ArbitraryPrecision
or I_Auto
(and arithmetic::Integer
lattices are processed), the lattice must be converted for every call.void plll::LatticeReduction::setGramSchmidt  (  GramSchmidt  ) 
Sets which GramSchmidt orthogonalization method will be used.
void plll::LatticeReduction::setGramSchmidtRestart  (  bool  ) 
Sets that the current GramSchmidt method should use restarts.
This makes only sense for G_Classic
and G_Givens
, where swap()
, add()
etc. modify the GramSchmidt coefficients directly and thus might propagate approximation errors.
Currently experimental.
void plll::LatticeReduction::setIntegers  (  Integers  ) 
Sets which integer arithmetic will be used for all lattice operations.
void plll::LatticeReduction::setLattice  (  const linalg::math_matrix< arithmetic::Integer > &  lattice  ) 
Sets the current lattice of the LatticeReduction
object to the lattice given by the current matrix.
The rows of the matrix lattice
are taken as the generating set.
void plll::LatticeReduction::setLattice  (  const linalg::math_matrix< arithmetic::NInt< IType > > &  lattice  ) 
Sets the current lattice of the LatticeReduction
object to the lattice given by the current matrix.
The rows of the matrix lattice
are taken as the generating set.
IType  A native CPU integer type. Must be int , long int or long long . 
void plll::LatticeReduction::setMaximalCoreUsage  (  unsigned  ) 
Setups the maximal number of cores which will be used by the plll
library.
If 0 is specified, as many as possible (i.e. needed and available) are used. This currently only affects parallel enumeration.
The default value is 0.
void plll::LatticeReduction::setMinCallbackFunction  (  const MinCallbackFunction &  , 
const MinCallbackFunction_LI &  = MinCallbackFunction_LI() 

) 
Sets a minimum callback function which will be called as soon as a new shortest vector is found during reduction.
It will not be called during enumerations (see [setEnumCallbackFunction](setEnumCallbackFunction) for this case), but only afterwards if the returned vector is shorter than the previous ones.
(Note that the unprojected norms will be used to compare lengths.)
MinCallbackFunction
callback function is set and the integer arithmetic is set to I_LongInt
or I_Auto
(and long int
lattices are processed), the lattice must be converted for every call.void plll::LatticeReduction::setMinCallbackFunction  (  const MinCallbackFunction_LI &  ) 
Sets a minimum callback function which will be called as soon as a new shortest vector is found during reduction.
It will not be called during enumerations (see [setEnumCallbackFunction](setEnumCallbackFunction) for this case), but only afterwards if the returned vector is shorter than the previous ones.
(Note that the unprojected norms will be used to compare lengths.)
I_ArbitraryPrecision
or I_Auto
(and arithmetic::Integer
lattices are processed), the lattice must be converted for every call.void plll::LatticeReduction::setRange  (  unsigned  begin, 
unsigned  end = std::numeric_limits< unsigned >::max() 

) 
Retricts all algorithms to the range [begin, end].
If not said otherwise, they will be dealt with after projection into the orthogonal complement of the first begin
basis vectors.
If end
is larger than the index of the last vector, all basis vectors following index begin
will be used. The default is to handle all basis vectors.
void plll::LatticeReduction::setVerbose  (  VerboseOutputLevel  level, 
const VerboseFunction &  = 0 

) 
Sets the verbose output level to level
.
If given, the current verbose output function will also be set.
void plll::LatticeReduction::sizereduction  (  ) 
Applies only size reduction to the vectors.
void plll::LatticeReduction::sort  (  bool  projected = false  ) 
Sorts the vectors by their norm.
If the parameter projected
is set to true
, the GramSchmidt projected norms are used instead.
void plll::LatticeReduction::svp  (  bool  make_basis = true , 
bool  extreme = false , 

bool  dual = false 

) 
Computes a shortest vector of the lattice and inserts it at the beginning.
If make_basis
is set to true
, the resulting generating system is reduced to a basis using LLL, so that the first vector is the shortest (such bases are also called SVP bases).
If extreme
is set to true
, Extreme Pruning as described by N. Gama, P. Q. Nguyen and O. Regev in [7] will be used. Note that this is experimental at the moment.
In case dual
is set to true
, a SVP generating system respectively basis will be computed of the reversed dual of the current lattice.