vec_ZZ_p tracevec;  // mutable   // but these will remain public   ZZ_pXModulus(const ZZ_pX& ff);   const ZZ_pX& val() const { return f; }   operator const ZZ_pX& () const { return f; }};inline long deg(const ZZ_pXModulus& F) { return F.n; }void build(ZZ_pXModulus& F, const ZZ_pX& f);// deg(f) > 0.void rem21(ZZ_pX& x, const ZZ_pX& a, const ZZ_pXModulus& F);// x = a % f// deg(a) <= 2(n-1), where n = F.n = deg(f)void rem(ZZ_pX& x, const ZZ_pX& a, const ZZ_pXModulus& F);// x = a % f, no restrictions on deg(a);  makes repeated calls to rem21inline ZZ_pX operator%(const ZZ_pX& a, const ZZ_pXModulus& F)   { ZZ_pX x; rem(x, a, F); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX& operator%=(ZZ_pX& x, const ZZ_pXModulus& F)   { rem(x, x, F); return x; } void DivRem(ZZ_pX& q, ZZ_pX& r, const ZZ_pX& a, const ZZ_pXModulus& F);void div(ZZ_pX& q, const ZZ_pX& a, const ZZ_pXModulus& F);inline ZZ_pX operator/(const ZZ_pX& a, const ZZ_pXModulus& F)   { ZZ_pX x; div(x, a, F); NTL_OPT_RETURN(ZZ_pX, x); }inline ZZ_pX& operator/=(ZZ_pX& x, const ZZ_pXModulus& F)   { div(x, x, F); return x; } void MulMod(ZZ_pX& x, const ZZ_pX& a, const ZZ_pX& b, const ZZ_pXModulus& F);// x = (a * b) % f// deg(a), deg(b) < ninline ZZ_pX MulMod(const ZZ_pX& a, const ZZ_pX& b, const ZZ_pXModulus& F)   { ZZ_pX x; MulMod(x, a, b, F); NTL_OPT_RETURN(ZZ_pX, x); }void SqrMod(ZZ_pX& x, const ZZ_pX& a, const ZZ_pXModulus& F);// x = a^2 % f// deg(a) < ninline ZZ_pX SqrMod(const ZZ_pX& a, const ZZ_pXModulus& F)   { ZZ_pX x; SqrMod(x, a, F); NTL_OPT_RETURN(ZZ_pX, x); }void PowerMod(ZZ_pX& x, const ZZ_pX& a, const ZZ& e, const ZZ_pXModulus& F);// x = a^e % f, e >= 0inline ZZ_pX PowerMod(const ZZ_pX& a, const ZZ& e, const ZZ_pXModulus& F)   { ZZ_pX x; PowerMod(x, a, e, F); NTL_OPT_RETURN(ZZ_pX, x); }inline void PowerMod(ZZ_pX& x, const ZZ_pX& a, long e, const ZZ_pXModulus& F)   { PowerMod(x, a, ZZ_expo(e), F); }inline ZZ_pX PowerMod(const ZZ_pX& a, long e, const ZZ_pXModulus& F)   { ZZ_pX x; PowerMod(x, a, e, F); NTL_OPT_RETURN(ZZ_pX, x); }void PowerXMod(ZZ_pX& x, const ZZ& e, const ZZ_pXModulus& F);// x = X^e % f, e >= 0inline ZZ_pX PowerXMod(const ZZ& e, const ZZ_pXModulus& F)   { ZZ_pX x; PowerXMod(x, e, F); NTL_OPT_RETURN(ZZ_pX, x); }inline void PowerXMod(ZZ_pX& x, long e, const ZZ_pXModulus& F)   { PowerXMod(x, ZZ_expo(e), F); }inline ZZ_pX PowerXMod(long e, const ZZ_pXModulus& F)   { ZZ_pX x; PowerXMod(x, e, F); NTL_OPT_RETURN(ZZ_pX, x); }void PowerXPlusAMod(ZZ_pX& x, const ZZ_p& a, const ZZ& e, const ZZ_pXModulus& F);// x = (X + a)^e % f, e >= 0inline ZZ_pX PowerXPlusAMod(const ZZ_p& a, const ZZ& e, const ZZ_pXModulus& F)   { ZZ_pX x; PowerXPlusAMod(x, a, e, F); NTL_OPT_RETURN(ZZ_pX, x); }inline void PowerXPlusAMod(ZZ_pX& x, const ZZ_p& a, long e, const ZZ_pXModulus& F)   { PowerXPlusAMod(x, a, ZZ_expo(e), F); }inline ZZ_pX PowerXPlusAMod(const ZZ_p& a, long e, const ZZ_pXModulus& F)   { ZZ_pX x; PowerXPlusAMod(x, a, e, F); NTL_OPT_RETURN(ZZ_pX, x); }// If you need to compute a * b % f for a fixed b, but for many a's// (for example, computing powers of b modulo f), it is// much more efficient to first build a ZZ_pXMultiplier B for b,// and then use the routine below.class ZZ_pXMultiplier {public:   ZZ_pXMultiplier() : UseFFT(0)  { }   ZZ_pXMultiplier(const ZZ_pX& b, const ZZ_pXModulus& F);   ~ZZ_pXMultiplier() { }   // the following members may become private in the future   ZZ_pX b;      long UseFFT;   FFTRep B1;    FFTRep B2;    // but this will remain public   const ZZ_pX& val() const { return b; }};void build(ZZ_pXMultiplier& B, const ZZ_pX& b, const ZZ_pXModulus& F);void MulMod(ZZ_pX& x, const ZZ_pX& a, const ZZ_pXMultiplier& B,                                      const ZZ_pXModulus& F);inline ZZ_pX MulMod(const ZZ_pX& a, const ZZ_pXMultiplier& B,                                          const ZZ_pXModulus& F)   { ZZ_pX x; MulMod(x, a, B, F); NTL_OPT_RETURN(ZZ_pX, x); }// x = (a * b) % f/*******************************************************              Evaluation and related problems********************************************************/void BuildFromRoots(ZZ_pX& x, const vec_ZZ_p& a);// computes the polynomial (X-a[0]) ... (X-a[n-1]), where n = a.length()inline ZZ_pX BuildFromRoots(const vec_ZZ_p& a)   { ZZ_pX x; BuildFromRoots(x, a); NTL_OPT_RETURN(ZZ_pX, x); }void eval(ZZ_p& b, const ZZ_pX& f, const ZZ_p& a);// b = f(a)inline ZZ_p eval(const ZZ_pX& f, const ZZ_p& a)   { ZZ_p x; eval(x, f, a); NTL_OPT_RETURN(ZZ_p, x); }void eval(vec_ZZ_p& b, const ZZ_pX& f, const vec_ZZ_p& a);//  b[i] = f(a[i])inline vec_ZZ_p eval(const ZZ_pX& f, const vec_ZZ_p& a)   { vec_ZZ_p x; eval(x, f, a); NTL_OPT_RETURN(vec_ZZ_p, x); }void interpolate(ZZ_pX& f, const vec_ZZ_p& a, const vec_ZZ_p& b);// computes f such that f(a[i]) = b[i]inline ZZ_pX interpolate(const vec_ZZ_p& a, const vec_ZZ_p& b)   { ZZ_pX x; interpolate(x, a, b); NTL_OPT_RETURN(ZZ_pX, x); }/*****************************************************************                       vectors of ZZ_pX's*****************************************************************/NTL_vector_decl(ZZ_pX,vec_ZZ_pX)NTL_eq_vector_decl(ZZ_pX,vec_ZZ_pX)NTL_io_vector_decl(ZZ_pX,vec_ZZ_pX)/**********************************************************         Modular Composition and Minimal Polynomials***********************************************************/// algorithms for computing g(h) mod fvoid CompMod(ZZ_pX& x, const ZZ_pX& g, const ZZ_pX& h, const ZZ_pXModulus& F);// x = g(h) mod finline ZZ_pX CompMod(const ZZ_pX& g, const ZZ_pX& h,                            const ZZ_pXModulus& F)   { ZZ_pX x; CompMod(x, g, h, F); NTL_OPT_RETURN(ZZ_pX, x); }void Comp2Mod(ZZ_pX& x1, ZZ_pX& x2, const ZZ_pX& g1, const ZZ_pX& g2,              const ZZ_pX& h, const ZZ_pXModulus& F);// xi = gi(h) mod f (i=1,2)void Comp3Mod(ZZ_pX& x1, ZZ_pX& x2, ZZ_pX& x3,               const ZZ_pX& g1, const ZZ_pX& g2, const ZZ_pX& g3,              const ZZ_pX& h, const ZZ_pXModulus& F);// xi = gi(h) mod f (i=1..3)// The routine build (see below) which is implicitly called// by the various compose and UpdateMap routines builds a table// of polynomials.  // If ZZ_pXArgBound > 0, then the table is limited in// size to approximamtely that many KB.// If ZZ_pXArgBound <= 0, then it is ignored, and space is allocated// so as to maximize speed.// Initially, ZZ_pXArgBound = 0.// If a single h is going to be used with many g's// then you should build a ZZ_pXArgument for h,// and then use the compose routine below.// build computes and stores h, h^2, ..., h^m mod f.// After this pre-computation, composing a polynomial of degree // roughly n with h takes n/m multiplies mod f, plus n^2// scalar multiplies.// Thus, increasing m increases the space requirement and the pre-computation// time, but reduces the composition time.// If ZZ_pXArgBound > 0, a table of size less than m may be built.struct ZZ_pXArgument {   vec_ZZ_pX H;};extern long ZZ_pXArgBound;void build(ZZ_pXArgument& H, const ZZ_pX& h, const ZZ_pXModulus& F, long m);// m must be > 0, otherwise an error is raisedvoid CompMod(ZZ_pX& x, const ZZ_pX& g, const ZZ_pXArgument& H,              const ZZ_pXModulus& F);inline ZZ_pX CompMod(const ZZ_pX& g, const ZZ_pXArgument& H, const ZZ_pXModulus& F)   { ZZ_pX x; CompMod(x, g, H, F); NTL_OPT_RETURN(ZZ_pX, x); }#ifndef NTL_TRANSITIONvoid UpdateMap(vec_ZZ_p& x, const vec_ZZ_p& a,               const ZZ_pXMultiplier& B, const ZZ_pXModulus& F);inline vec_ZZ_pUpdateMap(const vec_ZZ_p& a,           const ZZ_pXMultiplier& B, const ZZ_pXModulus& F)   { vec_ZZ_p x; UpdateMap(x, a, B, F);      NTL_OPT_RETURN(vec_ZZ_p, x); }#endif/* computes (a, b), (a, (b*X)%f), ..., (a, (b*X^{n-1})%f),   where ( , ) denotes the vector inner product.   This is really a "transposed" MulMod by B.*/void PlainUpdateMap(vec_ZZ_p& x, const vec_ZZ_p& a,                    const ZZ_pX& b, const ZZ_pX& f);// same as above, but uses only classical arithmeticvoid ProjectPowers(vec_ZZ_p& x, const vec_ZZ_p& a, long k,                   const ZZ_pX& h, const ZZ_pXModulus& F);inline vec_ZZ_p ProjectPowers(const vec_ZZ_p& a, long k,                   const ZZ_pX& h, const ZZ_pXModulus& F){   vec_ZZ_p x;   ProjectPowers(x, a, k, h, F);   NTL_OPT_RETURN(vec_ZZ_p, x);}// computes (a, 1), (a, h), ..., (a, h^{k-1} % f)// this is really a "transposed" compose.void ProjectPowers(vec_ZZ_p& x, const vec_ZZ_p& a, long k,                   const ZZ_pXArgument& H, const ZZ_pXModulus& F);inline vec_ZZ_p ProjectPowers(const vec_ZZ_p& a, long k,                   const ZZ_pXArgument& H, const ZZ_pXModulus& F){   vec_ZZ_p x;   ProjectPowers(x, a, k, H, F);   NTL_OPT_RETURN(vec_ZZ_p, x);}// same as above, but uses a pre-computed ZZ_pXArgumentinline void project(ZZ_p& x, const vec_ZZ_p& a, const ZZ_pX& b)   { InnerProduct(x, a, b.rep); }inline ZZ_p project(const vec_ZZ_p& a, const ZZ_pX& b)   {  ZZ_p x; project(x, a, b); NTL_OPT_RETURN(ZZ_p, x); }void MinPolySeq(ZZ_pX& h, const vec_ZZ_p& a, long m);// computes the minimum polynomial of a linealy generated sequence;// m is a bound on the degree of the polynomial;// required: a.length() >= 2*minline ZZ_pX MinPolySeq(const vec_ZZ_p& a, long m)   { ZZ_pX x; MinPolySeq(x, a, m); NTL_OPT_RETURN(ZZ_pX, x); }void ProbMinPolyMod(ZZ_pX& h, const ZZ_pX& g, const ZZ_pXModulus& F, long m);inline ZZ_pX ProbMinPolyMod(const ZZ_pX& g, const ZZ_pXModulus& F, long m)   { ZZ_pX x; ProbMinPolyMod(x, g, F, m); NTL_OPT_RETURN(ZZ_pX, x); }inline void ProbMinPolyMod(ZZ_pX& h, const ZZ_pX& g, const ZZ_pXModulus& F)   { ProbMinPolyMod(h, g, F, F.n); }inline ZZ_pX ProbMinPolyMod(const ZZ_pX& g, const ZZ_pXModulus& F)   { ZZ_pX x; ProbMinPolyMod(x, g, F); NTL_OPT_RETURN(ZZ_pX, x); }// computes the monic minimal polynomial if (g mod f).// m = a bound on the degree of the minimal polynomial.// If this argument is not supplied, it defaults to deg(f).// The algorithm is probabilistic, always returns a divisor of// the minimal polynomial, and returns a proper divisor with// probability at most m/p.void MinPolyMod(ZZ_pX& h, const ZZ_pX& g, const ZZ_pXModulus& F, long m);inline ZZ_pX MinPolyMod(const ZZ_pX& g, const ZZ_pXModulus& F, long m)   { ZZ_pX x; MinPolyMod(x, g, F, m); NTL_OPT_RETURN(ZZ_pX, x); }inline void MinPolyMod(ZZ_pX& h, const ZZ_pX& g, const ZZ_pXModulus& F)   { MinPolyMod(h, g, F, F.n); }inline ZZ_pX MinPolyMod(const ZZ_pX& g, const ZZ_pXModulus& F)   { ZZ_pX x; MinPolyMod(x, g, F); NTL_OPT_RETURN(ZZ_pX, x); }// same as above, but guarantees that result is correctvoid IrredPolyMod(ZZ_pX& h, const ZZ_pX& g, const ZZ_pXModulus& F, long m);inline ZZ_pX IrredPolyMod(const ZZ_pX& g, const ZZ_pXModulus& F, long m)   { ZZ_pX x; IrredPolyMod(x, g, F, m); NTL_OPT_RETURN(ZZ_pX, x); }inline void IrredPolyMod(ZZ_pX& h, const ZZ_pX& g, const ZZ_pXModulus& F)   { IrredPolyMod(h, g, F, F.n); }inline ZZ_pX IrredPolyMod(const ZZ_pX& g, const ZZ_pXModulus& F)   { ZZ_pX x; IrredPolyMod(x, g, F); NTL_OPT_RETURN(ZZ_pX, x); }// same as above, but assumes that f is irreducible, // or at least that the minimal poly of g is itself irreducible.// The algorithm is deterministic (and is always correct)./*****************************************************************                   Traces, norms, resultants******************************************************************/void TraceVec(vec_ZZ_p& S, const ZZ_pX& f);inline vec_ZZ_p TraceVec(const ZZ_pX& f)   { vec_ZZ_p x; TraceVec(x, f); NTL_OPT_RETURN(vec_ZZ_p, x); }void FastTraceVec(vec_ZZ_p& S, const ZZ_pX& f);void PlainTraceVec(vec_ZZ_p& S, const ZZ_pX& f);void TraceMod(ZZ_p& x, const ZZ_pX& a, const ZZ_pXModulus& F);inline ZZ_p TraceMod(const ZZ_pX& a, const ZZ_pXModulus& F)   { ZZ_p x; TraceMod(x, a, F); NTL_OPT_RETURN(ZZ_p, x); }void TraceMod(ZZ_p& x, const ZZ_pX& a, const ZZ_pX& f);inline ZZ_p TraceMod(const ZZ_pX& a, const ZZ_pX& f)   { ZZ_p x; TraceMod(x, a, f); NTL_OPT_RETURN(ZZ_p, x); }void ComputeTraceVec(const ZZ_pXModulus& F);void NormMod(ZZ_p& x, const ZZ_pX& a, const ZZ_pX& f);inline ZZ_p NormMod(const ZZ_pX& a, const ZZ_pX& f)   { ZZ_p x; NormMod(x, a, f); NTL_OPT_RETURN(ZZ_p, x); }void resultant(ZZ_p& rres, const ZZ_pX& a, const ZZ_pX& b);inline ZZ_p resultant(const ZZ_pX& a, const ZZ_pX& b)   { ZZ_p x; resultant(x, a, b); NTL_OPT_RETURN(ZZ_p, x); }void CharPolyMod(ZZ_pX& g, const ZZ_pX& a, const ZZ_pX& f);// g = char poly of (a mod f)inline ZZ_pX CharPolyMod(const ZZ_pX& a, const ZZ_pX& f)   { ZZ_pX x; CharPolyMod(x, a, f); NTL_OPT_RETURN(ZZ_pX, x); }NTL_CLOSE_NNS#endif