#ifndef NTL_ZZ__H#define NTL_ZZ__H/********************************************************   LIP INTERFACE    The class ZZ implements signed, arbitrary length integers.**********************************************************/#include <NTL/lip.h>#include <NTL/tools.h>NTL_OPEN_NNSclass ZZ {public:NTL_verylong rep; // This is currently public for "emergency" situations                   // May be private in future versions.ZZ() // initial value is 0.{ rep = 0; }ZZ(INIT_SIZE_TYPE, long k)// initial value is 0, but space is pre-allocated so that numbers// x with x.size() <= k can be stored without re-allocation.// Call with ZZ(INIT_SIZE, k).// The purpose for the INIT_SIZE argument is to prevent automatic// type conversion from long to ZZ, which would be tempting, but wrong.{   rep = 0;   NTL_zsetlength(&rep, k); }ZZ(const ZZ& a)// initial value is a.{   rep = 0;   NTL_zcopy(a.rep, &rep);}ZZ(INIT_VAL_TYPE, long a) { rep = 0; NTL_zintoz(a, &rep); }ZZ(INIT_VAL_TYPE, int a) { rep = 0; NTL_zintoz(a, &rep); }ZZ(INIT_VAL_TYPE, unsigned long a) { rep = 0; NTL_zuintoz(a, &rep); }ZZ(INIT_VAL_TYPE, unsigned int a) { rep = 0; NTL_zuintoz((unsigned long) a, &rep); }inline ZZ(INIT_VAL_TYPE, const char *);inline ZZ(INIT_VAL_TYPE, float);inline ZZ(INIT_VAL_TYPE, double);ZZ& operator=(const ZZ& a) { NTL_zcopy(a.rep, &rep); return *this; }ZZ& operator=(long a) { NTL_zintoz(a, &rep); return *this; }~ZZ() { NTL_zfree(&rep); }void kill()// force the space held by this ZZ to be released.// The value then becomes 0.{ NTL_zfree(&rep); }void SetSize(long k)// pre-allocates space for k-digit numbers (base 2^NTL_ZZ_NBITS);  // does not change the value.{ NTL_zsetlength(&rep, k); }long size() const   { return NTL_zsize(rep); }// returns the number of (NTL_ZZ_NBIT-bit) digits of |a|; the size of 0 is 0.long SinglePrecision() const   { return NTL_zsptest(rep); }// tests if less than NTL_SP_BOUND in absolute valuelong WideSinglePrecision() const   { return NTL_zwsptest(rep); }// tests if less than NTL_WSP_BOUND in absolute valuestatic const ZZ& zero();ZZ(ZZ& x, INIT_TRANS_TYPE) { rep = x.rep; x.rep = 0; }// used to cheaply hand off memory management of return value,// without copying, assuming compiler implements the// "return value optimization"};const ZZ& ZZ_expo(long e);inline void clear(ZZ& x)// x = 0   { NTL_zzero(&x.rep); }inline void set(ZZ& x)// x = 1   { NTL_zone(&x.rep); }inline void swap(ZZ& x, ZZ& y)// swap the values of x and y (swaps pointers only)   { NTL_zswap(&x.rep, &y.rep); }inline double log(const ZZ& a)   { return NTL_zlog(a.rep); }/**********************************************************   Conversion routines.***********************************************************/inline void conv(ZZ& x, const ZZ& a) { x = a; }inline ZZ to_ZZ(const ZZ& a) { return a; }inline void conv(ZZ& x, long a) { NTL_zintoz(a, &x.rep); }inline ZZ to_ZZ(long a) { return ZZ(INIT_VAL, a); }inline void conv(ZZ& x, int a) { NTL_zintoz(long(a), &x.rep); }inline ZZ to_ZZ(int a) { return ZZ(INIT_VAL, a); }inline void conv(ZZ& x, unsigned long a) { NTL_zuintoz(a, &x.rep); }inline ZZ to_ZZ(unsigned long a) { return ZZ(INIT_VAL, a); }inline void conv(ZZ& x, unsigned int a) { NTL_zuintoz((unsigned long)(a), &x.rep); }inline ZZ to_ZZ(unsigned int a) { return ZZ(INIT_VAL, a); }void conv(ZZ& x, const char *s);inline ZZ::ZZ(INIT_VAL_TYPE, const char *s) {  rep = 0; conv(*this, s); }inline ZZ to_ZZ(const char *s) { return ZZ(INIT_VAL, s); }inline void conv(ZZ& x, double a) { NTL_zdoubtoz(a, &x.rep); }inline ZZ::ZZ(INIT_VAL_TYPE, double a) { rep = 0; conv(*this, a); }inline ZZ to_ZZ(double a) { return ZZ(INIT_VAL, a); }inline void conv(ZZ& x, float a) { NTL_zdoubtoz(double(a), &x.rep); }inline ZZ::ZZ(INIT_VAL_TYPE, float a) { rep = 0; conv(*this, a); }inline ZZ to_ZZ(float a) { return ZZ(INIT_VAL, a); }inline void conv(long& x, const ZZ& a) { x = NTL_ztoint(a.rep); }inline long to_long(const ZZ& a)  { return NTL_ztoint(a.rep); }inline void conv(int& x, const ZZ& a) { x = int(NTL_ztoint(a.rep)); }inline int to_int(const ZZ& a)  { return int(NTL_ztoint(a.rep)); }inline void conv(unsigned long& x, const ZZ& a) { x = NTL_ztouint(a.rep); }inline long to_ulong(const ZZ& a)  { return NTL_ztouint(a.rep); }inline void conv(unsigned int& x, const ZZ& a)    { x = (unsigned int)(NTL_ztouint(a.rep)); }inline unsigned int to_uint(const ZZ& a)     { return (unsigned int)(NTL_ztouint(a.rep)); }inline void conv(double& x, const ZZ& a) { x = NTL_zdoub(a.rep); }inline double to_double(const ZZ& a) { return NTL_zdoub(a.rep); }inline void conv(float& x, const ZZ& a) { x = float(NTL_zdoub(a.rep)); }inline float to_float(const ZZ& a) { return float(NTL_zdoub(a.rep)); }inline void ZZFromBytes(ZZ& x, const unsigned char *p, long n)   { NTL_zfrombytes(&x.rep, p, n); }inline ZZ ZZFromBytes(const unsigned char *p, long n)   { ZZ x; ZZFromBytes(x, p, n); NTL_OPT_RETURN(ZZ, x); }inline void BytesFromZZ(unsigned char *p, const ZZ& a, long n)   { NTL_zbytesfromz(p, a.rep, n); }// ****** comparisonsinline long sign(const ZZ& a)// returns the sign of a (-1, 0, or 1).   { return NTL_zsign(a.rep); }inline long compare(const ZZ& a, const ZZ& b)// returns the sign of a-b (-1, 0, or 1).{   return NTL_zcompare(a.rep, b.rep);}inline long IsZero(const ZZ& a)// zero test   { return NTL_ziszero(a.rep); }inline long IsOne(const ZZ& a)   { return NTL_zisone(a.rep); }// test for 1   /* the usual comparison operators */inline long operator==(const ZZ& a, const ZZ& b)  { return NTL_zcompare(a.rep, b.rep) == 0; }inline long operator!=(const ZZ& a, const ZZ& b)  { return NTL_zcompare(a.rep, b.rep) != 0; }inline long operator<(const ZZ& a, const ZZ& b)  { return NTL_zcompare(a.rep, b.rep) < 0; }inline long operator>(const ZZ& a, const ZZ& b)  { return NTL_zcompare(a.rep, b.rep) > 0; }inline long operator<=(const ZZ& a, const ZZ& b)  { return NTL_zcompare(a.rep, b.rep) <= 0; }inline long operator>=(const ZZ& a, const ZZ& b)  { return NTL_zcompare(a.rep, b.rep) >= 0; }/* single-precision versions of the above */inline long compare(const ZZ& a, long b) { return NTL_zscompare(a.rep, b); }inline long compare(long a, const ZZ& b) { return -NTL_zscompare(b.rep, a); }inline long operator==(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) == 0; }inline long operator!=(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) != 0; }inline long operator<(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) < 0; }inline long operator>(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) > 0; }inline long operator<=(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) <= 0; }inline long operator>=(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) >= 0; }inline long operator==(long a, const ZZ& b) { return b == a; }inline long operator!=(long a, const ZZ& b) { return b != a; }inline long operator<(long a, const ZZ& b) { return b > a; }inline long operator>(long a, const ZZ& b) { return b < a; }inline long operator<=(long a, const ZZ& b) { return b >= a; }inline long operator>=(long a, const ZZ& b) { return b <= a; }/**************************************************                 Addition**************************************************/inline void add(ZZ& x, const ZZ& a, const ZZ& b)// x = a + b   { NTL_zadd(a.rep, b.rep, &x.rep); }inline void sub(ZZ& x, const ZZ& a, const ZZ& b)// x = a - b   { NTL_zsub(a.rep, b.rep, &x.rep); }inline void SubPos(ZZ& x, const ZZ& a, const ZZ& b)// x = a - b;  assumes a >= b >= 0.   { NTL_zsubpos(a.rep, b.rep, &x.rep); }inline void negate(ZZ& x, const ZZ& a)// x = -a   { NTL_zcopy(a.rep, &x.rep); NTL_znegate(&x.rep); }inline void abs(ZZ& x, const ZZ& a)// x = |a|{ NTL_zcopy(a.rep, &x.rep); NTL_zabs(&x.rep); }/* single-precision versions of the above */inline void add(ZZ& x, const ZZ& a, long b)   { NTL_zsadd(a.rep, b, &x.rep); }inline void add(ZZ& x, long a, const ZZ& b) { add(x, b, a); }void sub(ZZ& x, const ZZ& a, long b);void sub(ZZ& x, long a, const ZZ& b);/* operator/function notation */inline ZZ operator+(const ZZ& a, const ZZ& b)   { ZZ x; add(x, a, b); NTL_OPT_RETURN(ZZ, x); } inline ZZ operator+(const ZZ& a, long b)   { ZZ x; add(x, a, b); NTL_OPT_RETURN(ZZ, x); } inline ZZ operator+(long  a, const ZZ& b)   { ZZ x; add(x, a, b); NTL_OPT_RETURN(ZZ, x); } inline ZZ operator-(const ZZ& a, const ZZ& b)   { ZZ x; sub(x, a, b); NTL_OPT_RETURN(ZZ, x); } inline ZZ operator-(const ZZ& a, long b)   { ZZ x; sub(x, a, b); NTL_OPT_RETURN(ZZ, x); } inline ZZ operator-(long  a, const ZZ& b)   { ZZ x; sub(x, a, b); NTL_OPT_RETURN(ZZ, x); } inline ZZ operator-(const ZZ& a)  { ZZ x; negate(x, a); NTL_OPT_RETURN(ZZ, x); }inline ZZ abs(const ZZ& a)  { ZZ x; abs(x, a); NTL_OPT_RETURN(ZZ, x); }/* op= notation */inline ZZ& operator+=(ZZ& x, const ZZ& a)  { add(x, x, a); return x; }inline ZZ& operator+=(ZZ& x, long a)  { add(x, x, a); return x; }inline ZZ& operator-=(ZZ& x, const ZZ& a)  { sub(x, x, a); return x; }inline ZZ& operator-=(ZZ& x, long a)  { sub(x, x, a); return x; }/* inc/dec */inline ZZ& operator++(ZZ& x) { add(x, x, 1); return x; }inline void operator++(ZZ& x, int) { add(x, x, 1); }inline ZZ& operator--(ZZ& x) { add(x, x, -1); return x; }inline void operator--(ZZ& x, int) { add(x, x, -1); }/*******************************************************                 Multiplication.********************************************************/inline void mul(ZZ& x, const ZZ& a, const ZZ& b)// x = a * b   { NTL_zmul(a.rep, b.rep, &x.rep); }inline void sqr(ZZ& x, const ZZ& a)// x = a*a   { NTL_zsq(a.rep, &x.rep); }inline ZZ sqr(const ZZ& a)   { ZZ x; sqr(x, a); NTL_OPT_RETURN(ZZ, x); }/* single-precision versions */inline void mul(ZZ& x, const ZZ& a, long b)   { NTL_zsmul(a.rep, b, &x.rep); }inline void mul(ZZ& x, long a, const ZZ& b)    { mul(x, b, a); }/* operator notation */inline ZZ operator*(const ZZ& a, const ZZ& b)  { ZZ x; mul(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator*(const ZZ& a, long b)  { ZZ x; mul(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator*(long a, const ZZ& b)  { ZZ x; mul(x, a, b); NTL_OPT_RETURN(ZZ, x); }/* op= notation */inline ZZ& operator*=(ZZ& x, const ZZ& a)  { mul(x, x, a); return x; }inline ZZ& operator*=(ZZ& x, long a)  { mul(x, x, a); return x; }// Special routines for implementing CRT in ZZ_pX arithmeticinline void ZZ_p_crt_struct_init(void **crt_struct, long n, const ZZ& p,                                  const long *primes)    { NTL_crt_struct_init(crt_struct, n, p.rep, primes); }inline void ZZ_p_crt_struct_insert(void *crt_struct, long i, const ZZ& m)   { NTL_crt_struct_insert(crt_struct, i, m.rep); }inline void ZZ_p_crt_struct_free(void *crt_struct)   { NTL_crt_struct_free(crt_struct); }inline void ZZ_p_crt_struct_eval(void *crt_struct, ZZ& t, const long *a)   { NTL_crt_struct_eval(crt_struct, &t.rep, a); }inline long ZZ_p_crt_struct_special(void *crt_struct)   { return NTL_crt_struct_special(crt_struct); }// Special routines for fast remainderinginline void ZZ_p_rem_struct_init(void **rem_struct, long n,                                  const ZZ& p, long *primes)   { NTL_rem_struct_init(rem_struct, n, p.rep, primes); }inline void ZZ_p_rem_struct_free(void *rem_struct)   { NTL_rem_struct_free(rem_struct); }inline void ZZ_p_rem_struct_eval(void *rem_struct, long *x, const ZZ& a)   { NTL_rem_struct_eval(rem_struct, x, a.rep); }/*******************************************************                    Division*******************************************************/inline void DivRem(ZZ& q, ZZ& r, const ZZ& a, const ZZ& b)// q = [a/b], r = a - b*q// |r| < |b|, and if r != 0, sign(r) = sign(b)   { NTL_zdiv(a.rep, b.rep, &q.rep, &r.rep); }inline void div(ZZ& q, const ZZ& a, const ZZ& b)// q = a/b   { NTL_zdiv(a.rep, b.rep, &q.rep, 0); }inline void rem(ZZ& r, const ZZ& a, const ZZ& b)// r = a%b   { NTL_zmod(a.rep, b.rep, &r.rep); }inline void QuickRem(ZZ& r, const ZZ& b)// r = r%b// assumes b > 0 and r >=0// division is performed in place and may cause r to be re-allocated.   { NTL_zquickmod(&r.rep, b.rep); }long divide(ZZ& q, const ZZ& a, const ZZ& b);// if b | a, sets q = a/b and returns 1; otherwise returns 0.long divide(const ZZ& a, const ZZ& b);// if b | a, returns 1; otherwise returns 0./* non-standard single-precision versions */inline long DivRem(ZZ& q, const ZZ& a, long b)   { return NTL_zsdiv(a.rep, b, &q.rep); } inline long rem(const ZZ& a, long b)   { return NTL_zsmod(a.rep, b); }/* single precision versions */inline void div(ZZ& q, const ZZ& a, long b)   { (void) NTL_zsdiv(a.rep, b, &q.rep); }long divide(ZZ& q, const ZZ& a, long b);// if b | a, sets q = a/b and returns 1; otherwise returns 0.long divide(const ZZ& a, long b);// if b | a, returns 1; otherwise returns 0.inline ZZ operator/(const ZZ& a, const ZZ& b)   { ZZ x; div(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator/(const ZZ& a, long b)   { ZZ x; div(x, a, b); NTL_OPT_RETURN(ZZ, x); }inline ZZ operator%(const ZZ& a, const ZZ& b)   { ZZ x; rem(x, a, b); NTL_OPT_RETURN(ZZ, x); }