Search for a good generating vector involves enumerating the values its components can take.

The representation of search spaces in Lattice Builder is based on sequences of possible values for the components of the generating vector.

See also: GenSeq

Coprime Integers

In the general case, one normally needs to enumerate all integers that are relatively prime with the number of points \(n\) in the lattice point set. This is implemented by the class template GenSeq::CoprimeIntegers. Some figures of merit are invariant under the transformation \(a \mapsto n - a\) where \(a\) is any component of the generating vector. When using such a symmetric figure of merit, redundancy can be avoided by enumerating only the first half of the sequence of integers coprime with \(n\), i.e. by compressing the search space. In that case, we pass Compress::Symmetric as the first template argument to GenSeq::CoprimeIntegers:

typedef GenSeq::CoprimeIntegers<Compress::SYMMETRIC> HalfSeq;

Otherwise, we pass Compress::None:

typedef GenSeq::CoprimeIntegers<Compress::NONE> WholeSeq;

These concepts are illustrated in tutorial/GenSeqCoprimeIntegers.cc :

   typedef GenSeq::CoprimeIntegers<Compress::NONE> WholeSeq;
   typedef GenSeq::CoprimeIntegers<Compress::SYMMETRIC> HalfSeq;
   for (Modulus n : {7, 8, 12}) {
      std::cout << "lattice size: " << n << std::endl;
      std::cout << "    whole sequence: " << WholeSeq(n) << std::endl;
      std::cout << "     half sequence: " << HalfSeq(n) << std::endl;
   }

The ouput of the above code is:

lattice size: 7
    whole sequence: [1, 2, 3, 4, 5, 6]
     half sequence: [1, 2, 3]
lattice size: 8
    whole sequence: [1, 3, 5, 7]
     half sequence: [1, 3]
lattice size: 12
    whole sequence: [1, 7, 5, 11]
     half sequence: [1, 5]

Random Traversal

Sometimes, as with random Korobov or random CBC construction, it is necessary to randomly select a certain number of elements from a GenSeq::CoprimeIntegers instance. GenSeq::CoprimeIntegers optionally takes a second template arguments that specifies a method of traversal of its values; it defaults to Traversal::Forward which enumerates the values in their original order in the sequence. It can be replaced with Traversal::Random for the above purpose:

typedef Traversal::Random<LFSR113> Trav;

typedef GenSeq::CoprimeIntegers<Compress::SYMMETRIC, Trav> RandomSeq;

The traversal type Traversal::Random also takes a template argument that specifies the type of random generator to use. We use LFSR258 in our example, but any C++11-compliant random engine could be used. Next, a random traversal object must be instantiated with the desired number r of random samples:

Trav trav(r);

Then, the sequence object can be instantiated with the lattice size n, and the traversal object:

RandomSeq seq(n, trav);

A complete example can be found in tutorial/GenSeqRandom.cc :

   typedef Traversal::Random<LFSR113> Trav;
   typedef GenSeq::CoprimeIntegers<Compress::SYMMETRIC, Trav> RandomSeq;
   size_t r = 4; // 4 random samples
   Trav trav(r);
   for (Modulus n : {31, 256}) {
      std::cout << "lattice size: " << n
         << " (" << trav.size() << " random samples)" << std::endl;
      RandomSeq seq(n, trav);
      std::cout << "          sequence: " << seq << std::endl;
      std::cout << "     same sequence: " << seq << std::endl;
      seq.randomGenerator().jump();
      std::cout << "    other sequence: " << seq << std::endl;
   }

The output of the above code is:

lattice size: 31 (4 random samples)
          sequence: [3, 8, 6, 1]
     same sequence: [3, 8, 6, 1]
    other sequence: [15, 7, 13, 15]
lattice size: 256 (4 random samples)
          sequence: [19, 63, 49, 5]
     same sequence: [19, 63, 49, 5]
    other sequence: [123, 59, 111, 119]

Note that GenSeq::Random stores its own copy of the random engine, so that successive iteration over the same random sequence objects yields the same sequence of values. To obtain a different random selection of values, the initial state of the random generator must be changed. The LFSR258 generator exposes a jump() function for this purpose:

seq.randomGenerator().jump();

In some situations, the number r of random samples is not known in advance. In that case, the preferred method is to instantiate the traversal object without passing the argument r, which defaults to infinity, then to add a stopping condition in loops that iterate over the elements of the sequence.

Cylic Groups

In the case where the lattice size \(n\) is an integer power of a prime base, the class template GenSeq::CyclicGroup can be used to enumerate the elements of the cyclic group of integers modulo \(n\) can be enumerated, in the natural group order where the \(i\)-th element is \(g^i \bmod n\), where \(g\) is the group generator. This is useful in particular to perform fast CBC construction. Like GenSeq::CoprimeIntegers, GenSeq::CyclicGroup takes a compression type as the first template argument. This is illustrated in tutorial/GenSeqCyclicGroup.cc :

typedef GenSeq::CyclicGroup<Compress::NONE> WholeSeq;
typedef GenSeq::CyclicGroup<Compress::SYMMETRIC> HalfSeq;
void displaySeq(int base, int power)
{
   std::cout << "lattice size: " << base << "^" << power << std::endl;
   std::cout << "    whole sequence: " << WholeSeq(base, power) << std::endl;
   std::cout << "     half sequence: " << HalfSeq(base, power) << std::endl;
}
int main()
{
   displaySeq(7, 1);
   displaySeq(2, 3);
   displaySeq(3, 2);
   return 0;
}

The output of the above code is:

lattice size: 7^1
    whole sequence: [1, 3, 2, 6, 4, 5]
     half sequence: [1, 3, 2]
lattice size: 2^3
    whole sequence: [1, 5, 7, 3]
     half sequence: [1, 3]
lattice size: 3^2
    whole sequence: [1, 2, 4, 8, 7, 5]
     half sequence: [1, 2, 4]

In the symmetric case, each value \(a\) is mapped to \(\min\{a, n-a\}\).

Vectors of Integer Sequences

Construction algorithms often consider a distinct sequence of possible values for each component of the generating vector. When distinct random selection of sequence elements are required for each coordinate, as with random CBC or plain random constructions; in this case, the initial state of the random generator must be different for each coordinate, as explained in Random Traversal. This functionality is provided by the convenience template class GenSeq::VectorCreator, which automatically calls jump() on the random generator between different coordinates if the traversal method is Traversal::Random.

A vector of dim sequences of type Seq with size parameter n can be created with:

auto vec = GenSeq::VectorCreator<Seq>::create(n, dim);

In most situations when constructing rank-1 lattices, we consider only the value 1 for the first component. For that purpose, we can replace the first integer sequence with a singleton that contains only the value 1 with:

vec[0] = GenSeq::Creator<Seq>::create(n0);

A full example can be found in tutorial/GenSeqVector.cc :

   typedef GenSeq::CoprimeIntegers<Compress::NONE> Seq;
   SizeParam<LatType::ORDINARY> n(7);      // lattice size
   SizeParam<LatType::ORDINARY> n0(2);     // fake lattice size to obtain a single value (1)
   Dimension dim = 3;           // dimension
   auto vec = GenSeq::VectorCreator<Seq>::create(n, dim);
   vec[0] = GenSeq::Creator<Seq>::create(n0);
   std::cout << "lattice size: " << n << std::endl;
   std::cout << "    integer sequences: " << vec << std::endl;

The output of the above code is:

lattice size: 7
    integer sequences: [[1], [1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]]

For random sequence types, the number of random samples can be passed as an additional optional argument to GenSeq::VectorCreator::create():

   n = 31;
   typedef GenSeq::CoprimeIntegers<Compress::NONE, Traversal::Random<LFSR113>> RandomSeq;
   auto randVec = GenSeq::VectorCreator<RandomSeq>::create(n, dim, 5);
   randVec[0] = GenSeq::Creator<RandomSeq>::create(n0, 1); // replace 1st with singleton
   std::cout << "lattice size: " << n << std::endl;
   std::cout << "    random integer sequences: " << randVec << std::endl;

The output of the above code is:

lattice size: 31
    random integer sequences: [[1], [29, 14, 26, 29, 9], [28, 18, 29, 28, 12]]

Distinct random sequences are automatically created.

Extension of the Number of Points

A lattice with \(b^m\) points in dimension \(s\) and generating vector \(\boldsymbol a = (a_1,\dots,a_s)\) can be extended to \(b^{m+1}\) points by appending a \(m+1\)-st digit in base \(b\) to the left of each \(a_j\). It is easy to verify that the original lattice is indeed embedded in the extended lattice. The following instruction shows how to instantiate a sequence of generator values seq that adds a \(m+1\)-st digit in base b, where numPoints = b \(^m\) to the left of the \(m\) digits in base b of the integer gen (which stands for any of the \(a_j\)'s):

GenSeq::Extend<> seq(b * numPoints, numPoints, gen);

In practice, low would be one of the \(a_j\)'s. To add two digits instead of one, the first constructor argument b * numPoints must be replaced with b * b * numPoints. A complete example can be found in tutorial/GenSeqExtend.cc.