zz_px.h

数值算法库for Windows

   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 rem21

inline 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) < n

inline 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) < n

inline 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 >= 0

inline 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 >= 0

inline 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 >= 0

inline 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 f



void CompMod(ZZ_pX& x, const ZZ_pX& g, const ZZ_pX& h, const ZZ_pXModulus& F);
// x = g(h) mod f

inline 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 raised

void 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_TRANSITION

void UpdateMap(vec_ZZ_p& x, const vec_ZZ_p& a,
               const ZZ_pXMultiplier& B, const ZZ_pXModulus& F);

inline vec_ZZ_p
UpdateMap(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 arithmetic


void 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_pXArgument

inline 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*m

inline 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 correct

void 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