Skip to content

yanesca/cleanbkz

Repository files navigation

cleanbkz is a library to find short vectors in a lattice. Once finished 
it will contain an improved enumeration algorithm using extreme pruning,
the bkz2.0 and probably an improved random sampler algorithm. 

------------------------
1. Compiling the cleanbkz sources
------------------------

cleanbkz requires the NTL library. Version 5.4.2 (or higher) is needed. 
Once you have NTL installed, execute:

$ cmake .
$ make

Now both the library and the tests are compiled. You can find the test
executables and the command line interface in the bin/ folder.

The scripts plot.sh and debug.sh require gnuplot to function properly 
and visualize the generated data.


------------------------
2. The command line interface 
------------------------

Every command line tool has a built-in help accessible with the -h switch. 
Examples:

0) Measuring the rate of reduction and enumeration:

./bin/timing -d 60 -k 20 -n 960

Wait until it finishes. On a AMD Opteron(tm) 3380 it took 15 minutes and 
gave the following result:
 
Measuring dimension 60:
t_node= 6.26296e-08
t_reduc= 0.855437


1) Generating a lattice:

./bin/genlattice -d 60 -c 0.94 -s 11 -k 20 > data/d60s11k20c0_94.lat


2) Generating a boundary function:

./bin/boundtool -f data/d60s11k20c0_94.lat -n 6.26296e-08 -r 0.855437 -l 60 > data/d60s11k20c0_94.plt

Wait until it finishes. On a AMD Opteron(tm) 3380 it took 20 minutes. You 
also can generate a pdf chart of the bounding function:

./plot.sh data/d60s11k20c0_94.plt 

This bounding function will not yet be optimal. To get a close to optimal
bounding function run the optimization a little longer:

./bin/boundtool -f data/d60s11k20c0_94.lat -n 6.26296e-08 -r 0.855437 -l 60 -c 3000 > data/d60s11k20c0_94_tri.plt


3) Running the actual enumeration:

The file produced in the previous step contains data for gnuplot and
other information like the bounding function in NTL's format, the
predicted success probability and the expected running time. 

The following program requires the boundary function in NTL's format,
so first we need to copy the line (without the starting '#' sign) in
a new text file. In this example the name of this new text file is
'd60s11k20c0_94.bnd'. Now issue the command

./bin/eprune -l data/d60s11k20c0_94.lat -b data/d60s11k20c0_94.bnd

and wait until it finishes. On a AMD Opteron(tm) 3380 it took around
89 seconds, fairly close to the promised 95 seconds.


------------------------
3. Generate API documentation 
------------------------

The source files are annotated for doxygen documentation. To generate
the documentation, first install doxygen and then execute:

$ make doc

Now the documentation is in the doc/ folder.


------------------------
4. File extensions and formats
------------------------

.lat	These are the data files generated by the genlattice tool and
	contain the lattice basis in NTL's output format. 

.plt	Boundary function generated by the boundtool application in a 
	form readable by gnuplot.

.bnd	Boundary function in NTL's format. It is usually created by 
	copying the corresponding line from a .plt file.


About

It is a library to find short vectors in a lattice.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published