\**************************************************************************/void GCD(ZZX& d, const ZZX& a, const ZZX& b);ZZX GCD(const ZZX& a, const ZZX& b); // d = gcd(a, b), LeadCoeff(d) >= 0.  Uses a modular algorithm.void XGCD(ZZ& r, ZZX& s, ZZX& t, const ZZX& a, const ZZX& b,           long deterministic=0);// r = resultant of a and b; if r != 0, then computes s and t such// that: a*s + b*t = r; otherwise s and t not affected.  if// !deterministic, then resultant computation may use a randomized// strategy that errs with probability no more than 2^{-80}./**************************************************************************\                               Input/OutputI/O format:   [a_0 a_1 ... a_n],represents the polynomial a_0 + a_1*X + ... + a_n*X^n.\**************************************************************************/istream& operator>>(istream& s, ZZX& x);ostream& operator<<(ostream& s, const ZZX& a);/**************************************************************************\                             Some utility routines\**************************************************************************/long deg(const ZZX& a);  returns degree of a; deg(0) == -1const ZZ& coeff(const ZZX& a, long i);// returns a read-only reference to a.rep[i], or zero if i not in// rangeconst ZZ& LeadCoeff(const ZZX& a);// read-only reference to leading term of a, or zero if a == 0const ZZ& ConstTerm(const ZZX& a);// read-only reference to constant term of a, or zero if a == 0void SetCoeff(ZZX& x, long i, const ZZ& a);void SetCoeff(ZZX& x, long i, long a);// makes coefficient of X^i equal to a; error is raised if i < 0void SetCoeff(ZZX& x, long i);// makes coefficient of X^i equal to 1; error is raised if i < 0void SetX(ZZX& x); // x is set to the monomial Xlong IsX(const ZZX& a); // test if x = Xvoid diff(ZZX& x, const ZZX& a); // x = derivative of aZZX diff(const ZZX& a); long MaxBits(const ZZX& f);// returns max NumBits of coefficients of fvoid reverse(ZZX& x, const ZZX& a, long hi);ZZX reverse(const ZZX& a, long hi);void reverse(ZZX& x, const ZZX& a);ZZX reverse(const ZZX& a);// x = reverse of a[0]..a[hi] (hi >= -1);// hi defaults to deg(a) in second versionvoid VectorCopy(vec_ZZ& x, const ZZX& a, long n);vec_ZZ VectorCopy(const ZZX& a, long n);// x = copy of coefficient vector of a of length exactly n.// input is truncated or padded with zeroes as appropriate./**************************************************************************\                       Arithmetic mod X^nAll routines require n >= 0, otherwise an error is raised.\**************************************************************************/void trunc(ZZX& x, const ZZX& a, long m); // x = a % X^mZZX trunc(const ZZX& a, long m);void MulTrunc(ZZX& x, const ZZX& a, const ZZX& b, long n);ZZX MulTrunc(const ZZX& a, const ZZX& b, long n);// x = a * b % X^nvoid SqrTrunc(ZZX& x, const ZZX& a, long n);ZZX SqrTrunc(const ZZX& a, long n);// x = a^2 % X^nvoid InvTrunc(ZZX& x, const ZZX& a, long n);ZZX InvTrunc(const ZZX& a, long n);// computes x = a^{-1} % X^m.  Must have ConstTerm(a) invertible./**************************************************************************\                               Modular ArithmeticThe modulus f must be monic with deg(f) > 0, and other arguments must have smaller degree.\**************************************************************************/void MulMod(ZZX& x, const ZZX& a, const ZZX& b, const ZZX& f);ZZX MulMod(const ZZX& a, const ZZX& b, const ZZX& f);// x = a * b mod fvoid SqrMod(ZZX& x, const ZZX& a, const ZZX& f);ZZX SqrMod(const ZZX& a, const ZZX& f);// x = a^2 mod fvoid MulByXMod(ZZX& x, const ZZX& a, const ZZX& f);ZZX MulByXMod(const ZZX& a, const ZZX& f);// x = a*X mod f/**************************************************************************\                  traces, norms, resultants, discriminants,                   minimal and characteristic polynomials\**************************************************************************/void TraceMod(ZZ& res, const ZZX& a, const ZZX& f);ZZ TraceMod(const ZZX& a, const ZZX& f);// res = trace of (a mod f).  f must be monic, 0 < deg(f), deg(a) <// deg(f)void TraceVec(vec_ZZ& S, const ZZX& f);vec_ZZ TraceVec(const ZZX& f);// S[i] = Trace(X^i mod f), for i = 0..deg(f)-1.// f must be a monic polynomial.// The following routines use a modular approach.void resultant(ZZ& res, const ZZX& a, const ZZX& b, long deterministic=0);ZZ resultant(const ZZX& a, const ZZX& b, long deterministic=0);// res = resultant of a and b. If !deterministic, then it may use a// randomized strategy that errs with probability no more than// 2^{-80}.void NormMod(ZZ& res, const ZZX& a, const ZZX& f, long deterministic=0);ZZ NormMod(const ZZX& a, const ZZX& f, long deterministic=0);// res = norm of (a mod f).  f must be monic, 0 < deg(f), deg(a) <// deg(f). If !deterministic, then it may use a randomized strategy// that errs with probability no more than 2^{-80}.void discriminant(ZZ& d, const ZZX& a, long deterministic=0);ZZ discriminant(const ZZX& a, long deterministic=0);// d = discriminant of a = (-1)^{m(m-1)/2} resultant(a, a')/lc(a),// where m = deg(a). If !deterministic, then it may use a randomized// strategy that errs with probability no more than 2^{-80}.void CharPolyMod(ZZX& g, const ZZX& a, const ZZX& f, long deterministic=0);ZZX CharPolyMod(const ZZX& a, const ZZX& f, long deterministic=0);// g = char poly of (a mod f).  f must be monic.  If !deterministic,// then it may use a randomized strategy that errs with probability no// more than 2^{-80}.void MinPolyMod(ZZX& g, const ZZX& a, const ZZX& f);ZZX MinPolyMod(const ZZX& a, const ZZX& f);// g = min poly of (a mod f).  f must be monic, 0 < deg(f), deg(a) <// deg(f).  May use a probabilistic strategy that errs with// probability no more than 2^{-80}./**************************************************************************\                  Incremental Chinese Remaindering\**************************************************************************/long CRT(ZZX& a, ZZ& prod, const zz_pX& A);long CRT(ZZX& a, ZZ& prod, const ZZ_pX& A);// Incremental Chinese Remaindering: If p is the current zz_p/ZZ_p modulus with// (p, prod) = 1; Computes a' such that a' = a mod prod and a' = A mod p,// with coefficients in the interval (-p*prod/2, p*prod/2]; // Sets a := a', prod := p*prod, and returns 1 if a's value changed./**************************************************************************\                                vectors of ZZX's\**************************************************************************/NTL_vector_decl(ZZX,vec_ZZX)// vec_ZZXNTL_eq_vector_decl(ZZX,vec_ZZX)// == and !=NTL_io_vector_decl(ZZX,vec_ZZX)// I/O operators/**************************************************************************\                                MiscellanyA ZZX f is represented as a vec_ZZ, which can be accessed asf.rep.  The constant term is f.rep[0] and the leading coefficient isf.rep[f.rep.length()-1], except if f is zero, in which casef.rep.length() == 0.  Note that the leading coefficient is alwaysnonzero (unless f is zero).  One can freely access and modify f.rep,but one should always ensure that the leading coefficient is nonzero,which can be done by invoking f.normalize().\**************************************************************************/void clear(ZZX& x); // x = 0void set(ZZX& x); // x = 1void ZZX::normalize();// f.normalize() strips leading zeros from f.rep.void ZZX::SetMaxLength(long n);// f.SetMaxLength(n) pre-allocate spaces for n coefficients.  The// polynomial that f represents is unchanged.void ZZX::kill();// f.kill() sets f to 0 and frees all memory held by f.  Equivalent to// f.rep.kill().ZZX::ZZX(INIT_SIZE_TYPE, long n);// ZZX(INIT_SIZE, n) initializes to zero, but space is pre-allocated// for n coefficientsstatic const ZZX& zero();// ZZX::zero() is a read-only reference to 0void swap(ZZX& x, ZZX& y); // swap x & y (by swapping pointers)