Provides an interface to the lattice reduction algorithms of the plll library. More...

#include <plll.hpp>

Classes
class	GramSchmidtInformer
	Provides information on the Gram-Schmidt 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 Gram-Schmidt 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 Gram-Schmidt 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 Gram-Schmidt orthogonalizations. More...

Arithmetic	getArithmetic () const
	Returns the currently set arithmetic for Gram-Schmidt 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...

Gram-Schmidt orthogonalization configuration functions.
void	setGramSchmidt (GramSchmidt)
	Sets which Gram-Schmidt orthogonalization method will be used. More...

void	setGramSchmidtRestart (bool)
	Sets that the current Gram-Schmidt method should use restarts. More...

GramSchmidt	getGramSchmidt () const
	Returns the currently used Gram-Schmidt orthogonalization method. More...

bool	getGramSchmidtRestart () const
	Returns whether restarts are used for the current Gram-Schmidt orthogonalization method. More...

Gram-Schmidt orthogonalization querying functions.
void	forceGSRebuild (bool makeSureAllComputed=false)
	Forces the Gram-Schmidt coefficients to be rebuild. More...

double	getGSCoefficientD (unsigned, unsigned) const
	Returns the (i, j) Gram-Schmidt coefficient as a `double`. More...

long double	getGSCoefficientLD (unsigned, unsigned) const
	Returns the (i, j) Gram-Schmidt coefficient as a `long double`. More...

arithmetic::Real	getGSCoefficientR (unsigned, unsigned) const
	Returns the (i, j) Gram-Schmidt coefficient as a `arithmetic::Real` number. More...

arithmetic::Real	getGSCoefficientR (unsigned, unsigned, const arithmetic::RealContext &) const
	Returns the (i, j) Gram-Schmidt coefficient as a `arithmetic::Real` number. More...

double	getGSSqNormD (unsigned) const
	Returns the squared norm of the i-th Gram-Schmidt orthogonalized basis vector as a `double`. More...

long double	getGSSqNormLD (unsigned) const
	Returns the squared norm of the i-th Gram-Schmidt orthogonalized basis vector as a `long double`. More...

arithmetic::Real	getGSSqNormR (unsigned) const
	Returns the squared norm of the i-th Gram-Schmidt orthogonalized basis vector as a `arithmetic::Real` number. More...

arithmetic::Real	getGSSqNormR (unsigned, const arithmetic::RealContext &) const
	Returns the squared norm of the i-th Gram-Schmidt 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.

Multi-threading 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` ( $\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` ( $\alpha$ ), block size `blocksize` and mode `mode`. More...

void	hkz (bool dual=false)
	Computes a Hermite-Korkine-Zolotarev 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` ( $\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` ( $\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...

Detailed Description

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.

Definition at line 66 of file plll.hpp.

Member Typedef Documentation

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.

Definition at line 851 of file plll.hpp.

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

Definition at line 882 of file plll.hpp.

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.

See also: Callbacks

Definition at line 780 of file plll.hpp.

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.

See also: Callbacks

Definition at line 788 of file plll.hpp.

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.

See also: Callbacks

Definition at line 820 of file plll.hpp.

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.

See also: Callbacks

Definition at line 835 of file plll.hpp.

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

Definition at line 867 of file plll.hpp.

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.

See also: Callbacks

Definition at line 798 of file plll.hpp.

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.

See also: Callbacks

Definition at line 808 of file plll.hpp.

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.

See also: Verbose output

Definition at line 895 of file plll.hpp.

Member Enumeration Documentation

enum plll::LatticeReduction::Arithmetic

Specifies which arithmetic to use for Gram-Schmidt orthogonalization.

Specifies which arithmetic should be used by the plll library for Gram-Schmidt 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.

See also: Arithmetic

Enumerator
A_Rational	Rational arithmetic, i.e. a pair of `arithmetic::Integer` objects is used for numerator and denominator. While this yields infinite precision, it is also quite slow.
A_Real	MPFR-based `arithmetic::Real` arithmetic. This is a floating point type with arbitrary (but fixed) precision. A precision is automatically selected by the library.
A_LongDouble	The system's native `long double` arithmetic. This is a finite-precision floating point type with implementation defined precision. On Intel/AMD/... platforms, it usually provides a mantissa of 80 bits, while on UltraSparc platforms, this is a Float128 type with 112 bit mantissa, whose arithmetic is unfortunately usually implemented in software and not in hardware. This is the default setting for `plll`.
A_Double	The system's native `double` arithmetic. This is a finite-precision floating point type with implementation defined precision. It usually has a mantissa of 53 bits.
A_DoubleDouble	Uses two native `double` floating point numbers to represent floating point numbers with higher precision. While the exponent is still limited to a `double`'s range, the precision is much higher; double double numbers correspond to floating point numbers with a mantissa of 104 bits. 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 `double` floating point numbers to represent floating point numbers with higher precision. While the exponent is still limited to a `double`'s range, the precision is much higher; quad double numbers correspond to floating point numbers with a mantissa of 209 bits. 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 `A_LongDouble`.

Definition at line 123 of file plll.hpp.

enum plll::LatticeReduction::BKZMode

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 Korkine-Zolotarev or at least SVP bases for certain blocks of (projected) basis vectors, or their dual.

Enumerator
BKZ_SchnorrEuchner	The classical Schnorr-Euchner BKZ algorithm, as described in Section 6 of [15] by C.-P. Schnorr and M. Euchner. This is the default setting for `plll`. See also Schnorr-Euchner BKZ
BKZ_Simplified	A simplified version of the BKZ algorithm, as described by G. Hanrot, X. Pujol and D. Stehle in [8]. See also Simplified BKZ
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 Hermite-Korkine-Zolotarev (HKZ) bases for every block. See also Terminating BKZ
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. See also Terminating BKZ
BKZ_PrimalDual	The primal-dual BKZ algorithm by H. Koy, as described in Section 3 of [17] See also Primal-Dual BKZ
BKZ_SlideReduction	The slide reduction algorithm, as described by N. Gama and P. Q. Nguyen in [5]. See also Slide Reduction
BKZ_ImprovedSlideReduction	A improved and accelerated version of Slide Reduction, as described in [18] by C.-P. Schnorr (Section 3). See also Improved Slide Reduction
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. See also Improved Slide Reduction
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. See also Improved Slide Reduction
BKZ_SemiBlock2k	The semi block 2k-reduction, as described by C.-P. Schnorr in Section 2 of [17]. See also Semi-Block-2k-Reduction
BKZ_SamplingReduction	The Sampling Reduction, as described by J. A. Buchmann and C. Ludwig in [2]. See also Sampling Reduction
BKZ_Default	Alias for the default BKZ variant, i.e. for `BKZ_SchnorrEuchner`.

Definition at line 315 of file plll.hpp.

enum plll::LatticeReduction::DIChoice

Specifies which Deep Insertion choice is used.

Specifies which vectors are considered for Deep Insertions by the plll library.

Enumerator
DIC_First	Deep Insertions considers only the first t vectors of the basis, where t is given.
DIC_Block	Deep Insertions considers only the block of t basis vectors ending at the current vector, where t is given.
DIC_FirstBlock	Deep Insertions considers both the first t basis vectors, and the block of t basis vectors ending at the current vector, where t is given. This is the default setting for the LLL reduction in V. Shoup's Number Theory Library, if Deep Insertions are enabled.
DIC_All	Deep Insertions considers all basis vectors as possible destinations. This is the default setting for `plll`.
DIC_Default	Alias for the default Deep Insertions choice, i.e. for `DIC_All`.

Definition at line 522 of file plll.hpp.

enum plll::LatticeReduction::DIMethod

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 `plll`.
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 `DI_None`.

Definition at line 485 of file plll.hpp.

enum plll::LatticeReduction::DIMode

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.

Enumerator
DIM_BeforeSR	Do Deep Insertions only before size reduction.
DIM_AfterSR	Do Deep Insertions only after size reduction.
DIM_Both	Do Deep Insertions both before and after size reduction. This is the default setting for `plll`.
DIM_Default	Alias for the default Deep Insertions mode, i.e. for `DIM_Both`.

Definition at line 552 of file plll.hpp.

enum plll::LatticeReduction::GramSchmidt

Specifies which Gram-Schmidt orthogonalization is used.

Specifies which Gram-Schmidt orthogonalization should be used by the plll library. Always available are classic GS, classic GS with integer arithmetic, and numerically stable GS. For floating-point arithmetic, also Givens rotations can be used for GS orthogonalization.

See also: Gram-Schmidt orthogonalization

Enumerator
G_Classic	"Classical" Gram-Schmidt orthogonalization. Uses formulae to update Gram-Schmidt coefficients on swaps, transformations etc., which can introduce additional error with floating point arithmetic.
G_ClassicInteger	Integer-based Gram-Schmidt orthogonalization. Internally uses arbitrary precision integers respectively rational numbers. Slow, but always accurate.
G_Givens	Uses Givens rotations to compute Gram-Schmidt orthogonalization. Only available for floating-point arithmetic (i.e. everything but `A_Rational`). Uses formulae to update Gram-Schmidt coefficients on swaps, transformations etc., which can introduce additional error with floating point arithmetic.
G_NumStable	Uses numerically stable Gram-Schmidt 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 `plll`.
G_Default	Alias for the default Gram-Schmidt orthogonalization, i.e. for `A_NumStable`.

Definition at line 209 of file plll.hpp.

enum plll::LatticeReduction::Integers

Specifies which arithmetic to use for integer operations.

Specifies which arithmetic should be used by the plll library for integer operations. Besides GMP-based arbitrary precision integers, it also provides support for system-dependent long int integers and for an automatic decision mode which uses arbitrary precision integers if necessary and system integers otherwise.

See also: Arithmetic

Enumerator
I_Auto	Decides based on the input whether to use arbitrary precision integer arithmetic or system-dependent integer arithmetic. This decision is analyzed from time to time, and arithmetic is changed when necessary. This is the default setting for `plll`.
I_ArbitraryPrecision	Uses `arithmetic::Integer` arbitrary precision integers. These are provided by GMP and are only limited by the system's available RAM.
I_LongInt	Uses `long int` native CPU arithmetic. On modern CPUs, this yields at least 64 bits of precision.
I_Default	Alias for the default integer arithmetic, i.e. for `A_Auto`.

Definition at line 178 of file plll.hpp.

enum plll::LatticeReduction::LLLMode

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 Gram-Schmidt orthogonalization $\pi_1(b_1), \dots, \pi_k(b_k)$ of the basis $b_1, \dots, b_k$ , this condition can be expressed as $\alpha \cdot \\|\pi_k(b_k)\\|^2 > \\|\pi_k(b_{k+1})\\|^2$ . This is the default setting for `plll`. See also Classic LLL
LLL_Unprojected	A simpler condition, which compares the unprojected lengths of two adjacent. In terms of the basis $b_1, \dots, b_k$ , this condition can be expressed as $\alpha \cdot \\|b_k\\|^2 > \\|b_{k+1}\\|^2$ . See also Unprojected LLL
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 Gram-Schmidt orthogonalization $\pi_1(b_1), \dots, \pi_k(b_k)$ of the basis $b_1, \dots, b_k$ , this condition can be expressed as $\frac{3}{4} \cdot \alpha \cdot \\|\pi_k(b_k)\\|^2 > \\|\pi_{k+1}(b_{k+1})\\|^2$ . See also Siegel LLL
LLL_Default	Alias for the default LLL condition, i.e. for `LLL_Classic`.

Definition at line 270 of file plll.hpp.

enum plll::LatticeReduction::SVPMode

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 Kannan-Schnorr-Euchner enumeration algorithm [15] with various improvements; see, for example, Appendix B of [7]. See also Kannan-Schnorr-Euchner enumeration
SVP_ParallelKannanSchnorrEuchner	A parallelized variant of the Kannan-Schnorr-Euchner 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 `plll`. Note that in case only one core is available, automatically the solver `SVP_KannanSchnorrEuchner` will be used. See also Kannan-Schnorr-Euchner enumeration
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. See also Schnorr's new SVP solver
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]. See also Voronoi Cell computation
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. See also List Sieve
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. See also List Sieve Birthday
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. See also Gauss Sieve
SVP_Default	Alias for the default SVP solver, i.e. for `SVP_ParallelKannanSchnorrEuchner`.

Definition at line 409 of file plll.hpp.

enum plll::LatticeReduction::Transform

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.

Enumerator
T_Normal	Computes a transformation matrix such that if is the old and the new matrix representing the lattice before respectively after reduction, then $T_1 \cdot A = A'$ .
T_Inverse	Computes a transformation matrix such that if is the old and the new matrix representing the lattice before respectively after reduction, then $T_2 \cdot A' = A$ . Note that if the matrices are square, then both are invertible and $T_2 = T_1^{-1}$ .

Definition at line 249 of file plll.hpp.

enum plll::LatticeReduction::VerboseLevel

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.

See also: Verbose output

Enumerator
VL_Error	The given message is an error.
VL_Warning	The given message is a warning.
VL_Information	The given message is purely informative.
VL_Chatter	The given message is chatter which can safely be ignored. Can be helpful for debugging purposes or to see more about how the algorithms work.

Definition at line 596 of file plll.hpp.

enum plll::LatticeReduction::VerboseOutputLevel

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

See also: Verbose output

Enumerator
VOL_None	Outputs nothing.
VOL_Warnings	Outputs only warnings and errors.
VOL_Informative	Outputs warnings, errors and informative messages.
VOL_Full	Outputs everything.

Definition at line 575 of file plll.hpp.

Constructor & Destructor Documentation

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.

Parameters

lattice The matrix whose rows to take as a generating system for the lattice.

See also: void setLattice(const linalg::math_matrix<arithmetic::Integer> & lattice)

template<typename IType >

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.

Parameters

lattice The matrix whose rows to take as a generating system for the lattice.

Template Parameters

IType A native CPU integer type. Must be int, long int or long long.

See also: void setLattice(const linalg::math_matrix<arithmetic::Integer> & lattice)

Member Function Documentation

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 ( $\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.

See also: BKZ-like reduction

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.

See also: disableAnnealing()

void plll::LatticeReduction::disableAnnealingLLL ( )

Disable annealing for LLL.

See also: disableAnnealing()

void plll::LatticeReduction::disableTransform ( )

Disables recording of a transformation matrix.

See also: Recording transformation matrices

void plll::LatticeReduction::enableTransform ( Transform = T_Normal )

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 $A$ denotes the basis at this point, $A'$ at a later point and $T$ the transformation matrix at that point, then $T \cdot A = A'$ .

See also: Recording transformation matrices

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.

See also: Arithmetic

void plll::LatticeReduction::forceGSRebuild ( bool makeSureAllComputed = false )

Forces the Gram-Schmidt coefficients to be rebuild.

If the argument makeSureAllComputed is set to true, all Gram-Schmidt 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 Gram-Schmidt orthogonalizations.

See also: Arithmetic

std::pair<CallbackFunction, CallbackFunction_LI> plll::LatticeReduction::getCallbackFunction ( ) const

Retrieves the currently set callback function.

See also: Callbacks

double plll::LatticeReduction::getCallbackInterval ( ) const

Retrieves the current (minimal) callback interval.

See also: Callbacks

unsigned plll::LatticeReduction::getDeepInsertionBlocksize ( ) const

Retrieves the current Deep Insertions choice block size parameter.

See also: Deep Insertions

DIChoice plll::LatticeReduction::getDeepInsertionChoice ( ) const

Retrieves the current Deep Insertions choice.

See also: Deep Insertions

DIMethod plll::LatticeReduction::getDeepInsertionMethod ( ) const

Retrieves the current Deep Insertions method.

See also: Deep Insertions

DIMode plll::LatticeReduction::getDeepInsertionMode ( ) const

Retrieves the current Deep Insertions mode.

See also: Deep Insertions

std::pair<EnumCallbackFunction, EnumCallbackFunction_LI> plll::LatticeReduction::getEnumCallbackFunction ( )

Retrieves the current enumeration callback function.

See also: Callbacks

GramSchmidt plll::LatticeReduction::getGramSchmidt ( ) const

Returns the currently used Gram-Schmidt orthogonalization method.

See also: Gram-Schmidt orthogonalization

bool plll::LatticeReduction::getGramSchmidtRestart ( ) const

Returns whether restarts are used for the current Gram-Schmidt orthogonalization method.

See also: Gram-Schmidt orthogonalization

double plll::LatticeReduction::getGSCoefficientD	(	unsigned	,
		unsigned
	)		const

Returns the (i, j) Gram-Schmidt 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) Gram-Schmidt 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) Gram-Schmidt 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) Gram-Schmidt 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 i-th Gram-Schmidt 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 i-th Gram-Schmidt 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 i-th Gram-Schmidt 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 i-th Gram-Schmidt 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.

See also: 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.

See also: Multi-Threading

std::pair<MinCallbackFunction, MinCallbackFunction_LI> plll::LatticeReduction::getMinCallbackFunction ( ) const

Retrieves the currently set minimum callback function.

See also: Callbacks

std::pair<unsigned, unsigned> plll::LatticeReduction::getRange ( ) const

Retrieves the current range.

See also: Reduction Range

const linalg::math_matrix<arithmetic::Integer>* plll::LatticeReduction::getTransformation ( ) const

Queries the current transformation matrix.

If none is recorded, NULL is returned.

See also: Recording transformation matrices

Transform plll::LatticeReduction::getTransformationMode ( ) const

Queries whether transformation matrix (normal or inverse) is recorded.

See also: Recording transformation matrices

const VerboseFunction& plll::LatticeReduction::getVerboseFunction ( )

Retrieves the current verbose output function.

See also: Verbose output

VerboseOutputLevel plll::LatticeReduction::getVerboseOutputLevel ( )

Retrieves the current verbose output level.

See also: Verbose output

void plll::LatticeReduction::hkz ( bool dual = false )

Computes a Hermite-Korkine-Zolotarev reduced basis.

This is one of the strongest reduction method known and cannot be computed efficiently. It will be computed by $k$ calls to the SVP solver if a lattice of rank $k$ 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 ( $\alpha$ ), the given block size blocksize and mode mode.

See also: bkz(alpha, blocksize, 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.

See also: hkz(dual)

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 ( $\alpha$ ) and mode mode.

See also: lll(alpha, 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.

See also: svp(*, *, dual)

bool plll::LatticeReduction::isTransformationRecorded ( ) const

Queries whether a transformation matrix is recorded.

See also: Recording transformation matrices

void plll::LatticeReduction::lll	(	double	alpha = `0.99`,
		LLLMode	mode = `LLL_Classic`
	)

Applies LLL with given reduction parameter alpha ( $\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.

See also: LLL-like reduction

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.

See also: setAnnealing()

void plll::LatticeReduction::setAnnealingLLL	(	const AnnealCallbackFunction &	,
		const LLL_AnnealFunction &
	)

Sets annealing functions for LLL.

See also: setAnnealing()

void plll::LatticeReduction::setArithmetic ( Arithmetic )

Sets which arithmetic will be used for Gram-Schmidt orthogonalizations.

See also: Arithmetic

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.

Warning: If only a usual 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.

See also: Callbacks

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.

Warning: If the integer arithmetic is set to I_ArbitraryPrecision or I_Auto (and arithmetic::Integer lattices are processed), the lattice must be converted for every call.

See also: Callbacks

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.

See also: Callbacks

void plll::LatticeReduction::setDeepInsertionChoice	(	DIChoice	,
		unsigned	= `1`
	)

Sets the Deep Insertion choice and block size, which by default is 1.

See also: Deep Insertions

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.

See also: Deep Insertions

void plll::LatticeReduction::setDeepInsertionMode ( DIMode )

Sets the Deep Insertions mode.

See also: Deep Insertions

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.

See also: setDefaultAnnealing()

void plll::LatticeReduction::setDefaultAnnealingLLL ( )

Sets the defalut LLL annealing function.

See also: setDefaultAnnealing()

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.

Warning: If only a usual 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.

See also: Callbacks

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.

Warning: If the integer arithmetic is set to I_ArbitraryPrecision or I_Auto (and arithmetic::Integer lattices are processed), the lattice must be converted for every call.

See also: Callbacks

void plll::LatticeReduction::setGramSchmidt ( GramSchmidt )

Sets which Gram-Schmidt orthogonalization method will be used.

See also: Gram-Schmidt orthogonalization

void plll::LatticeReduction::setGramSchmidtRestart ( bool )

Sets that the current Gram-Schmidt method should use restarts.

This makes only sense for G_Classic and G_Givens, where swap(), add() etc. modify the Gram-Schmidt coefficients directly and thus might propagate approximation errors.

Currently experimental.

See also: Gram-Schmidt orthogonalization

void plll::LatticeReduction::setIntegers ( Integers )

Sets which integer arithmetic will be used for all lattice operations.

See also: Arithmetic

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.

template<typename IType >

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.

Template Parameters

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.

See also: Multi-Threading

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

Warning: If only a usual 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.

See also: Callbacks

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

Warning: If the integer arithmetic is set to I_ArbitraryPrecision or I_Auto (and arithmetic::Integer lattices are processed), the lattice must be converted for every call.

See also: Callbacks

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.

See also: Reduction Range

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.

See also: Verbose output

void plll::LatticeReduction::sizereduction ( )

Applies only size reduction to the vectors.

See also: How lattice reduction works

void plll::LatticeReduction::sort ( bool projected = false )

Sorts the vectors by their norm.

If the parameter projected is set to true, the Gram-Schmidt 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.

See also: SVP solvers

The documentation for this class was generated from the following file:

/home/felix/projects/code/plll/plll/plll/include/plll.hpp

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation