The class performing block reduction. More...

#include <bkz.h>

Public Member Functions
	BKZReduction (MatGSOInterface< ZT, FT > &m, LLLReduction< ZT, FT > &lll_obj, const BKZParam &param)
	Create a BKZObject. More...

	~BKZReduction ()

bool	svp_preprocessing (int kappa, unsigned int block_size, const BKZParam &param)
	Preprocesses a block. More...

bool	svp_postprocessing (int kappa, int block_size, const vector< FT > &solution, bool dual=false)
	Inserts given (dual) vector into the basis. More...

bool	svp_reduction (int kappa, int block_size, const BKZParam &param, bool dual=false)
	(d)SVP-reduce a block. More...

bool	tour (const int loop, int &kappa_max, const BKZParam &param, int min_row, int max_row)
	Runs a BKZ tour. More...

bool	sd_tour (const int loop, const BKZParam &param, int min_row, int max_row)
	Runs a SD-BKZ tour. More...

bool	hkz (int &kappa_max, const BKZParam &param, int min_row, int max_row)
	HKZ reduces a block. More...

bool	slide_tour (const int loop, const BKZParam &param, int min_row, int max_row)
	Runs a tour of slide reduction. More...

bool	bkz ()
	Runs the main loop of block reduction. More...

void	rerandomize_block (int min_row, int max_row, int density)

void	dump_gso (const std::string &filename, bool append, const std::string &step, const int loop, const double time)
	Dumps the shape of the basis. More...

Data Fields
int	status

long	nodes

Detailed Description

template<class ZT, class FT>
class BKZReduction< ZT, FT >

The class performing block reduction.

This class implements BKZ, SD-BKZ and Slide Reduction. For this it relies on the GSO, LLL, and Enumeration modules. It assumes that the basis is LLL reduced.

Constructor & Destructor Documentation

◆ BKZReduction()

template<class ZT , class FT >

FPLLL_BEGIN_NAMESPACE BKZReduction< ZT, FT >::BKZReduction	(	MatGSOInterface< ZT, FT > &	m,
		LLLReduction< ZT, FT > &	lll_obj,
		const BKZParam &	param
	)

Create a BKZObject.

Parameters

m	GSO object corresponding to the basis to be reduced
lll_obj	LLL object associated to the same GSO object m
param	parameter object (see bkz_param.h)

◆ ~BKZReduction()

template<class ZT , class FT >

BKZReduction< ZT, FT >::~BKZReduction

Member Function Documentation

◆ bkz()

template<class ZT , class FT >

bool BKZReduction< ZT, FT >::bkz

Runs the main loop of block reduction.

Top level function implementing block reduction by repeatedly calling the corresponding tour and regularly checking terminating conditions. Also performs some postprocessing.

Returns: true if the reduction was successful, false otherwise.

◆ dump_gso()

template<class ZT , class FT >

void BKZReduction< ZT, FT >::dump_gso	(	const std::string &	filename,
		bool	append,
		const std::string &	step,
		const int	loop,
		const double	time
	)

Dumps the shape of the basis.

Writes the specified prefix and shape of the current basis into the specified file.

Parameters

filename	name of the file
prefix	string to write into the file before the shape of the basis
append	flag specifying if the shape should be appended to the file (or if the file should be overwritten)

◆ hkz()

template<class ZT , class FT >

bool BKZReduction< ZT, FT >::hkz	(	int &	kappa_max,
		const BKZParam &	param,
		int	min_row,
		int	max_row
	)

HKZ reduces a block.

Runs HKZ reduction from min_row to max_row by successively calling svp_reduction.

Parameters

kappa_max	the largest kappa s.t. the block from min_row to kappa is BKZ reduced, also only for reporting purposes
param	parameter object
min_row	start of the tour
max_row	end of the tour

Returns: false if it made progress, true otherwise

◆ rerandomize_block()

template<class ZT , class FT >

void BKZReduction< ZT, FT >::rerandomize_block	(	int	min_row,
		int	max_row,
		int	density
	)

Randomize basis between from min_row and max_row (exclusive)

permute rows
apply lower triangular matrix with coefficients in -1,0,1
LLL reduce result

Parameters

min_row	start in this row
max_row	stop at this row (exclusive)
density	number of non-zero coefficients in lower triangular transformation matrix

◆ sd_tour()

template<class ZT , class FT >

bool BKZReduction< ZT, FT >::sd_tour	(	const int	loop,
		const BKZParam &	param,
		int	min_row,
		int	max_row
	)

Runs a SD-BKZ tour.

Runs a dual BKZ tour from max_row to min_row and a BKZ tour from min_row to max_row by successively calling svp_reduction.

Parameters

loop	counter indicating the iteration, only for reporting purposes
param	parameter object
min_row	start of the tour
max_row	end of the tour

Returns: false if it made progress, true otherwise

◆ slide_tour()

template<class ZT , class FT >

bool BKZReduction< ZT, FT >::slide_tour	(	const int	loop,
		const BKZParam &	param,
		int	min_row,
		int	max_row
	)

Runs a tour of slide reduction.

Runs a tour of slide reduction from min_row to max_row by 1) alternating LLL and svp reductions on disjoint blocks 2) dual svp reductions on slightly shifted disjoint blocks

Parameters

loop	counter indicating the iteration, only for reporting purposes
param	parameter object
min_row	start of the tour
max_row	end of the tour

Returns: false if it made progress, true otherwise

◆ svp_postprocessing()

template<class ZT , class FT >

bool BKZReduction< ZT, FT >::svp_postprocessing	(	int	kappa,
		int	block_size,
		const vector< FT > &	solution,
		bool	dual = `false`
	)

Inserts given (dual) vector into the basis.

Inserts a (dual) vector into the basis. This function does not produce any linear dependencies, i.e. the result is a basis with the specified (dual) vector in the first (resp, last) position, but there are no guarantees beyond that, i.e. the basis might not be LLL reduced or even size reduced.

Parameters

kappa	start of the block
block_size	size of the block
solution	the coefficients of the (dual) vector in the current (dual) basis
dual	flag specifying if 'solution' is a dual or primal vector and to be inserted into the basis or its dual

Returns: false if it made progress, true otherwise

◆ svp_preprocessing()

template<class ZT , class FT >

bool BKZReduction< ZT, FT >::svp_preprocessing	(	int	kappa,
		unsigned int	block_size,
		const BKZParam &	param
	)

Preprocesses a block.

Preprocess a block using LLL or stronger recursive preprocessing.

Parameters

kappa	start of the block
block_size	size of the block
param	parameter object for the current block size (the parameter object for the recursive calls will be created in this function using the information from this object)

Returns: false if it modified the basis, true otherwise

◆ svp_reduction()

template<class ZT , class FT >

bool BKZReduction< ZT, FT >::svp_reduction	(	int	kappa,
		int	block_size,
		const BKZParam &	param,
		bool	dual = `false`
	)

(d)SVP-reduce a block.

Ensures that the first (resp. last) vector in a block of the (dual) basis is the shortest vector in the projected lattice generated by the block (or its dual, resp.). This is implemented using pruned enumeration with rerandomization. The results returned by the enumeration are inserted using postprocessing, and so are no guarantees beyond that, i.e. the basis might not be LLL reduced or even size reduced.

Parameters

kappa	start of the block
block_size	size of the block
param	parameter object (may be different from the one in the constructor)
dual	flag specifying if the block is to be SVP or dual SVP reduced.

Returns: false if it made progress, true otherwise

◆ tour()

template<class ZT , class FT >

bool BKZReduction< ZT, FT >::tour	(	const int	loop,
		int &	kappa_max,
		const BKZParam &	param,
		int	min_row,
		int	max_row
	)

Runs a BKZ tour.

Runs a BKZ tour from min_row to max_row by successively calling svp_reduction.

Parameters

loop	counter indicating the iteration, only for reporting purposes
kappa_max	the largest kappa s.t. the block from min_row to kappa is BKZ reduced, also only for reporting purposes
param	parameter object
min_row	start of the tour
max_row	end of the tour

Returns: false if it made progress, true otherwise

Field Documentation

◆ nodes

template<class ZT , class FT >

long BKZReduction< ZT, FT >::nodes

Number of nodes visited during enumeration.

◆ status

template<class ZT , class FT >

int BKZReduction< ZT, FT >::status

Status of reduction (see defs.h)

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

fplll/bkz.h
fplll/bkz.cpp

Public Member Functions

Data Fields

Detailed Description

Constructor & Destructor Documentation

◆ BKZReduction()

◆ ~BKZReduction()

Member Function Documentation

◆ bkz()

◆ dump_gso()

◆ hkz()

◆ rerandomize_block()

◆ sd_tour()

◆ slide_tour()

◆ svp_postprocessing()

◆ svp_preprocessing()

◆ svp_reduction()

◆ tour()

Field Documentation

◆ nodes

◆ status