|
class | AWCSWBLattice |
| This class represents the lattice associated with either an AWC or a SWB random number generator. More...
|
class | ComboLattice |
| This class represents a combined MRG. More...
|
class | FlexModInt |
| The FlexModInt class permits one to use the NTL functions that work on integers, vectors, and polynomials over Z_p (with arithmetic modulo p) using the flexible type Int for the modulus and coefficients. More...
|
class | FlexModInt< NTL::ZZ > |
class | FlexModInt< std::int64_t > |
class | IntFactor |
| An object of this class represents a factor in the decomposition of a positive integer. More...
|
class | IntFactorization |
| Represents the factorization of an arbitrary positive integer, usually into prime factors, but not always. More...
|
class | LCGComponent |
| This class offers tools to test the period of an LCG recurrence modulo \(m\), of the form. More...
|
class | LCGLattice |
| This class handles lattices that are produced by linear congruential generators (LCGs). More...
|
class | MixmaxMMRG |
| This class is used to manipulate easily MMRG of Mixmax types as described by Savvidy [CITE PAPER]. More...
|
class | MMRGLattice |
class | Modulus |
| This class offers a few tools to work with a modulus m. More...
|
class | MRGComponent |
| This class offers tools to verify if an MRG recurrence or order \(k\) modulo \(m\), of the form. More...
|
class | MRGLattice |
| This subclass of IntLatticeExt defines an MRG lattice and is similar to Rank1Lattice, but constructs lattices associated with multiple recursive generators (MRGs) with modulus m, order k, and vector of multipliers a = (a_1, . More...
|
class | MRGLatticeLac |
| This subclass of MRGLattice constructs and handles lattice bases built from MRGs as in MRGLattice, but with arbitrary lacunary indices that can be spaced very far apart. More...
|
class | MWCComponent |
| This class represents the lattice associated to a Multiply-with-carry (MWC) random number generator. More...
|
|
enum | PrimeType { PRIME
, PROB_PRIME
, COMPOSITE
, UNKNOWN
} |
| Indicates whether an integer is prime, probably prime, composite, or its status is unknown (or we do not care). More...
|
enum | GenType {
LCG
, MRG
, MMRG
, MWC
,
COMBO
} |
| Types of generators handled by LatMRG. More...
|
enum | LatticeType { FULL
, RECURRENT
, ORBIT
, PRIMEPOWER
} |
| Indicates whether to analyze the lattice generated by all possible states, or a sub-lattice generated by the set of recurrent states or by a sub-cycle of the generator. More...
|
enum | DecompType {
DECOMP
, DECOMP_WRITE
, DECOMP_READ
, DECOMP_PRIME
,
NO_DECOMP
} |
| Given an integer \(x\), this type indicates what to do about the decomposition of \(x\) in its prime factors, in the class IntFactorization. More...
|
enum | ImplemCond {
NO_COND
, APP_FACT
, POWER_TWO
, EQUAL_COEF
,
ZERO_COEF
} |
| Indicates which type of conditions are imposed on the coefficients \(a_i\) of a recurrence. More...
|
enum | SearchMethod { EXHAUST
, RANDOM
} |
| Indicates the search method used to find good multipliers \(a_i\). More...
|
enum | LacunaryType { NONE
, SUBVECTOR
, ARBITRARYINDICES
} |
| Indicates the type of lacunary projection used in MMRGLattice: More...
|
|
template<typename Int, typename Real> |
MRGLattice< Int, Real > * | getLatCombo (std::vector< MRGPeriod< Int > * > &comp, int maxDim) |
| This function computes and returns a MRGLattice that is the lattice of the combination of generators described in the MRGPeriods in the vector comp.
|
template MRGLattice< std::int64_t, double > * | getLatCombo (std::vector< MRGPeriod< std::int64_t > * > &comp, int maxDim) |
template MRGLattice< NTL::ZZ, double > * | getLatCombo (std::vector< MRGPeriod< NTL::ZZ > * > &comp, int maxDim) |
static std::string | toStringPrimeType (PrimeType prime) |
| The following are functions for printing the enum constants in this module.
|
static std::string | toStringGenType (GenType gen) |
static std::string | toStringLatticeType (LatticeType lat) |
static std::string | toStringDecompType (DecompType decomp) |
static std::string | toStringImplemCond (ImplemCond implem) |
static std::string | toStringSearchMethod (SearchMethod searchm) |
static std::string | toStringLacunaryType (LacunaryType lacunary) |
template<typename Int> |
static void | setModulusIntP (const Int &m) |
| Sets to m the modulus used by NTL for its IntP calculations.
|
template<typename Int> |
static void | findPrime (int64_t e, int64_t s, bool facto, std::ostream &fout, const int64_t RMtrials=200) |
| Finds and prints the \(s\) largest prime integers \(m < 2^e\).
|
template<typename Int> |
static void | findPrime (int64_t k, int64_t e, int64_t s, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials=200) |
| Finds the \(s\) largest prime integers \(m<2^e\) for which \(r = (m^k-1)/(m-1)\) is also prime.
|
template<typename Int> |
static void | findPrime (int64_t k, int64_t e, int64_t c1, int64_t c2, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials=200) |
| Finds all integers \(m\), in \(2^e + c_1 \le m \le 2^e + c_2\), such that \(m\) and \(r = (m^k-1)/(m-1)\) are prime.
|
template<typename Int> |
static void | findPrime (int64_t k, int64_t e, int64_t s, const Int &S1, const Int &S2, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials=200) |
| This is the general purpose function, called by the other ones.
|
static void | writeHeader (int64_t k, int64_t e, int64_t c1, int64_t c2, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials=200) |
| Writes the search parameters to the stream fout.
|
template<typename Int> |
static void | nextM (Int &m) |
template<typename Int> |
void | findPrime (int64_t k, int64_t e, int64_t s, const Int &S1, const Int &S2, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials) |
| This is the general purpose function, called by the other ones.
|
template<typename Int> |
void | findPrime (int64_t e, int64_t s, bool facto, std::ostream &fout, const int64_t RMtrials) |
| Finds and prints the \(s\) largest prime integers \(m < 2^e\).
|
template<typename Int> |
void | findPrime (int64_t k, int64_t e, int64_t s, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials) |
| Finds the \(s\) largest prime integers \(m<2^e\) for which \(r = (m^k-1)/(m-1)\) is also prime.
|
template<typename Int> |
void | findPrime (int64_t k, int64_t e, int64_t c1, int64_t c2, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials) |
| Finds all integers \(m\), in \(2^e + c_1 \le m \le 2^e + c_2\), such that \(m\) and \(r = (m^k-1)/(m-1)\) are prime.
|
template<typename Int> |
static bool | isPrimitiveElement (const Int &a, const IntFactorization< Int > &fac, const Int &p, long e=1) |
| This file provides static functions to test for the primitivity of an integer or a polynomial in a finite field.
|
template<typename Int> |
static bool | isPrimitive (const NTL::Vec< Int > &aa, const Int &m, const IntFactorization< Int > &fm, const IntFactorization< Int > &fr) |
| Returns true iff the polynomial \(f\) is a primitive polynomial modulo \(m\).
|
template<typename Int> |
static bool | isPrimitive23 (const NTL::Vec< Int > &aa, const Int &m, const IntFactorization< Int > &fr) |
| Similar to isPrimitive above, except that this function only checks for Conditions 2 and 3.
|
template<typename Int> |
static void | setCharacPoly (typename FlexModInt< Int >::PolX &f, const NTL::Vec< Int > &aa) |
| Sets the coefficients of the polynomial f so it corresponds to the characteristic polynomial \(P(z) = z^k - a_1 z^{k-1} - \cdots- a_{k-1} z - a_k\) with coefficients \(c_{k-j} = a_j = \)aa[j].
|
template<typename Int> |
static void | setCharacPoly (typename FlexModInt< Int >::PolX &f, typename FlexModInt< Int >::IntVecP &aaP) |
| In this version, the vector of coefficients is passed directly as an IntVecP, so there is no need to convert it internally (this is more efficient).
|
template<typename Int> |
static void | vecMRGToPoly (typename FlexModInt< Int >::PolX &f, typename FlexModInt< Int >::IntVecP aaP, const NTL::Vec< Int > &xx) |
| Converts the vector state xx of an MRG to its polynomial representation in f.
|
template<typename Int> |
static void | polyToVecMRG (const NTL::Vec< Int > &xx, typename FlexModInt< Int >::IntVecP aaP, typename FlexModInt< Int >::PolX &f) |
| Converts the polynomial representation in f to the vector state xx of an MRG, with xx[j] \(x_{n-k+1+j]\).
|
template<typename Int> |
bool | isPrimitiveElement (const Int &a, const IntFactorization< Int > &fac, const Int &p, long e) |
| Returns in fj the polynomial \(x^j \mod f(x) (\bmod m)\) where \(f(x)\) is the polynomial with coefficients in 'C', modulo 'm'.
|
template<typename Int> |
static void | setCharacPoly (typename FlexModInt< Int >::PolX &f, typename FlexModInt< Int >::IntVecP aaP) |
This has to be redone in a way similar to Rank1Lattice.
Anything to change or to add ??? **********************
template<typename Int>
bool LatMRG::isPrimitiveElement |
( |
const Int & | a, |
|
|
const IntFactorization< Int > & | fac, |
|
|
const Int & | p, |
|
|
long | e ) |
|
static |
This file provides static functions to test for the primitivity of an integer or a polynomial in a finite field.
Suppose that \(a\), \(e\), and \(p\) are integers, \(p\) is a prime number, and \(a\) is relatively prime with \(m=p^e\). The smallest positive integer \(\lambda(m,a)\) for which \(a^{\lambda(m,a)}= 1 \ \bmod\ 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 element modulo \(m\). The function isPrimitiveElement tests for this property.
The function isPrimitive tests for the primitivity of the characteristic polynomial of an MRG, with coefficients in \(\mathbb Z_m\). This is done by checking the conditions proposed by Alanen and Knuth [1], and restated in [6] and in the LatMRG user's guide. The polynomial arithmetic is done using NTL. A polynomial
\[ f(z) = c_0 + c_1 z^1 + \cdots + c_{k-1} z^{k-1} + c_k z^k \tag{eq.poly1}
\]
of degree \(k\) and integer coefficients \(c_j \in \mathbb Z_m\) is represented in NTL by the vector \((c_0,c_1,\dots,c_k)\) of its coefficients, which is directly accessible. The characteristic polynomial of an MRG, usually written as
\[ P(z) = z^k - a_1 z^{k-1} - \cdots- a_{k-1} z - a_k, \tag{eq.poly2}
\]
must be put in the form (eq.poly1)
to use NTL. It has \(c_k=1, $c_{k-1}= -a_1\f, \cdots, c_1 = -a_{k-1}, c_0 = - a_k\).
We recall that the polynomial \(f(z)\) in (eq.poly1)
with \(c_k=1\) is primitive modulo \(m\) if and only if the three following conditions are satisfied:
- None
- \([(-1)^{k} c_0]^{(m-1)/q} \bmod m \neq1\) for each prime factor \(q\) of \(m - 1\);
- None
- \(z^r \bmod(f(z),m) = (-1)^{k} c_0 \bmod m\);
- None
- \(z^{r/q} \bmod(f(z), m) \) has positive degree for each prime factor \(q\) of \(r\), with \(1<q< r\);
where \(r = (m^k - 1)/(m - 1)\). Condition 1 is the same as saying that \((-1)^{k} c_0\) is a primitive root of \(m\). Condition 3 is automatically satisfied when \(r\) is prime.
The types used for the polynomial coefficients in depend on the choice of Int and are determined by the template class FlexModInt.h. The function isPrimitiveElement does no use FlexModInt. Returns true iff a is a primitive element modulo \(p^e\), where \(p\) is assumed to be a prime number. The prime factor decomposition of \(p-1\) must be given in fac, and the list of inverse factors in fac must be up to date.
This file provides static functions to test for the primitivity of an integer or a polynomial in a finite field.