LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER > Class Template Reference

Cyclic group. More...

#include <CyclicGroup.h>

Inherits LatBuilder::Traversal::Policy< CyclicGroup< COMPRESS, TRAV, ORDER >, TRAV >.

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

Public Types
typedef size_t	size_type
typedef Modulus	value_type
typedef TRAV	Traversal
	Traversal type.

Public Member Functions
	CyclicGroup (Traversal trav=Traversal())
	Constructor for an empty group.
	CyclicGroup (Modulus base, Level power, Traversal trav=Traversal())
	Constructor for the cyclic group of integers modulo \(b^m\), where \(b\) is a prime base. More...
template<class TRAV2 >
	CyclicGroup (const CyclicGroup< COMPRESS, TRAV2, ORDER > &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	base () const
	Returns the base of the group modulus.
Modulus	power () const
	Returns the power of the base of the group modulus.
Modulus	fullSize () const
	Returns the cardinality of the full group. More...
Modulus	size () const
	Returns the cardinality of the group part specified by COMPRESS.
Modulus	modulus () const
	Returns the modulus \(b^m\) of the cyclic group.
Modulus	generator () const
	Returns the generator \(g\) for the group.
value_type	operator[] (size_type i) const
	Returns the element at index i.
CyclicGroup< COMPRESS, TRAV,!ORDER >	inverse () const
	Returns the group generated by the inverse generator.
CyclicGroup	subgroup (Level level) const
	Returns the subgroup at level level.

Static Public Member Functions
static constexpr LatBuilder::Compress	compress ()
static std::string	name ()
static Modulus	smallestGenerator (Modulus base, Level power, bool checkPrime=true)
	Returns the smallest generator for the group of cyclic integers modulo \(b^m\). More...

Friends
template<LatBuilder::Compress , class , GroupOrder >
class	CyclicGroup
class	CyclicGroup< COMPRESS, TRAV,!ORDER >

Detailed Description

template<Compress COMPRESS = Compress::NONE, class TRAV = CyclicGroupTraversal, GroupOrder ORDER = GroupOrder::DIRECT>
class LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER >

Cyclic group.

Cyclic group \(\{ 1, g, g^2, \dots, g^{\varphi(b^m) - 1} \}\) of integers modulo \(b^m\), where \(b\) is a prime base, \(g\) is the generator of the group, and \(\varphi\) is Euler's totient function.

The generator of the group is computed by the class constructor.

Template Parameters

COMPRESS

Compression type. If Compress::SYMMETRIC, only the first half of the group is considered and an element value of \(a\) is mapped to \(\min(a, b^m - a)\).

Remarks

In base 2, the group is the union of two cyclic groups rather than a single cyclic group.

Examples:

tutorial/GenSeqCyclicGroup.cc, and tutorial/MeritSeqFastCBC.cc.

Constructor & Destructor Documentation

template<Compress COMPRESS, class TRAV , GroupOrder ORDER>

LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER >::CyclicGroup	(	Modulus	base,
		Level	power,
		Traversal	trav = Traversal()
	)

Constructor for the cyclic group of integers modulo \(b^m\), where \(b\) is a prime base.

Parameters

base	Prime base \(b\).
power	Power \(m\) of the base.
trav	Traversal instance.

References LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER >::fullSize(), LatBuilder::intPow(), LatBuilder::modularPow(), LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER >::modulus(), and LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER >::smallestGenerator().

Member Function Documentation

template<Compress COMPRESS = Compress::NONE, class TRAV = CyclicGroupTraversal, GroupOrder ORDER = GroupOrder::DIRECT>

Modulus LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER >::fullSize ( ) const

inline

Returns the cardinality of the full group.

Remarks

If COMPRESS is Compress::NONE, this is the same as size().

References LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER >::base(), and LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER >::modulus().

Referenced by LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER >::CyclicGroup().

template<Compress COMPRESS, class TRAV , GroupOrder ORDER>

Modulus LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER >::smallestGenerator ( Modulus  base, Level  power, bool  checkPrime = true  )

static

Returns the smallest generator for the group of cyclic integers modulo \(b^m\).

Parameters

base	\(b\)
power	\(m\)
checkPrime	If true, checks if the base is actually prime.

The algorithm is described in [2] .

References LatCommon::IsPrime(), LatBuilder::modularPow(), and LatBuilder::primeFactors().

Referenced by LatBuilder::GenSeq::CyclicGroup< COMPRESS, TRAV, ORDER >::CyclicGroup().

---

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

• latbuilder/include/latbuilder/GenSeq/CyclicGroup.h