inline long operator%(const ZZ& a, long b)   { return rem(a, b); }inline ZZ& operator/=(ZZ& x, const ZZ& b)   { div(x, x, b); return x; } inline ZZ& operator/=(ZZ& x, long b)   { div(x, x, b); return x; } inline ZZ& operator%=(ZZ& x, const ZZ& b)   { rem(x, x, b); return x; } /**********************************************************                        GCD's***********************************************************/inline void GCD(ZZ& d, const ZZ& a, const ZZ& b)// d = gcd(a, b)   { NTL_zgcd(a.rep, b.rep, &d.rep); }inline ZZ GCD(const ZZ& a, const ZZ& b)   { ZZ x; GCD(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline void XGCD(ZZ& d, ZZ& s, ZZ& t, const ZZ& a, const ZZ& b)//  d = gcd(a, b) = a*s + b*t;   { NTL_zexteucl(a.rep, &s.rep, b.rep, &t.rep, &d.rep); }// single-precision versionslong GCD(long a, long b);void XGCD(long& d, long& s, long& t, long a, long b);/************************************************************                      Bit Operations*************************************************************/inline void LeftShift(ZZ& x, const ZZ& a, long k)// x = (a << k), k < 0 => RightShift   { NTL_zlshift(a.rep, k, &x.rep); }inline ZZ LeftShift(const ZZ& a, long k)   { ZZ x; LeftShift(x, a, k); NTL_OPT_RETURN(ZZ, x); }inline void RightShift(ZZ& x, const ZZ& a, long k)// x = (a >> k), k < 0 => LeftShift   { NTL_zrshift(a.rep, k, &x.rep); }inline ZZ RightShift(const ZZ& a, long k)   { ZZ x; RightShift(x, a, k); NTL_OPT_RETURN(ZZ, x); }#ifndef NTL_TRANSITIONinline ZZ operator>>(const ZZ& a, long n)   { ZZ x; RightShift(x, a, n); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator<<(const ZZ& a, long n)   { ZZ x; LeftShift(x, a, n); NTL_OPT_RETURN(ZZ, x); }inline ZZ& operator<<=(ZZ& x, long n)   { LeftShift(x, x, n); return x; }inline ZZ& operator>>=(ZZ& x, long n)   { RightShift(x, x, n); return x; }#endifinline long MakeOdd(ZZ& x)// removes factors of 2 from x, returns the number of 2's removed// returns 0 if x == 0   { return NTL_zmakeodd(&x.rep); }inline long NumTwos(const ZZ& x)// returns max e such that 2^e divides x if x != 0, and returns 0 if x == 0.   { return NTL_znumtwos(x.rep); }inline long IsOdd(const ZZ& a)// returns 1 if a is odd, otherwise 0   { return NTL_zodd(a.rep); }inline long NumBits(const ZZ& a)// returns the number of bits in |a|; NumBits(0) = 0   { return NTL_z2log(a.rep); }inline long bit(const ZZ& a, long k)// returns bit k of a, 0 being the low-order bit   { return NTL_zbit(a.rep, k); }#ifndef NTL_GMP_LIP// only defined for the "classic" long integer package, for backward// compatability.inline long digit(const ZZ& a, long k)   { return NTL_zdigit(a.rep, k); }#endif// returns k-th digit of |a|, 0 being the low-order digit.inline void trunc(ZZ& x, const ZZ& a, long k)// puts k low order bits of |a| into x   { NTL_zlowbits(a.rep, k, &x.rep); }inline ZZ trunc_ZZ(const ZZ& a, long k)   { ZZ x; trunc(x, a, k); NTL_OPT_RETURN(ZZ, x); }inline long trunc_long(const ZZ& a, long k)// returns k low order bits of |a|   { return NTL_zslowbits(a.rep, k); }inline long SetBit(ZZ& x, long p)// returns original value of p-th bit of |a|, and replaces// p-th bit of a by 1 if it was zero;// error if p < 0    { return NTL_zsetbit(&x.rep, p); }inline long SwitchBit(ZZ& x, long p)// returns original value of p-th bit of |a|, and switches// the value of p-th bit of a;// p starts counting at 0;//   error if p < 0   { return NTL_zswitchbit(&x.rep, p); }inline long weight(long a)// returns Hamming weight of |a|   { return NTL_zweights(a); }inline long weight(const ZZ& a)// returns Hamming weight of |a|   { return NTL_zweight(a.rep); }inline void bit_and(ZZ& x, const ZZ& a, const ZZ& b)// x = |a| AND |b|   { NTL_zand(a.rep, b.rep, &x.rep); }void bit_and(ZZ& x, const ZZ& a, long b);inline void bit_and(ZZ& x, long a, const ZZ& b)   { bit_and(x, b, a); }inline void bit_or(ZZ& x, const ZZ& a, const ZZ& b)// x = |a| OR |b|   { NTL_zor(a.rep, b.rep, &x.rep); }void bit_or(ZZ& x, const ZZ& a, long b);inline void bit_or(ZZ& x, long a, const ZZ& b)   { bit_or(x, b, a); }inline void bit_xor(ZZ& x, const ZZ& a, const ZZ& b)// x = |a| XOR |b|   { NTL_zxor(a.rep, b.rep, &x.rep); }void bit_xor(ZZ& x, const ZZ& a, long b);inline void bit_xor(ZZ& x, long a, const ZZ& b)   { bit_xor(x, b, a); }inline ZZ operator&(const ZZ& a, const ZZ& b)   { ZZ x; bit_and(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator&(const ZZ& a, long b)   { ZZ x; bit_and(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator&(long a, const ZZ& b)   { ZZ x; bit_and(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator|(const ZZ& a, const ZZ& b)   { ZZ x; bit_or(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator|(const ZZ& a, long b)   { ZZ x; bit_or(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator|(long a, const ZZ& b)   { ZZ x; bit_or(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator^(const ZZ& a, const ZZ& b)   { ZZ x; bit_xor(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator^(const ZZ& a, long b)   { ZZ x; bit_xor(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator^(long a, const ZZ& b)   { ZZ x; bit_xor(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ& operator&=(ZZ& x, const ZZ& b)    { bit_and(x, x, b); return x; }inline ZZ& operator&=(ZZ& x, long b)    { bit_and(x, x, b); return x; }inline ZZ& operator|=(ZZ& x, const ZZ& b)    { bit_or(x, x, b); return x; }inline ZZ& operator|=(ZZ& x, long b)    { bit_or(x, x, b); return x; }inline ZZ& operator^=(ZZ& x, const ZZ& b)    { bit_xor(x, x, b); return x; }inline ZZ& operator^=(ZZ& x, long b)    { bit_xor(x, x, b); return x; }long NumBits(long a);long bit(long a, long k);long NextPowerOfTwo(long m);// returns least nonnegative k such that 2^k >= minlinelong NumBytes(const ZZ& a)   { return (NumBits(a)+7)/8; }inlinelong NumBytes(long a)   { return (NumBits(a)+7)/8; }/***********************************************************          Some specialized routines************************************************************/inline long ZZ_BlockConstructAlloc(ZZ& x, long d, long n)   { return NTL_zblock_construct_alloc(&x.rep, d, n); }inline void ZZ_BlockConstructSet(ZZ& x, ZZ& y, long i)   { NTL_zblock_construct_set(x.rep, &y.rep, i); }inline long ZZ_BlockDestroy(ZZ& x)   { return NTL_zblock_destroy(x.rep);  }inline long ZZ_storage(long d)   { return NTL_zblock_storage(d); }inline long ZZ_RoundCorrection(const ZZ& a, long k, long residual)   { return NTL_zround_correction(a.rep, k, residual); }/***********************************************************                  Psuedo-random Numbers************************************************************/void SetSeed(const ZZ& s);// initialize random number generatorvoid RandomBnd(ZZ& x, const ZZ& n);// x = "random number" in the range 0..n-1, or 0  if n <= 0inline ZZ RandomBnd(const ZZ& n)   { ZZ x; RandomBnd(x, n); NTL_OPT_RETURN(ZZ, x); }void RandomLen(ZZ& x, long NumBits);// x = "random number" with precisely NumBits bits.inline ZZ RandomLen_ZZ(long NumBits)   { ZZ x; RandomLen(x, NumBits); NTL_OPT_RETURN(ZZ, x); }void RandomBits(ZZ& x, long NumBits);// x = "random number", 0 <= x < 2^NumBits inline ZZ RandomBits_ZZ(long NumBits)   { ZZ x; RandomBits(x, NumBits); NTL_OPT_RETURN(ZZ, x); }// single-precision version of the abovelong RandomBnd(long n);long RandomLen_long(long l);long RandomBits_long(long l);unsigned long RandomWord();unsigned long RandomBits_ulong(long l);/**********************************************************             Incremental Chinese Remaindering***********************************************************/long CRT(ZZ& a, ZZ& p, const ZZ& A, const ZZ& P);long CRT(ZZ& a, ZZ& p, long A, long P);// 0 <= A < P, (p, P) = 1;// computes b such that b = a mod p, b = A mod p,//   and -p*P/2 < b <= p*P/2;// sets a = b, p = p*P, and returns 1 if a's value//   has changed, otherwise 0inline long CRTInRange(const ZZ& gg, const ZZ& aa)   { return NTL_zcrtinrange(gg.rep, aa.rep); }// an auxilliary routine used by newer CRT routines to maintain// backward compatability.// test if a > 0 and -a/2 < g <= a/2// this is "hand crafted" so as not too waste too much time// in the CRT routines./**********************************************************                  Rational Reconstruction***********************************************************/inlinelong ReconstructRational(ZZ& a, ZZ& b, const ZZ& u, const ZZ& m,                          const ZZ& a_bound, const ZZ& b_bound){   return NTL_zxxratrecon(u.rep, m.rep, a_bound.rep, b_bound.rep, &a.rep, &b.rep);}/************************************************************                      Primality Testing *************************************************************/void GenPrime(ZZ& n, long l, long err = 80);inline ZZ GenPrime_ZZ(long l, long err = 80) { ZZ x; GenPrime(x, l, err); NTL_OPT_RETURN(ZZ, x); }long GenPrime_long(long l, long err = 80);// This generates a random prime n of length l so that the// probability of erroneously returning a composite is bounded by 2^(-err).void GenGermainPrime(ZZ& n, long l, long err = 80);inline ZZ GenGermainPrime_ZZ(long l, long err = 80) { ZZ x; GenGermainPrime(x, l, err); NTL_OPT_RETURN(ZZ, x); }long GenGermainPrime_long(long l, long err = 80);// This generates a random prime n of length l so that thelong ProbPrime(const ZZ& n, long NumTrials = 10);// tests if n is prime;  performs a little trial division,// followed by a single-precision MillerWitness test, followed by// up to NumTrials general MillerWitness tests.long MillerWitness(const ZZ& n, const ZZ& w);// Tests if w is a witness to primality a la Miller.// Assumption: n is odd and positive, 0 <= w < n.void RandomPrime(ZZ& n, long l, long NumTrials=10);// n =  random l-bit primeinline ZZ RandomPrime_ZZ(long l, long NumTrials=10)   { ZZ x; RandomPrime(x, l, NumTrials); NTL_OPT_RETURN(ZZ, x); }void NextPrime(ZZ& n, const ZZ& m, long NumTrials=10);// n = smallest prime >= m.inline ZZ NextPrime(const ZZ& m, long NumTrials=10)   { ZZ x; NextPrime(x, m, NumTrials); NTL_OPT_RETURN(ZZ, x); }// single-precision versionslong ProbPrime(long n, long NumTrials = 10);long RandomPrime_long(long l, long NumTrials=10);long NextPrime(long l, long NumTrials=10);/************************************************************                      Exponentiation*************************************************************/inline void power(ZZ& x, const ZZ& a, long e)   { NTL_zexp(a.rep, e, &x.rep); }inline ZZ power(const ZZ& a, long e)   { ZZ x; power(x, a, e); NTL_OPT_RETURN(ZZ, x); }inline void power(ZZ& x, long a, long e)   {  NTL_zexps(a, e, &x.rep); }inline ZZ power_ZZ(long a, long e)   { ZZ x; power(x, a, e); NTL_OPT_RETURN(ZZ, x); }long power_long(long a, long e); void power2(ZZ& x, long e);inline ZZ power2_ZZ(long e)   { ZZ x; power2(x, e); NTL_OPT_RETURN(ZZ, x); }/*************************************************************                       Square Roots**************************************************************/inline void SqrRoot(ZZ& x, const ZZ& a)// x = [a^{1/2}], a >= 0{   NTL_zsqrt(a.rep, &x.rep);}inline ZZ SqrRoot(const ZZ& a)   { ZZ x; SqrRoot(x, a); NTL_OPT_RETURN(ZZ, x); }inline long SqrRoot(long a) { return NTL_zsqrts(a); }// single-precision version/***************************************************************                      Modular Arithmetic***************************************************************/// The following routines perform arithmetic mod n, n positive.// All args (other than exponents) are assumed to be in the range 0..n-1.inline void AddMod(ZZ& x, const ZZ& a, const ZZ& b, const ZZ& n)// x = (a+b)%n   { NTL_zaddmod(a.rep, b.rep, n.rep, &x.rep); }   inline ZZ AddMod(const ZZ& a, const ZZ& b, const ZZ& n)   { ZZ x; AddMod(x, a, b, n); NTL_OPT_RETURN(ZZ, x); }inline void SubMod(ZZ& x, const ZZ& a, const ZZ& b, const ZZ& n)// x = (a-b)%n   { NTL_zsubmod(a.rep, b.rep, n.rep, &x.rep); }inline ZZ SubMod(const ZZ& a, const ZZ& b, const ZZ& n)   { ZZ x; SubMod(x, a, b, n); NTL_OPT_RETURN(ZZ, x); }inline void NegateMod(ZZ& x, const ZZ& a, const ZZ& n)// x = -a % n   { NTL_zsubmod(0, a.rep, n.rep, &x.rep); }inline ZZ NegateMod(const ZZ& a, const ZZ& n)   { ZZ x; NegateMod(x, a, n); NTL_OPT_RETURN(ZZ, x); }void AddMod(ZZ& x, const ZZ& a, long b, const ZZ& n);inline ZZ AddMod(const ZZ& a, long b, const ZZ& n)   { ZZ x; AddMod(x, a, b, n); NTL_OPT_RETURN(ZZ, x); }inline void AddMod(ZZ& x, long a, const ZZ& b, const ZZ& n)   { AddMod(x, b, a, n); }inline ZZ AddMod(long a, const ZZ& b, const ZZ& n)   { ZZ x; AddMod(x, a, b, n); NTL_OPT_RETURN(ZZ, x); }void SubMod(ZZ& x, const ZZ& a, long b, const ZZ& n);