Tutorial

This page contains very basic and relatively short examples demonstrating the usage of the principal functions of LatticeTester.

The examples featured here are available in the directory examples of the repository. They are compiled along the library and their source code includes the description of their usage.

These examples where conceived with two goals in mind:

• Having examples for most of the functionnalities of LatticeTester
• Testing the implementation and efficiency of the implementation of a few methods

In the examples you will learn how to create the objects representing the lattices and manipulate them, how to use the methods to manipulate those lattices basis, how to use the reduction algorithms available and how to compute basic mesures of interest like the spectral test and the normalized version of the spectral test.

Please note that the code presented here is in C++, meaning that much of it include statements, variable declarations and output formatting. The code segments relevant to the examples (that actually showcase LatticeTester fonctionnalities) have been commented to facilitate the code reading.

Warning!

It is not advised to run the BasisConstruction and the Reduction examples on a local machine because they use matrix sets that test their limits. Their execution takes a long time and uses a lot of memory. Users are nonetheless ecouraged to play with these examples, either by modifying them, or by generating another matrix set with the python3 script in the examples/bench.zip archive.

Using the library

In the event that you should need more flexibility than what is offered by the executable, we also present the classes containing the main functionnalities of LatticeTester. There are three of them bringing together similar computations :

• BasisConstruction grouping functions helping with basis, dual, and projection constructions
• Reducer with functions to do basis reduction and solve the shortest vector problem
• LatticeAnalysis that contains functions to do the computation of figures of merit

This section won't go into the depth of each of those class since it would be redundant with their documentation. Instead, we point to the examples, where their usage is demonstrated. We also point out to the following classes without which the usage of the main classes would be difficult :

• IntLatticeBasis is a class representing a lattice basis. This is the lowest level class available to represent a lattice in LatticeTester and it is the class that is needed for the instanciation of a Reducer.
• Config stores all the configuration for the execution of a LatticeAnalysis. It is possible to lauch tests by passing a Config object to a LatticeAnalysis.
• ParamReader implements a simple interface to read information from files. It also offers methods to initialize a Config object from the format of file specified above.
• Normalizer is a base class to the implementation of a normalizer to figures of merit. There are many modules implementing various normalizers for the spectral test that are available in LatticeTester.
• Weights is a base class to weight multiple figures of merit in some way to build a figure of merit of of them. Although this is not directly used by LatticeTester, it is relevant to point out this class to users interested in computing figures of merit with multiple projections from a lattice.

Basis manipulation

The following example showcases the usage of LatticeTester::BasisConstruction, either directly on matrices or on IntLatticeBasis objects. One of the repercutions this has is that this example also showcases how to create an IntLatticeBasis object.

This example compares the execution time of the two different methods for basis construction as well as the time taken to build a dual basis after one or the other. BasisConstruction contains two methods to build a basis from a set of generating vectors, GCDConstruction and LLLConstruction, described on the LatticeTester::BasisConstruction page. It is these methods that are compared here. Bellow is the code for the example.

// This should always use Types 2 or 3, because we get too big numbers with GCD
// elimination.
#define NTL_TYPES_CODE 2

#include <iostream>
#include <ctime>

#include "latticetester/Types.h"
#include "latticetester/BasisConstruction.h"
#include "latticetester/Util.h"
#include "latticetester/ParamReader.h"
#include "latticetester/IntLatticeBasis.h"

#include "Examples.h"

using namespace LatticeTester;

namespace {
  const std::string prime = primes[0];
}

int main() {
  clock_t timer = clock();
  // The different clocks we will use for benchmarking
  // We use ctime for implementation simplicity
  int max_dim = 6; // Actual max dim is 5*max_dim
  clock_t gcd_time[max_dim], lll_time[max_dim],
  dual1_time[max_dim], dual2_time[max_dim], totals[4];
  for (int i = 0; i < max_dim; i++) {
    gcd_time[i] = 0;
    lll_time[i] = 0;
    dual1_time[i] = 0;
    dual2_time[i] = 0;
  }

  // Defining constants for the execution of the algorithms
  BasisConstruction<BScal> constr; // The basis constructor we will use
  BMat bas_mat, dua_mat;

  clock_t tmp;
  for (int j = 0; j < max_dim; j++) {
    for (int k = 0; k < 10; k++) {
      std::string name = "bench/" + prime + "_" + std::to_string((j+1)*5) + "_" + std::to_string(k);
      ParamReader<MScal, BScal, RScal> reader(name + ".dat");
      reader.getLines();
      int numlines;
      unsigned int ln;
      reader.readInt(numlines, 0, 0);
      BMat bas_mat, dua_mat;
      bas_mat.SetDims(numlines, numlines);
      dua_mat.SetDims(numlines, numlines);
      ln = 1;
      reader.readBMat(bas_mat, ln, 0, numlines);

      // Creating a lattice basis
      IntLatticeBasis<MScal, BScal, NScal, RScal> lattice(bas_mat, numlines);

      if (NTL::determinant(bas_mat) == 0) {
        std::cout << name << " is singular\n";
        continue;
      }

      // Timing GCDConstruction first
      tmp = clock();
      constr.GCDConstruction(bas_mat);
      MScal modulo(1);
      gcd_time[j] += clock() - tmp;

      // Timing DualConstruction
      tmp = clock();
      constr.DualConstruction(bas_mat, dua_mat, modulo);
      dual1_time[j] += clock() - tmp;

      // Timing LLLConstruction next
      tmp = clock();
      constr.LLLConstruction(lattice.getBasis());
      modulo = MScal(1);
      lll_time[j] += clock() - tmp;

      // The following works, but does not set all the properties of lattice to
      // properly work with a dual.
      tmp = clock();
      constr.DualConstruction(lattice.getBasis(), lattice.getDualBasis(), modulo);
      dual2_time[j] += clock() - tmp;
      // This sets the lattice to know it has a dual. Computing the norm of the
      // vectors in the lattice would also be wise.
      lattice.setDualFlag(true);
    }
  }

  std::cout << "         ";
  int width1 = getWidth(gcd_time, max_dim, "GCD", totals, 0);
  int width2 = getWidth(lll_time, max_dim, "LLL", totals, 1);
  int width3 = getWidth(dual1_time, max_dim, "DUAL1", totals, 2);
  int width4 = getWidth(dual2_time, max_dim, "DUAL2", totals, 3);
  std::cout << std::endl;

  std::cout << "Total time" << std::setw(width1) << totals[0]
    << std::setw(width2) << totals[1]
    << std::setw(width3) << totals[2]
    << std::setw(width4) << totals[3] << std::endl;
  for (int i = 0; i < max_dim; i++) {
    std::cout << "Dim" << std::setw(6) << (i+1)*5
      << std::setw(width1) << gcd_time[i] << std::setw(width2) << lll_time[i]
      << std::setw(width3) << dual1_time[i] << std::setw(width4) << dual2_time[i];
    std::cout << std::endl;
  }
  std::cout << "Total time: " << (double)(clock()-timer)/(CLOCKS_PER_SEC*60) << " minutes\n";

  return 0;
}

There are two things to learn from this example. First is how to create an IntLatticeBasis. Second is the way that the BasisConstruction class is used.

When working only with LatticeTester it is recommended to represent lattices only by using the IntLatticeBasis class instead of the IntLattice class. The reasoning is that IntLattice does not bring any new functionnality by itself, it is a class that contains virtual methods specifying an easily expandable interface for different lattice types. It is also better to use IntLatticeBasis because the constructor is all that is needed to get a usable object as is done in this example. This is not the case of the IntLattice class.

Secondly, the BasisConstruction class is also very straight forward. Once the object is created, its methods can be called on matrices to transform them in place. Note that the usage of this class does not follow standard object oriented design. Since the algorithms in it are quite simple and are to be applied on basic types only, this constructed more like a container for those function, regrouping them in one simple location. Hence, when an object of this class is created, it is then possible to apply the contained algorithms on different objects as is done here.

The output of this program looks like this:

               GCD    LLL     DUAL1    DUAL2
Dim     5     4418   3074       735     1002
Dim    10    13497   7900      2647     8151
Dim    15    38502  20984      9543    19052
Dim    20    94467  44949     88171    50834
Dim    25   152712  86751    154730   181654
Dim    30   594683 137168   2970433  1682890
Dim    35 21994254 221505 168412442 13860037

Using the input and output classes

This is an example showing of the usage of both LatticeTester::ParamReader and LatticeTester::WriterRes. These two classes can read from files and format output to them. Since this functionnality is the main way to make a program interractive, most uses that are not scripting will need these classes. Both classes can be created easily, simply by specifying a path for a file that ParamReader will read from and that WriterRes will write to. most methods are named quite explicitly as can be seen below.

#define NTL_TYPES_CODE 1

#include <iostream>

#include "latticetester/ParamReader.h"
#include "latticetester/Types.h"
#include "latticetester/Reducer.h"
#include "latticetester/IntLatticeBasis.h"
#include "latticetester/WriterRes.h"

#include "NTL/LLL.h"

using namespace LatticeTester;

int main() {
  int size = 9;
  // Those two lines create a reader and ready it to be used.
  ParamReader<MScal, BScal, RScal> reader("44matrixEx.dat");
  reader.getLines();
  // Reading a matrix as an examples
  BMat matrix(size, size); // The "recipient"
  unsigned int ln = 0; // The line counter
  reader.readBMat(matrix, ln, 0, size);

  // Creation of a writer object for file IOExample.out
  WriterRes<MScal> writer("IOExample.out");

  // Writing to the file
  writer.writeString("We can write messages in the file.");
  writer.newLine();
  writer.writeString("Here is one way to write a matrix.");
  writer.newLine();
  writer.writeMMat(matrix);

  // Adding indentation
  writer.beginTabbedSection();
  writer.newLine();
  writer.writeString("Here is another one.");
  writer.newLine();
  for (int i = 0; i < matrix.NumRows(); i++) {
    writer.writeString("[");
    for (int j = 0; j < matrix.NumCols(); j++) {
      writer.writeIntScal(matrix[i][j]);
      if (j == matrix.NumCols()-1) continue;
      writer.writeString(" ");
    }
    writer.writeString("]");
    writer.newLine();
  }
  // Printing \n and ending indented section.
  writer.newParagraph();

  writer.writeString("It's also possible to use *ToString() methods to write"
      " stuff in the output\nfile.");
  writer.newLine();
  IntLatticeBasis<MScal, BScal, NScal, RScal> lat_basis(matrix, size);
  lat_basis.updateVecNorm();
  lat_basis.sort(0);
  // Writing in the file
  writer.writeString("The matrix and its vectors norms:");
  writer.newLine();
  writer.writeString(lat_basis.toStringBasis());
  writer.newLine();

  writer.writeString("Writers can be used as the program progresses, just like"
      "using a standard\noutput print, but also can be created at the end of the"
      "execution to print the\nresult of the execution, making them quite"
      "flexible.");

  return 0;
}

The way that the reader class works, is that you call a method such as readBMat in the example and it will store the requested type in a container specified as the first argument. It reads on a line specified as the second argument (starting from 0) and reads starting from the n-th word of that line (n being specified as a third argument, starting from 0). If a fourth argument is needed, it is type specific like here where the matrix needs a dimension.

The writer class works the same, but is a little simpler since everything is written sequentially. This class can also (try to) enforce indentation of the ouputed text. To do that, the usage of the newLine method, as is done in this example, is needed. This example is fairly limited in scope and does not contain other other information relevant to the usage of LatticeTester.

The Reducer class

This following example is about the usage of the LatticeTester::Reducer class. This class is central to LatticeTester and contains the most important features of the library. This example uses most of the functions of that class and tries to compare their execution times. This example works very similarly to the BasisConstruction example.

// We define the numeric types.
// It is possible to use this example with TYPES 2 and 3. For now 1 calls the
// same function for both execution and we look forward to change that.
#define NTL_TYPES_CODE 2

#include <iostream>
#include <ctime>

#include "latticetester/ParamReader.h"
#include "latticetester/Types.h"
#include "latticetester/Reducer.h"
#include "latticetester/IntLatticeBasis.h"
#include "latticetester/WriterRes.h"

#include "Examples.h"

using namespace LatticeTester;

namespace {
  // Returns the average of the length of this vector
  NScal average(NVect vector) {
    NScal sum(0);
    for (int i = 0; i<vector.length(); i++) {
      sum += vector[i];
    }
    return sum/NScal(vector.length());
  }
}

int main() {
  clock_t timer = clock();
  int max_dim = 10; 
  clock_t die_time[max_dim], lll_time[max_dim], bkz_time[max_dim],
  sho_die[max_dim], sho_lll[max_dim], sho_bkz[max_dim], tmp;
  clock_t total_times[6];
  for (int i = 0; i < max_dim; i++){
    lll_time[i] = 0;
    die_time[i] = 0;
    bkz_time[i] = 0;
    sho_die[i] = 0;
    sho_lll[i] = 0;
    sho_bkz[i] = 0;
  }
  int die_fails=0, lll_fails=0, bkz_fails=0;
  NScal vec_length[3];
  vec_length[0] = vec_length[1] = vec_length[2] = 0;

  std::string prime = primes[0];

  for (int j = 0; j < max_dim; j++) {
    for (int k = 0; k < 10; k++) {
      // We dynamically allocate memory to these two pointers every time we need to
      // create an object of their type. This is because of the OOP approach
      // to lattice reduction.
      IntLatticeBasis<MScal, BScal, NScal, RScal>* basis;
      Reducer<MScal, BScal, NScal, RScal>* red;

      ParamReader<MScal, BScal, RScal> reader;
      std::string name;
      int numlines;
      BMat matrix1;
      unsigned int ln;

      name = "bench/" + prime + "_" + std::to_string(5*(j+1)) + "_" + std::to_string(k);
      reader = ParamReader<MScal, BScal, RScal>(name + ".dat");
      reader.getLines();
      reader.readInt(numlines, 0, 0);
      matrix1.SetDims(numlines, numlines);
      ln = 1;
      reader.readBMat(matrix1, ln, 0, numlines);

      // Dieter reduction before shortest vector search
      tmp = clock();
      basis = new IntLatticeBasis<MScal, BScal, NScal, RScal>(matrix1, numlines);
      red = new Reducer<MScal, BScal, NScal, RScal>(*basis);
      red->redDieter(0);
      die_time[j] += clock() - tmp;
      basis->updateVecNorm();
      vec_length[0] += average(basis->getVecNorm());
      tmp = clock();
      if (!red->shortestVector(L2NORM)) {
        die_fails++;
      }
      sho_die[j] += clock() - tmp;
      delete red;
      //std::cout << "Dieter: " << average(basis->getVecNorm()) << "\n";
      delete basis;

      // LLL reduction before shortest vector search
      tmp = clock();
      basis = new IntLatticeBasis<MScal, BScal, NScal, RScal>(matrix1, numlines);
      red = new Reducer<MScal, BScal, NScal, RScal>(*basis);
      red->redLLLNTL();
      lll_time[j] += clock() - tmp;
      basis->updateVecNorm();
      vec_length[1] += average(basis->getVecNorm());
      tmp = clock();
      if (!red->shortestVector(L2NORM)) {
        lll_fails++;
      }
      sho_lll[j] += clock() - tmp;
      delete red;
      //std::cout << "LLL: " << average(basis->getVecNorm()) << "\n";
      delete basis;

      // BKZ reduction before shortest vector search
      tmp = clock();
      basis = new IntLatticeBasis<MScal, BScal, NScal, RScal>(matrix1, numlines);
      red = new Reducer<MScal, BScal, NScal, RScal>(*basis);
      red->redBKZ();
      bkz_time[j] += clock() - tmp;
      basis->updateVecNorm();
      vec_length[2] += average(basis->getVecNorm());
      tmp = clock();
      if (!red->shortestVector(L2NORM)) {
        bkz_fails++;
      }
      sho_bkz[j] += clock() - tmp;
      delete red;
      //std::cout << "BKZ: " << average(basis->getVecNorm()) << "\n";
      delete basis;
    }
  }

  std::cout << "ALL THE RESULTS ARE NUMBERED IN TERMS OF SYSTEM CLOCK TICKS\n";
  std::cout << "          ";
  int width1 = getWidth(die_time, max_dim, "Dieter", total_times, 0);
  int width2 = getWidth(lll_time, max_dim, "LLL", total_times, 1);
  int width3 = getWidth(bkz_time, max_dim, "BKZ", total_times, 2);
  int width4 = getWidth(sho_die, max_dim, "SV Dieter", total_times, 3);
  int width5 = getWidth(sho_lll, max_dim, "SV LLL", total_times, 4);
  int width6 = getWidth(sho_bkz, max_dim, "SV BKZ", total_times, 5);
  std::cout << std::endl;

  std::cout << "Total time" << std::setw(width1) << total_times[0]
    << std::setw(width2) << total_times[1]
    << std::setw(width3) << total_times[2]
    << std::setw(width4) << total_times[3]
    << std::setw(width5) << total_times[4]
    << std::setw(width6) << total_times[5] << std::endl;
  for (int i = 0; i < max_dim; i++) {
    std::cout << "Dim " << std::setw(6) << (i+1)*5 
      << std::setw(width1) << die_time[i] 
      << std::setw(width2) << lll_time[i] 
      << std::setw(width3) << bkz_time[i] 
      << std::setw(width4) << sho_die[i] 
      << std::setw(width5) << sho_lll[i] 
      << std::setw(width6) << sho_bkz[i] 
      << std::endl;
  }
  std::cout << "Fails     "
    << std::setw(width1) << die_fails 
    << std::setw(width2) << lll_fails 
    << std::setw(width3) << bkz_fails 
    << std::endl;

  std::cout << std::fixed << std::setprecision(2) << "Averages: " << std::setw(width1) << vec_length[0]/vec_length[1]
    << std::setw(width2) << 1.0 << std::setw(width3) << vec_length[2]/vec_length[1]
    <<std::endl;

  std::cout << "Total time: " << (double)(clock()-timer)/(CLOCKS_PER_SEC*60) << " minutes\n";
  
  return 0;
}

This example first showcases the usage of the Reducer class. This class is one that is given a LatticeTester::IntLatticeBasis and then performs various algorithms on it when its methods are called. The methods this class implements perform what we call "reductions". Reductions are algorithms that reduce, in one way or another, the length of the vectors in the basis stored in the IntLatticeBasis. This example calls most of them, and the code bellow links to the documentation of these methods.

The program tests three reductions (Dieter, LLL and BKZ) in two ways. First, it performs it and times the execution of the reduction algorithm itself. this is what is shown in the first 3 columns of the results. The program then perform the "Shortest Vector" reduction, which is the search for the shortest non-zero vector in the lattice (see Background). This search is particularly costly so reducing the lattice basis first usually gains time. The next 3 colums show the execution times for the shortest vector reduction depending on the reduction algorithm used first. Finally, the example also records the number of failures of the shortest vector search for each algorithms. Below is an example output for this example.

ALL THE RESULTS ARE NUMBERED IN TERMS OF SYSTEM CLOCK TICKS
            Dieter    LLL     BKZ   SV Dieter     SV LLL     SV BKZ
Total time 7479736 804050 2414321 11960009667 2665878917 2444318476
Dim      5    3889    873     945         634        583        579
Dim     10   25622   3104    4025        3012       2603       2582
Dim     15   52247   6485   10449        8268       6081       6023
Dim     20   94343  12015   23153       20410      12513      12014
Dim     25  137098  22926   48952      262480      36137      29878
Dim     30  195888  30963   87739      604659     141528     105142
Dim     35  350096  44862  149397     9703739    1469959     968583
Dim     40  468672  54571  176943    28913921    5581257    3571159
Dim     45  619861  80332  229724   607680675   66124526   53250411
Dim     50  839252  98698  269042  1260636786  110130393  102112537
Dim     55 1119413 125894  364620  2351365585  186791907  204776212
Dim     60 1591436 120304  420965  3423588351  416827286  371013095
Dim     65 1981919 203023  628367  4277221147 1878754144 1708470261
Fails           14      2       2
Total time: 284.743 minutes

Construction figures of merit

This examples shows how it is possible to use LatticeTester to compute a variety of figures of merit. This example uses a few different tools that have not been presented before: LatticeTester::BasisConstruction as a way to build projections of a lattice, LatticeTester::CoordinateSets, a namespace containing classes to create indices sets and LatticeTester::Weights and its subclasses that ease the weighting of different projections in a figure of merit.

#define NTL_TYPES_CODE 2

#include <iostream>

#include "latticetester/Types.h"
#include "latticetester/IntLatticeBasis.h"
#include "latticetester/Reducer.h"
#include "latticetester/ParamReader.h"

// Application specific headers
#include "latticetester/NormaBestLat.h"
#include "latticetester/NormaBestBound.h"
#include "latticetester/CoordinateSets.h"
#include "latticetester/UniformWeights.h"
#include "latticetester/BasisConstruction.h"

using namespace LatticeTester;

int main() {
  int min_dim = 0, max_dim = 10;
  ParamReader<MScal, BScal, RScal> reader("./44matrixEx.dat");
  reader.getLines();
  BMat matrix(max_dim,max_dim);
  unsigned int ln = 0;
  reader.readBMat(matrix, ln, 0, max_dim);
  IntLatticeBasis<MScal, BScal, NScal, RScal> lat_basis(matrix, max_dim);
  double merit1 = 1.0, merit2 = 1.0;

  // The variables specific to the construction of a figure of merit
  UniformWeights weights(1.0); // This just puts a weight of 1 to everything
  BasisConstruction<BScal> constructor; // Computes projections basis
  IntLatticeBasis<MScal, BScal, NScal, RScal> proj_basis(max_dim); // To store projections
  // CoordinateSets namespace contains classes to create iterators on sets of coordinates
  CoordinateSets::FromRanges coord(min_dim+1, max_dim, min_dim, max_dim-1);

  // For loop on the iterator built previously
  for(auto it = coord.begin(); it != coord.end(); it++){
    // Computing the projection
    constructor.ProjectionConstruction(lat_basis, proj_basis, *it);

    proj_basis.updateVecNorm();
    proj_basis.sort(0);
    Reducer<MScal, BScal, NScal, RScal> red(proj_basis);
    red.redBKZ();
    red.shortestVector(L2NORM);
    double shortest = NTL::conv<double>(red.getMinLength());

    // Instanciating the normalizers
    // The prefered way of doing this is descibed in Normalizer documentation
    RScal log_density=-log(abs(NTL::determinant(proj_basis.getBasis())));
    Normalizer<RScal>* norma = new NormaBestLat<RScal>(log_density, max_dim);

    // Computing the figure of merit for this projection
    double merit = weights.getWeight(*it) * shortest/norma->getBound((*it).size());
    // Testing if it is the minimum as of now
    if (merit < merit1) merit1 = merit;
    delete norma;
    norma = new NormaBestBound<RScal>(log_density, max_dim);
    merit = weights.getWeight(*it) * shortest/norma->getBound((*it).size());
    if (merit < merit2) merit2 = merit;
    delete norma;
  }

  std::cout << "Figure of merit with BestLat: " << merit1 << "\n";
  std::cout << "Figure of merit with BestBound: " << merit2 << std::endl;
  std::cout << "Figures of merit are different for different normalizers,"
    " weights and projections choices\n";

  return 0;
}

Note that this example is fairly short, which stands out from the other examples, but also from what we would expect from a typical C++ program. Only a few more lines would be needed to make this program read a file name from the command line to perform the computation of the same figure of merit on different matrices.

The first new class seen here is LatticeTester::UniformWeights. This is one of the few classes that inherit from the Weights class stated before. The base class only specifies an interface and the subclasses LatticeTester::UniformWeights, LatticeTester::ProductWeights, LatticeTester::ProjectionDependentWeights and LatticeTester::PODWeights are implementations of weighting classes. These classes are classes that can assign different weights to different projections of a lattice when computing a figure of merit. Typically, these weights only have to be multiplied to the value computed for a projection by specifying the projection to the object. In the case of this example, uniform weights of value 1 are used. This multiplies 1 to every figure of merit, which does nothing. But using other more sophisticated weights would only change the construction process for them and not the actual usage.

The next new thing going on is the usage of the ProjectionConstruction method of the BasisConstruction class. This method is aptly named, as it simply constructs a projection, specified by the third argument, from the first lattice argument and puts it into the second lattice argument. To use this method, it is recommended to pair it with one of the CoordinateSets. These class can be modified to generate coordinate subsets from a list of coordinates, generally the lattice coordinates. From instances of these classes, it is possible to obtain an iterator to perform a loop over the coordinates sets as is done in the example.

The last thing going on is the usage of some Normalizer classes. LatticeTester contains a few classes implementing a normalizer. They are all subclasses of the Normalizer class and can all be instanciated as specified in the documentation of that class. To use this class, it suffices to divide the length of the shortest vector in the lattice by the bound in the dimension of that vector obtained with getBound(dim). If the normalizer has correctly been instanciated, the obtained number should be a mesure rescalled between 0 and 1.