LatMRG::IntPrimitivity< Int > Class Template Reference

This class deals with primitive roots and primitive elements modulo an integer. More...

#include <latmrg/IntPrimitivity.h>

Public Member Functions
	IntPrimitivity ()
	IntPrimitivity (const IntFactorization< Int > &f, const Int &p, long e=1)
	Constructor fixing the modulus of congruence as \(m = p^e\). More...
long	getE ()
	Gets the value of \(e\). More...
IntFactorization< Int >	getF ()
	Gets the value of \(f\). More...
Int	getP ()
	Gets the value of \(p\). More...
bool	isPrimitiveElement (const Int &a) const
	Returns true if \(a\) is a primitive element modulo \(p^e\). More...
bool	isPrimitiveElement (const IntVec &V, int k) const
	Returns true if \((-1)^{k+1}V[k]\) is a primitive element modulo \(p^e\). More...
void	setF (const IntFactorization< Int > &f)
	Sets the value of \(f\). More...
void	setpe (const Int &p, long e)
	Sets the value of \(p\), \(e\) and \(m = p^e\). More...
std::string	toString () const
	Returns this object as a string. More...

Private Types
typedef NTL::vector< Int >	IntVec

Private Attributes
long	m_e
	Exponent used to compute the modulus \(m = p^e\). More...
IntFactorization< Int >	m_f
	Factorization of \(p-1\). More...
Int	m_m
	The modulus \(m = p^e\). More...
Int	m_p
	Prime number \(p\). More...

Detailed Description

template<typename Int>
class LatMRG::IntPrimitivity< Int >

This class deals with primitive roots and primitive elements modulo an integer.

Let \(a\), \(e\) and \(p\) be integers, with \(p\) a prime number. Assume also that \(a\) and \(m=p^e\) are relatively prime. The smallest positive integer \(\lambda(m)\) for which \(a^{\lambda}= 1 \ \mod\ m \) is called the order of \(a\) modulo \(m\). Any \(a\) which has the maximum possible order for a given \(m\) is called a primitive root modulo \(m\). For the following important cases, the value of the order for given \(m\) is [rKNU98a] :

\begin{align*} \lambda(2^e) & = 2^{e-2}, \qquad e > 2 \\ \lambda(p^e) & = p^{e-1}(p - 1), \qquad p > 2. \end{align*}

Member Typedef Documentation

IntVec

template<typename Int >

typedef NTL::vector<Int> LatMRG::IntPrimitivity< Int >::IntVec

private

Constructor & Destructor Documentation

IntPrimitivity() [1/2]

template<typename Int >

LatMRG::IntPrimitivity< Int >::IntPrimitivity

(

)

IntPrimitivity() [2/2]

template<typename Int >

LatMRG::IntPrimitivity< Int >::IntPrimitivity	(	const IntFactorization< Int > &	f,
		const Int &	p,
		long	e = 1
	)

Constructor fixing the modulus of congruence as \(m = p^e\).

The argument \(f\) must contain the prime factor decomposition of \(p-1\) and its inverse factors.

Member Function Documentation

getE()

template<typename Int >

long LatMRG::IntPrimitivity< Int >::getE ( )

inline

Gets the value of \(e\).

getF()

template<typename Int >

IntFactorization<Int> LatMRG::IntPrimitivity< Int >::getF ( )

inline

Gets the value of \(f\).

getP()

template<typename Int >

Int LatMRG::IntPrimitivity< Int >::getP ( )

inline

Gets the value of \(p\).

isPrimitiveElement() [1/2]

template<typename Int >

bool LatMRG::IntPrimitivity< Int >::isPrimitiveElement

(

const Int &

a

)

const

Returns true if \(a\) is a primitive element modulo \(p^e\).

This method uses the prime factor decomposition of \(p-1\) and its inverse factors.

isPrimitiveElement() [2/2]

template<typename Int >

bool LatMRG::IntPrimitivity< Int >::isPrimitiveElement	(	const IntVec &	V,
		int	k
	)		const

Returns true if \((-1)^{k+1}V[k]\) is a primitive element modulo \(p^e\).

This method uses the prime factor decomposition of \(p-1\) and its inverse factors.

setF()

template<typename Int >

void LatMRG::IntPrimitivity< Int >::setF ( const IntFactorization< Int > &  f )

inline

Sets the value of \(f\).

setpe()

template<typename Int >

void LatMRG::IntPrimitivity< Int >::setpe	(	const Int &	p,
		long	e
	)

Sets the value of \(p\), \(e\) and \(m = p^e\).

toString()

template<typename Int >

std::string LatMRG::IntPrimitivity< Int >::toString

(

)

const

Returns this object as a string.

Member Data Documentation

m_e

template<typename Int >

long LatMRG::IntPrimitivity< Int >::m_e

private

Exponent used to compute the modulus \(m = p^e\).

m_f

template<typename Int >

IntFactorization<Int> LatMRG::IntPrimitivity< Int >::m_f

private

Factorization of \(p-1\).

m_m

template<typename Int >

Int LatMRG::IntPrimitivity< Int >::m_m

private

The modulus \(m = p^e\).

m_p

template<typename Int >

Int LatMRG::IntPrimitivity< Int >::m_p

private

Prime number \(p\).

---

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

• include/latmrg/IntPrimitivity.h