LatBuilder::GenSeq::GeneratingValues< LatticeType::POLYNOMIAL, COMPRESS, TRAV > Class Template Reference

Indexed sequence of Polynomials coprime with a specified polynomial modulus. More...

#include <GeneratingValues-PLR.h>

Inherits LatBuilder::Traversal::Policy< GeneratingValues< LatticeType::POLYNOMIAL, COMPRESS, TRAV >, TRAV >.

Classes
struct	RebindTraversal
	Rebinds the traversal type. More...

Public Types
typedef GeneratingValuesTraits< self_type >::Modulus	Modulus
	Modulus type.
typedef GeneratingValuesTraits< self_type >::value_type	value_type
	Value type.
typedef GeneratingValuesTraits< self_type >::size_type	size_type
	Size type.
typedef TRAV	Traversal
	Traversal type.

Public Member Functions
	GeneratingValues (Modulus modulus=(Modulus)(1), Traversal trav=Traversal())
	Constructor. More...
template<class TRAV2 >
	GeneratingValues (const GeneratingValues< LatticeType::POLYNOMIAL, COMPRESS, TRAV2 > &other, Traversal trav=Traversal())
	Cross-traversal copy-constructor.
template<class TRAV2 >
RebindTraversal< TRAV2 >::Type	rebind (TRAV2 trav) const
	Returns a copy of this object, but using a different traversal policy.
Modulus	modulus () const
	Returns the modulus.
size_type	size () const
	Returns the size of the sequence. More...
value_type	operator[] (size_type i) const
	Returns the element at index i.

Static Public Member Functions
static std::string	name ()

Friends
template<LatBuilder::LatticeType , LatBuilder::Compress , class >
class	GeneratingValues

Detailed Description

template<Compress COMPRESS, class TRAV>
class LatBuilder::GenSeq::GeneratingValues< LatticeType::POLYNOMIAL, COMPRESS, TRAV >

Indexed sequence of Polynomials coprime with a specified polynomial modulus.

we note a polynomial by specifing its variable (for example \(T(z)\)), and whenever \(T(z)=\sum_{i=0}^{w} t_{i}z^i \in \mathbb{Z}_{2}[z]\), $T$ stands for the integer \(T = \sum_{i=0}^{w} t_{i}2^i \in \mathbb{N}\).

Let \(P(z) = \prod_{j=1}^{l} p_{j}(z)^{\alpha_{j}}\) such that \(p_{j}(z)\) is irreductible over \(\mathbb{Z}_{2}\), and let \(\varphi(P(z)) = \left | (\mathbb{Z}_{2}[z]/(P(z)))^{*} \right |\). The chinese remainder theorem states that there is an isomorphism between \((\mathbb{Z}_{2}[z]/(P(z)))^{*}\) and \((\mathbb{Z}_{2}[z]/(p_{1}^{\alpha_{1}}(z)))^{*}\times...\times (\mathbb{Z}_{2}[z]/(p_{l}^{\alpha_{l}}(z)))^{*}\)

\begin{eqnarray*} \Psi :\quad &(\mathbb{Z}_{2}[z]/(P(z)))^{*} &&\longrightarrow \quad && (\mathbb{Z}_{2}[z]/(p_{1}^{\alpha_{1}}(z)))^{*}\times...\times (\mathbb{Z}_{2}[z]/(p_{l}^{\alpha_{l}}(z)))^{*}\\ & k(z) &&\longmapsto &&\big(k_{1}(z),...,k_{l}(z)\big) = \big(k(z) \mod p_{1}^{\alpha_{1}}(z),...,k(z) \mod p_{l}^{\alpha_{l}}(z)\big) \\ \end{eqnarray*}

We order elements of \((\mathbb{Z}_{2}[z]/(P(z)))^{*}\) as follows: we identify \(k(z) \in (\mathbb{Z}_{2}[z]/(P(z)))^{*}\) with \(\Psi(k(z)) = \big(k_{1}(z),...,k_{l}(z)\big) \in (\mathbb{Z}_{2}[z]/(p_{1}^{\alpha_{1}}(z)))^{*}\times...\times (\mathbb{Z}_{2}[z]/(p_{l}^{\alpha_{l}}(z)))^{*}\), for which we choose the dictionnary order, with \((\mathbb{Z}_{2}[z]/(p_{j}^{\alpha_{j}}(z)))^{*}\) ordered as follows:

\[ h_{1}(z) <_{p_{j}} h_{2}(z) \quad \text{iff } \left\{ \begin{array}{ll} Q_1 < Q_2 \\ \text{or } Q_1 = Q_2 \text{ and } R_1 < R_2 \end{array} \right. \]

with

\[ \left\{ \begin{array}{ll} h_{1}(z) = p_{j}(z) Q_{1}(z) + R_{1}(z) \\ h_{2}(z) = p_{2}(z) Q_{2}(z) + R_{2}(z) \end{array} \right., \quad \deg(R_{1}(z)),\deg(R_{2}(z)) < \deg(p_{j}(z)) \]

Equivalently, to each \(k(z) \in (\mathbb{Z}_{2}[z]/(P(z)))^{*}\) we assign the index

\[ i_{k(z)} = \sum_{j=1}^{l} (R_{j} + (2^{\deg(p_j(z))}-1)Q_{j}-1) \prod_{g=1}^{j-1} \varphi(p_{g}^{\alpha_{g}}(z)), \]

with

\[ k_{j}(z) = p_{j}(z) Q_{j}(z) + R_{j}(z), \quad \deg(R_{j}(z)) < \deg(p_{j}(z)) \]

If \(i = \sum_{j=1}^{l} r_{j} \prod_{g=1}^{j-1}\varphi(p_{g}^{\alpha_{g}}(z)) \in \{0,\dots, \varphi(P(z))-1\}\) is an index, \((k_1(z),\dots,k_l(z))\) can be computed using the formula

\[ k_{j}(z) = p_j(z) Q_j(z) + R_j(z) \]

with

\[ \left\{ \begin{array}{ll} Q_{j} = \left \lfloor \frac{r_{j}}{2^{\deg(p_{j})}-1} \right \rfloor\\ R_{j} = r_{j} \mod (2^{\deg(p_{j})}-1) +1 \end{array} \right. \]

Constructor & Destructor Documentation

GeneratingValues()

template<Compress COMPRESS, class TRAV >

LatBuilder::GenSeq::GeneratingValues< LatticeType::POLYNOMIAL, COMPRESS, TRAV >::GeneratingValues	(	Modulus	modulus = (Modulus)(1),
		Traversal	trav = Traversal()
	)

Constructor.

Parameters

modulus	modulus relative to which all numbers in the sequence are coprime.
trav	Traversal instance.

References LatticeTester::gcd(), LatBuilder::intPow(), and NTL::vector< T >::size().

Member Function Documentation

size()

template<Compress COMPRESS, class TRAV >

size_type LatBuilder::GenSeq::GeneratingValues< LatticeType::POLYNOMIAL, COMPRESS, TRAV >::size ( ) const

inline

Returns the size of the sequence.

The size is the value of Euler's totient function.

---

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

• include/latbuilder/GenSeq/GeneratingValues-PLR.h