Tutorial and Library Usage

Most use cases of LatMRG should be covered by the executable program, but LatMRG is also distributed as a library to easily expand its functions.

You might want to:

• Perform tests in a sequence or on subsets that we do not provide
• Test unimplemented forms of generators
• Implement new tests and figures of merit With some knowledge of the C++ programming language, it is possible to both expand the functionnalities of LatMRG and to use it as a library to write your own programs.

This section first presents the main classes of the library and how to expand them. We then provide a few programming guidelines to expand the software provided in LatMRG. Finally, we present a few examples of its usage as a library.

Classes of LatMRG

We present the main classes of LatMRG. This will not cover the details of those classes, which is available in their respective documentation.

Types in LatMRG

If you browse the source code, you will notice that a lot of classes are template classes. This is because the arithmetic can be done with a variable level of precision depending on the usage. Template classes feature readily available template instantiation with relevant types and types combinations in the library.

For integers, types we use are fixed width 64 bits integers int64_t and the arbitrary precision integers of NTL ZZ. For floating point numbers, the template parameters types can be double or RR from NTL. Choosing standard types int64_t and double makes the program perform much faster because of the arithmetic. But they have a limited precision. This is specially important for integers: lattices basis need to be stored exactly for the program to work properly. If you think you might need to store a number greater than 2^63-1, it is best to use arbitrary precision integers.

This topic is discussed more in length latter.

MRG Representation

The most important feature of LatMRG is its capacity to represent MRG random number generators and their lattices. The library features two different classes in this regard, depending on the use case.

LatMRG::MRGLattice is the main class to do so. This class allows the the storage of a MRG's parameters (a vector of multipliers, a modulo and an order) and also the reprensentation of a lattice basis for this generator. This class also has an overridable interface to build the basis of the generator lattice for an arbitrary dimension.

The other class to store MRG generators is the LatMRG::MRGComponent class. Just like MRGLattice, this class stores the components of a MRG generator, but it cannot store a lattice basis. This is useful when you want to avoid having to store a heavy object only for generators componenets. This class also bundles a few utility function that can, for example, check if the components stored are that of a full period MRG.

MRGLattice is used as the base class for other MRG generator types classes. Combined generators represented in LatMRG::ComboLattice, MWC generators in LatMRG::MWCLattice and LatMRG::AWCSWBLattice and even MMRG generators in LatMRG::MMRGLattice. Since most generators have an equivalence with MRG, it is practical to just define them with a constructor that initializes the underlying MRGLattice correctly. For example, the next few lines of code (and a few more declaration in the class body) are what initializes a MWCLattice with

\begin{align} x_n & = (e_1 x_{n-1} + \cdots + e_k x_{n-k} + c_{n-1})d\ \mathrm{mod} \ b, \\ c_n & = \lfloor (e_0 x_n + e_1 x_{n-1} + \cdots + e_k x_{n-k} + c_{n-1} )/b \rfloor, \\ u_n & = \sum_{i=1}^\infty x_{n+i-1} b^{-i}. \end{align}

The resulting object can then be used in any function working on MRGLattices seamlessly.

template<typename Int>
  Int LCGMod(const Int& b, const NTL::vector<Int>& e){
    Int m(0);
    for(int i = 0; i <= e.length(); i++) {
      m += e[i] * NTL::power(b, i);
    }
    return m;
  }

template<typename Int>
  NTL::vector<Int> LCGCoeff(const Int& b, const NTL::vector<Int>& e){
    Int mult = LCGMod(b,e);
    std::cout << b << "\n";
    Int a = NTL::InvMod(b, mult);
    NTL::vector<Int> coeff;
    coeff.SetLength(2);
    coeff[1] = a;
    return coeff;
  }

template<typename Int, typename Dbl>
  MWCLattice<Int, Dbl>::MWCLattice(const Int & b, const IntVec & e, int k):
    MRGLattice<Int, Dbl>(LCGMod(b, e), LCGCoeff(b,e), 1, 1, FULL)
{
  m_MWCmod = b;
  m_MWCorder = k;
  m_eCoef.SetLength(k+1);
  for (int i = 0; i < k+1; i++)
    m_eCoef[i] = e[i];
}

Testing and Reducing Lattices

Most of the reduction functions available in LatMRG come from the LatticeTester library. By using this library, it is possible to

• Compute the dual of an arbitrary basis
• Perform BKZ, LLL and pairwise reduction of a lattice
• Find the shortest non-zero vector in a lattice
• Normalize the length of a short lattice vector

LatMRG mainly implements two things, buiding up on LatticeTester

• Projections sets, in a way that is relevant to testing a random number generator
• Figures of Merit computations based on the shortest vector length or on the spectral test.

LatMRG::Projections is the class representing projections. It can be considered as a set \(\mathcal{I}\) of sets of indices and can be iterated over to obtain those sets of indices. Once objects of this class have been initialized, they can be used as iterators. This pairs with the buildProjection method inherited from LatticeTester in MRGLattice.

Projections proj(a,b,c);
MRGLattice lat(m, a, n, k, latt);
lat.buildBasis(n);
while(!proj->end()) {
 LatticeTester::IntLattice proj_lat;
 lat.buildProjection(&proj_lat, proj->next());
 ...
}

The Test.h file provides with functions that wrap LatticeTester to either reduce a lattice or compute a form on merit on it. Once MRGLattice objects have been initialized, you simply need to build the lattice basis for different projections and call functions from this file on them.

Programming LatMRG

In this section, we will present how to use LatMRG as a library and provide guidelines on how to expand the software.

Working with types

The first thing anyone programming with LatMRG should know, is that LatMRG HAS TO perform on different types depending on the use case. Therefore, when programming new functions in LatMRG it is necessary to make sure that they are agnostic the possible types that might be used by the different LatMRG objects. Currently LatMRG can use ZZ from the NTL library, as well as fixed width int64_t integers to represent the generators and their basis. It can also represent floating point numbers with both double and RR types. Note that there is one cavehat to the previous statements: the BKZ reduction method (in LatticeTester) requires that integers are of the ZZ type. This is because we did not implement the BKZ reduction and use the NTL version instead. This version does not operate on long integers.

To work around this problem, LatMRG uses templates for most classes. This can feel problematic since these templates are not intended to work with most types ut only a few specific ones. This is mainly meant to reduce code duplication, but also gives us the flexibility to eventually change NTL for another library and not have to rewrite most of our code base. This is also intended to modify the old version of LatMRG that used compile time flags to determine the types.

Template classes in the software look like this:

template<typename Integ, typename Float> class LatMRGClass {
  typedef Integ Int;
  typedef Float Dbl;
  ...
};
extern template class LatMRGClass<std::int64_t, double>;
extern template class LatMRGClass<NTL::ZZ, double>;
extern template class LatMRGClass<NTL::ZZ, NTL::RR>;

The first thing to note are the typedefs. Having them means that it is possible to interract with the class and its types and still write types agnostic code by referring to typename LatMRGClass::Int. The other thing to note is that the library instanciates all its templated classes with the types we support. This is meant to reduce compile time when using the library and helps verify that supported types works.

Remarks

If you manipulate integers that are bigger than 2^32, the result of a multiplication can overflow. Multiplications will occur when building a lattice basis.

Adding new types of generators

Although it shouldn't be necessary to add new types of generators in the the software, it is possible that some users would want to include classes to represent specific parameter combinations for certain generator kinds and specialize the lattice construction for those. For all its operation on generators, LatMRG interracts with the base class MRGLattice. This class inherits from IntLattice in LatticeTester and has quite a few functions that can be specialized in subclasses.

To specialize the basis construction, all subclasses for MRGLattice can reimplement the virtual methods buildBasis(int) and incDim(). The first method is intended to build a basis of dimension specified as argument, and the second one increases the basis dimension by one.

The other main function you might want to specialize in MRGLattice is the toString() function. This function returns a string that describes the generator represented by the lattice. There curently is no standard format to be returned by this method and it is left to the user discretion to choose what information is important. For example, for MRGLattice, this only prints the coefficients as

a1 = x1
...
ak = xk

but it could be possible to create a class that represents a MRG with specific choice of coefficients. For example, if the coefficients are chosen as the sum of powers of primes p1, ..., pj one could change the method to print a1 = x1 = p1^e1 + ... + pj^ej.

Expanding the executable

One of the reasons you might want to use LatMRG is to search for generators. The main tool LatMRG provides for this is its executable, but this means expanding the search functionnality of the software is not as easy as writing a function to generate vectors \((a_1, \ldots, a_k)\) given a strategy. There are two options to search for custom new generators with LatMRG.

First, you can write some sort of script using the library functions to handle the lattices and make the computations. In that case, most, if not all, the logic would have to be written by you. If you want a customizable program, this might get complicated for what should be a "simple" task.

Your other option is to modify the executable of LatMRG to search generators as you need them and apply tests as it can already do. The intention of the executable is to be robust to different types specifications and easily enable users to modify it. We focus on this option here.

To search for generators, the program calls the following function:

template<typename Lat> struct SeekMain {
  typedef typename Lat::Int Int;
  typedef typename Lat::Dbl Dbl;
  typedef NTL::vector<Int> IntVec;
  typedef NTL::matrix<Int> IntMat;

  ConfigSeek<Int, Dbl> conf;

  ...

  int Seek (Lat* (*nextGenerator)(ConfigSeek<Int, Dbl>&) )
  {
    if (!conf.gen_set) {
      std::cerr << "No generator set for in seek tag. Aborting.\n";
      return 1;
    }
    if (!(conf.test_set)) {
      std::cerr << "No test set for in seek tag. Aborting.\n";
      return 1;
    }
    if (!conf.proj_set) {
      std::cerr << "No projections set for in seek tag. Aborting.\n";
      return 1;
    }
    // Initializing values
    // Dynamically allocated objects
    timer.init();

    int old = 0;
    // Launching the tests
    if (conf.progress) {
      old = print_progress(-1);
    }
    MeritList<Lat> bestLattice(conf.max_gen, conf.best);
    do {
      if (lat != NULL) delete lat;
      lat = nextGenerator(conf);
      if (lat == NULL) continue;
      bestLattice.add(test_seek(*lat, conf));
      conf.num_gen++;
      conf.currentMerit = bestLattice.getMerit();
      if (conf.progress) old = print_progress(old);
    } while (!timer.timeOver(conf.timeLimit) && lat);
    std::cout << "\r                                                                                                          \r";
    printResults(bestLattice);
    return 0;
  }
}; // end struct SeekMain

This function takes a pointer to a function as an argument. This function passed as an argument is used at each step to search and return the next generator to test. Following this logic, there is only need to implement another function to pass as nextGenerator and to make it such that the program can pass it to Seek().

nextGenerator Functions

Accessing the New Function

This means that searching generators with a new method can be done by implementing this method in a new function and modifying the executable for this function to be passed to the search method.