#ifndef NTL_ZZ_pX__H#define NTL_ZZ_pX__H#include <NTL/vector.h>#include <NTL/ZZ_p.h>#include <NTL/vec_ZZ.h>#include <NTL/vec_ZZ_p.h>#include <NTL/FFT.h>NTL_OPEN_NNS// some cross-over points// macros are used so as to be consistent with zz_pX #define NTL_ZZ_pX_FFT_CROSSOVER (20)  #define NTL_ZZ_pX_NEWTON_CROSSOVER (45)#define NTL_ZZ_pX_DIV_CROSSOVER (90)#define NTL_ZZ_pX_HalfGCD_CROSSOVER (25)#define NTL_ZZ_pX_GCD_CROSSOVER (180)#define NTL_ZZ_pX_BERMASS_CROSSOVER (90)#define NTL_ZZ_pX_TRACE_CROSSOVER (90)/************************************************************                         ZZ_pXThe class ZZ_pX implements polynomial arithmetic modulo p.Polynomials are represented as vec_ZZ_p's.If f is a ZZ_pX, then f.rep is a vec_ZZ_p.The zero polynomial is represented as a zero length vector.Otherwise. f.rep[0] is the constant-term, and f.rep[f.rep.length()-1]is the leading coefficient, which is always non-zero.The member f.rep is public, so the vector representation is fullyaccessible.Use the member function normalize() to strip leading zeros.**************************************************************/class ZZ_pX {public:typedef vec_ZZ_p VectorBaseType; vec_ZZ_p rep;/***************************************************************          Constructors, Destructors, and Assignment****************************************************************/ZZ_pX()//  initial value 0   { }ZZ_pX(INIT_SIZE_TYPE, long n) { rep.SetMaxLength(n); }ZZ_pX(const ZZ_pX& a) : rep(a.rep) { }// initial value is aZZ_pX& operator=(const ZZ_pX& a)    { rep = a.rep; return *this; }~ZZ_pX() { }void normalize();// strip leading zerosvoid SetMaxLength(long n) // pre-allocate space for n coefficients.// Value is unchanged   { rep.SetMaxLength(n); }void kill() // free space held by this polynomial.  Value becomes 0.   { rep.kill(); }static const ZZ_pX& zero();ZZ_pX(ZZ_pX& x, INIT_TRANS_TYPE) : rep(x.rep, INIT_TRANS) { }inline ZZ_pX(long i, const ZZ_p& c);inline ZZ_pX(long i, long c);ZZ_pX& operator=(long a);ZZ_pX& operator=(const ZZ_p& a);};/********************************************************************                           input and outputI/O format:   [a_0 a_1 ... a_n],represents the polynomial a_0 + a_1*X + ... + a_n*X^n.On output, all coefficients will be integers between 0 and p-1,amd a_n not zero (the zero polynomial is [ ]).On input, the coefficients are arbitrary integers which arethen reduced modulo p, and leading zeros stripped.*********************************************************************/NTL_SNS istream& operator>>(NTL_SNS istream& s, ZZ_pX& x);NTL_SNS ostream& operator<<(NTL_SNS ostream& s, const ZZ_pX& a);/**********************************************************                   Some utility routines***********************************************************/inline long deg(const ZZ_pX& a) { return a.rep.length() - 1; }// degree of a polynomial.// note that the zero polynomial has degree -1.const ZZ_p& coeff(const ZZ_pX& a, long i);// zero if i not in rangevoid GetCoeff(ZZ_p& x, const ZZ_pX& a, long i);// x = a[i], or zero if i not in rangeconst ZZ_p& LeadCoeff(const ZZ_pX& a);// zero if a == 0const ZZ_p& ConstTerm(const ZZ_pX& a);// zero if a == 0void SetCoeff(ZZ_pX& x, long i, const ZZ_p& a);// x[i] = a, error is raised if i < 0void SetCoeff(ZZ_pX& x, long i, long a);void SetCoeff(ZZ_pX& x, long i);// x[i] = 1, error is raised if i < 0inline ZZ_pX::ZZ_pX(long i, const ZZ_p& a)   { SetCoeff(*this, i, a); } inline ZZ_pX::ZZ_pX(long i, long a)   { SetCoeff(*this, i, a); } void SetX(ZZ_pX& x);// x is set to the monomial Xlong IsX(const ZZ_pX& a);// test if x = Xinline void clear(ZZ_pX& x) // x = 0   { x.rep.SetLength(0); }inline void set(ZZ_pX& x)// x = 1   { x.rep.SetLength(1); set(x.rep[0]); }inline void swap(ZZ_pX& x, ZZ_pX& y)// swap x & y (only pointers are swapped)   { swap(x.rep, y.rep); }void random(ZZ_pX& x, long n);inline ZZ_pX random_ZZ_pX(long n)   { ZZ_pX x; random(x, n); NTL_OPT_RETURN(ZZ_pX, x); }// generate a random polynomial of degree < n void trunc(ZZ_pX& x, const ZZ_pX& a, long m);// x = a % X^minline ZZ_pX trunc(const ZZ_pX& a, long m)   { ZZ_pX x; trunc(x, a, m); NTL_OPT_RETURN(ZZ_pX, x); }void RightShift(ZZ_pX& x, const ZZ_pX& a, long n);// x = a/X^ninline ZZ_pX RightShift(const ZZ_pX& a, long n)   { ZZ_pX x; RightShift(x, a, n); NTL_OPT_RETURN(ZZ_pX, x); }void LeftShift(ZZ_pX& x, const ZZ_pX& a, long n);// x = a*X^ninline ZZ_pX LeftShift(const ZZ_pX& a, long n)   { ZZ_pX x; LeftShift(x, a, n); NTL_OPT_RETURN(ZZ_pX, x); }#ifndef NTL_TRANSITIONinline ZZ_pX operator>>(const ZZ_pX& a, long n)   { ZZ_pX x; RightShift(x, a, n); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX operator<<(const ZZ_pX& a, long n)   { ZZ_pX x; LeftShift(x, a, n); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX& operator<<=(ZZ_pX& x, long n)   { LeftShift(x, x, n); return x; }inline ZZ_pX& operator>>=(ZZ_pX& x, long n)   { RightShift(x, x, n); return x; }#endifvoid diff(ZZ_pX& x, const ZZ_pX& a);// x = derivative of ainline ZZ_pX diff(const ZZ_pX& a)   { ZZ_pX x; diff(x, a); NTL_OPT_RETURN(ZZ_pX, x); }void MakeMonic(ZZ_pX& x);void reverse(ZZ_pX& c, const ZZ_pX& a, long hi);inline ZZ_pX reverse(const ZZ_pX& a, long hi)   { ZZ_pX x; reverse(x, a, hi); NTL_OPT_RETURN(ZZ_pX, x); }inline void reverse(ZZ_pX& c, const ZZ_pX& a){  reverse(c, a, deg(a)); }inline ZZ_pX reverse(const ZZ_pX& a)   { ZZ_pX x; reverse(x, a); NTL_OPT_RETURN(ZZ_pX, x); }inline void VectorCopy(vec_ZZ_p& x, const ZZ_pX& a, long n)   { VectorCopy(x, a.rep, n); }inline vec_ZZ_p VectorCopy(const ZZ_pX& a, long n)   { return VectorCopy(a.rep, n); }/*******************************************************************                        conversion routines********************************************************************/void conv(ZZ_pX& x, long a);void conv(ZZ_pX& x, const ZZ& a);void conv(ZZ_pX& x, const ZZ_p& a);void conv(ZZ_pX& x, const vec_ZZ_p& a);inline ZZ_pX to_ZZ_pX(long a)   { ZZ_pX x; conv(x, a); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX to_ZZ_pX(const ZZ& a)   { ZZ_pX x; conv(x, a); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX to_ZZ_pX(const ZZ_p& a)   { ZZ_pX x; conv(x, a); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX to_ZZ_pX(const vec_ZZ_p& a)   { ZZ_pX x; conv(x, a); NTL_OPT_RETURN(ZZ_pX, x); }/*************************************************************                        Comparison**************************************************************/long IsZero(const ZZ_pX& a); long IsOne(const ZZ_pX& a);inline long operator==(const ZZ_pX& a, const ZZ_pX& b){   return a.rep == b.rep;}inline long operator!=(const ZZ_pX& a, const ZZ_pX& b){   return !(a == b);}long operator==(const ZZ_pX& a, long b);long operator==(const ZZ_pX& a, const ZZ_p& b);inline long operator==(long a, const ZZ_pX& b) { return b == a; }inline long operator==(const ZZ_p& a, const ZZ_pX& b) { return b == a; }inline long operator!=(const ZZ_pX& a, long b) { return !(a == b); }inline long operator!=(const ZZ_pX& a, const ZZ_p& b) { return !(a == b); }inline long operator!=(long a, const ZZ_pX& b) { return !(a == b); }inline long operator!=(const ZZ_p& a, const ZZ_pX& b) { return !(a == b); }/***************************************************************                         Addition****************************************************************/void add(ZZ_pX& x, const ZZ_pX& a, const ZZ_pX& b);// x = a + bvoid sub(ZZ_pX& x, const ZZ_pX& a, const ZZ_pX& b);// x = a - bvoid negate(ZZ_pX& x, const ZZ_pX& a);// x = -a// scalar versionsvoid add(ZZ_pX& x, const ZZ_pX& a, const ZZ_p& b); // x = a + bvoid add(ZZ_pX& x, const ZZ_pX& a, long b);inline void add(ZZ_pX& x, const ZZ_p& a, const ZZ_pX& b) { add(x, b, a); }inline void add(ZZ_pX& x, long a, const ZZ_pX& b) { add(x, b, a); }void sub(ZZ_pX & x, const ZZ_pX& a, const ZZ_p& b); // x = a - bvoid sub(ZZ_pX& x, const ZZ_pX& a, long b);void sub(ZZ_pX& x, const ZZ_pX& a, const ZZ_p& b);void sub(ZZ_pX& x, long a, const ZZ_pX& b);void sub(ZZ_pX& x, const ZZ_p& a, const ZZ_pX& b);inline ZZ_pX operator+(const ZZ_pX& a, const ZZ_pX& b)   { ZZ_pX x; add(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX operator+(const ZZ_pX& a, const ZZ_p& b)   { ZZ_pX x; add(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX operator+(const ZZ_pX& a, long b)   { ZZ_pX x; add(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX operator+(const ZZ_p& a, const ZZ_pX& b)   { ZZ_pX x; add(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX operator+(long a, const ZZ_pX& b)   { ZZ_pX x; add(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX operator-(const ZZ_pX& a, const ZZ_pX& b)   { ZZ_pX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX operator-(const ZZ_pX& a, const ZZ_p& b)   { ZZ_pX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX operator-(const ZZ_pX& a, long b)   { ZZ_pX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX operator-(const ZZ_p& a, const ZZ_pX& b)   { ZZ_pX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX operator-(long a, const ZZ_pX& b)   { ZZ_pX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX& operator+=(ZZ_pX& x, const ZZ_pX& b)   { add(x, x, b); return x; }inline ZZ_pX& operator+=(ZZ_pX& x, const ZZ_p& b)   { add(x, x, b); return x; }inline ZZ_pX& operator+=(ZZ_pX& x, long b)   { add(x, x, b); return x; }inline ZZ_pX& operator-=(ZZ_pX& x, const ZZ_pX& b)   { sub(x, x, b); return x; }inline ZZ_pX& operator-=(ZZ_pX& x, const ZZ_p& b)   { sub(x, x, b); return x; }inline ZZ_pX& operator-=(ZZ_pX& x, long b)   { sub(x, x, b); return x; }inline ZZ_pX operator-(const ZZ_pX& a)    { ZZ_pX x; negate(x, a); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX& operator++(ZZ_pX& x) { add(x, x, 1); return x; }inline void operator++(ZZ_pX& x, int) { add(x, x, 1); }inline ZZ_pX& operator--(ZZ_pX& x) { sub(x, x, 1); return x; }inline void operator--(ZZ_pX& x, int) { sub(x, x, 1); }