zz_pex.h

使用NTL大整数库实现RSA公钥密码算法,可用于对文本文件进行加密和解密. 平台Windows98以上,VC++6.0, 内部文件路径均为相对路径,不存在无法编译的Bub.

inline void PowerXMod(ZZ_pEX& h, long e, const ZZ_pEXModulus& F)
   { PowerXMod(h, ZZ_expo(e), F); }


inline ZZ_pEX PowerXMod(const ZZ& e, const ZZ_pEXModulus& F)
   { ZZ_pEX x; PowerXMod(x, e, F);  NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX PowerXMod(long e, const ZZ_pEXModulus& F)
   { ZZ_pEX x; PowerXMod(x, e, F);  NTL_OPT_RETURN(ZZ_pEX, x); }


inline ZZ_pEX operator%(const ZZ_pEX& a, const ZZ_pEXModulus& F)
   { ZZ_pEX x; rem(x, a, F); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX& operator%=(ZZ_pEX& x, const ZZ_pEXModulus& F)
   { rem(x, x, F); return x; }

inline ZZ_pEX operator/(const ZZ_pEX& a, const ZZ_pEXModulus& F)
   { ZZ_pEX x; div(x, a, F); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX& operator/=(ZZ_pEX& x, const ZZ_pEXModulus& F)
   { div(x, x, F); return x; }



/*****************************************************************

                       vectors of ZZ_pEX's

*****************************************************************/



NTL_vector_decl(ZZ_pEX,vec_ZZ_pEX)

NTL_eq_vector_decl(ZZ_pEX,vec_ZZ_pEX)

NTL_io_vector_decl(ZZ_pEX,vec_ZZ_pEX)





/*******************************************************

              Evaluation and related problems

********************************************************/




void BuildFromRoots(ZZ_pEX& x, const vec_ZZ_pE& a);
inline ZZ_pEX BuildFromRoots(const vec_ZZ_pE& a)
   { ZZ_pEX x; BuildFromRoots(x, a); NTL_OPT_RETURN(ZZ_pEX, x); }
// computes the polynomial (X-a[0]) ... (X-a[n-1]), where n = a.length()


void eval(ZZ_pE& b, const ZZ_pEX& f, const ZZ_pE& a);
inline ZZ_pE eval(const ZZ_pEX& f, const ZZ_pE& a)
   { ZZ_pE x; eval(x, f, a); NTL_OPT_RETURN(ZZ_pE, x); }
// b = f(a)

void eval(vec_ZZ_pE& b, const ZZ_pEX& f, const vec_ZZ_pE& a);
inline vec_ZZ_pE eval(const ZZ_pEX& f, const vec_ZZ_pE& a)
   { vec_ZZ_pE x; eval(x, f, a); NTL_OPT_RETURN(vec_ZZ_pE, x); }
//  b[i] = f(a[i])

inline void eval(ZZ_pE& b, const ZZ_pX& f, const ZZ_pE& a)
   { conv(b, CompMod(f, rep(a), ZZ_pE::modulus())); }
   
inline ZZ_pE eval(const ZZ_pX& f, const ZZ_pE& a)
   { ZZ_pE x; eval(x, f, a); NTL_OPT_RETURN(ZZ_pE, x); }
// b = f(a)


void interpolate(ZZ_pEX& f, const vec_ZZ_pE& a, const vec_ZZ_pE& b);
inline ZZ_pEX interpolate(const vec_ZZ_pE& a, const vec_ZZ_pE& b)
   { ZZ_pEX x; interpolate(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }
// computes f such that f(a[i]) = b[i]





/**********************************************************

         Modular Composition and Minimal Polynomials

***********************************************************/



void CompMod(ZZ_pEX& x, const ZZ_pEX& g, const ZZ_pEX& h, const ZZ_pEXModulus& F);
inline ZZ_pEX 
CompMod(const ZZ_pEX& g, const ZZ_pEX& h, const ZZ_pEXModulus& F)
   { ZZ_pEX x; CompMod(x, g, h, F); NTL_OPT_RETURN(ZZ_pEX, x); }
// x = g(h) mod f

void Comp2Mod(ZZ_pEX& x1, ZZ_pEX& x2, const ZZ_pEX& g1, const ZZ_pEX& g2,
              const ZZ_pEX& h, const ZZ_pEXModulus& F);
// xi = gi(h) mod f (i=1,2)

void Comp3Mod(ZZ_pEX& x1, ZZ_pEX& x2, ZZ_pEX& x3, 
              const ZZ_pEX& g1, const ZZ_pEX& g2, const ZZ_pEX& g3,
              const ZZ_pEX& h, const ZZ_pEXModulus& 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_pEXArgBound > 0, then the table is limited in
// size to approximamtely that many KB.
// If ZZ_pEXArgBound <= 0, then it is ignored, and space is allocated
// so as to maximize speed.
// Initially, ZZ_pEXArgBound = 0.


// If a single h is going to be used with many g's
// then you should build a ZZ_pEXArgument 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_pEXArgBound > 0, a table of size less than m may be built.

struct ZZ_pEXArgument {
   vec_ZZ_pEX H;
};

extern long ZZ_pEXArgBound;


void build(ZZ_pEXArgument& H, const ZZ_pEX& h, const ZZ_pEXModulus& F, long m);

// m must be > 0, otherwise an error is raised

void CompMod(ZZ_pEX& x, const ZZ_pEX& g, const ZZ_pEXArgument& H, 
             const ZZ_pEXModulus& F);

inline ZZ_pEX 
CompMod(const ZZ_pEX& g, const ZZ_pEXArgument& H, const ZZ_pEXModulus& F)
   { ZZ_pEX x; CompMod(x, g, H, F); NTL_OPT_RETURN(ZZ_pEX, x); }
   



void MinPolySeq(ZZ_pEX& h, const vec_ZZ_pE& a, long m);
inline ZZ_pEX MinPolySeq(const vec_ZZ_pE& a, long m)
   { ZZ_pEX x; MinPolySeq(x, a, m); NTL_OPT_RETURN(ZZ_pEX, x); }


void MinPolyMod(ZZ_pEX& hh, const ZZ_pEX& g, const ZZ_pEXModulus& F);
inline ZZ_pEX MinPolyMod(const ZZ_pEX& g, const ZZ_pEXModulus& F)
   { ZZ_pEX x; MinPolyMod(x, g, F); NTL_OPT_RETURN(ZZ_pEX, x); }


void MinPolyMod(ZZ_pEX& hh, const ZZ_pEX& g, const ZZ_pEXModulus& F, long m);
inline ZZ_pEX MinPolyMod(const ZZ_pEX& g, const ZZ_pEXModulus& F, long m)
   { ZZ_pEX x; MinPolyMod(x, g, F, m); NTL_OPT_RETURN(ZZ_pEX, x); }

void ProbMinPolyMod(ZZ_pEX& hh, const ZZ_pEX& g, const ZZ_pEXModulus& F);
inline ZZ_pEX ProbMinPolyMod(const ZZ_pEX& g, const ZZ_pEXModulus& F)
   { ZZ_pEX x; ProbMinPolyMod(x, g, F); NTL_OPT_RETURN(ZZ_pEX, x); }

void ProbMinPolyMod(ZZ_pEX& hh, const ZZ_pEX& g, const ZZ_pEXModulus& F, long m);
inline ZZ_pEX ProbMinPolyMod(const ZZ_pEX& g, const ZZ_pEXModulus& F, long m)
   { ZZ_pEX x; ProbMinPolyMod(x, g, F, m); NTL_OPT_RETURN(ZZ_pEX, x); }

void IrredPolyMod(ZZ_pEX& h, const ZZ_pEX& g, const ZZ_pEXModulus& F);
inline ZZ_pEX IrredPolyMod(const ZZ_pEX& g, const ZZ_pEXModulus& F)
   { ZZ_pEX x; IrredPolyMod(x, g, F); NTL_OPT_RETURN(ZZ_pEX, x); }

void IrredPolyMod(ZZ_pEX& h, const ZZ_pEX& g, const ZZ_pEXModulus& F, long m);
inline ZZ_pEX IrredPolyMod(const ZZ_pEX& g, const ZZ_pEXModulus& F, long m)
   { ZZ_pEX x; IrredPolyMod(x, g, F, m); NTL_OPT_RETURN(ZZ_pEX, x); }


struct ZZ_pEXTransMultiplier {
   ZZ_pEX f0, fbi, b;
   long shamt, shamt_fbi, shamt_b;
};

void build(ZZ_pEXTransMultiplier& B, const ZZ_pEX& b, const ZZ_pEXModulus& F);

void TransMulMod(ZZ_pEX& x, const ZZ_pEX& a, const ZZ_pEXTransMultiplier& B,
               const ZZ_pEXModulus& F);

void UpdateMap(vec_ZZ_pE& x, const vec_ZZ_pE& a, 
         const ZZ_pEXTransMultiplier& B, const ZZ_pEXModulus& F);

inline vec_ZZ_pE UpdateMap(const vec_ZZ_pE& a,
         const ZZ_pEXTransMultiplier& B, const ZZ_pEXModulus& F)
   { vec_ZZ_pE x; UpdateMap(x, a, B, F); NTL_OPT_RETURN(vec_ZZ_pE, x); }

void ProjectPowers(vec_ZZ_pE& x, const vec_ZZ_pE& a, long k, 
                   const ZZ_pEXArgument& H, const ZZ_pEXModulus& F);
inline vec_ZZ_pE ProjectPowers(const vec_ZZ_pE& a, long k, 
                   const ZZ_pEXArgument& H, const ZZ_pEXModulus& F)
   { vec_ZZ_pE x; ProjectPowers(x, a, k, H, F); NTL_OPT_RETURN(vec_ZZ_pE, x); }

void ProjectPowers(vec_ZZ_pE& x, const vec_ZZ_pE& a, long k, const ZZ_pEX& h, 
                   const ZZ_pEXModulus& F);
inline vec_ZZ_pE ProjectPowers(const vec_ZZ_pE& a, long k, 
                   const ZZ_pEX& H, const ZZ_pEXModulus& F)
   { vec_ZZ_pE x; ProjectPowers(x, a, k, H, F); NTL_OPT_RETURN(vec_ZZ_pE, x); }

inline void project(ZZ_pE& x, const vec_ZZ_pE& a, const ZZ_pEX& b)
   { InnerProduct(x, a, b.rep); }

inline ZZ_pE project(const vec_ZZ_pE& a, const ZZ_pEX& b)
   { ZZ_pE x; InnerProduct(x, a, b.rep); NTL_OPT_RETURN(ZZ_pE, x); }



/*****************************************************************

          modular composition and minimal polynonomials
                         in towers

******************************************************************/


// composition

void CompTower(ZZ_pEX& x, const ZZ_pX& g, const ZZ_pEXArgument& A,
             const ZZ_pEXModulus& F);

inline ZZ_pEX CompTower(const ZZ_pX& g, const ZZ_pEXArgument& A,
             const ZZ_pEXModulus& F)
   { ZZ_pEX x; CompTower(x, g, A, F); NTL_OPT_RETURN(ZZ_pEX, x); }

void CompTower(ZZ_pEX& x, const ZZ_pX& g, const ZZ_pEX& h,
             const ZZ_pEXModulus& F);

inline ZZ_pEX CompTower(const ZZ_pX& g, const ZZ_pEX& h,
             const ZZ_pEXModulus& F)
   { ZZ_pEX x; CompTower(x, g, h, F); NTL_OPT_RETURN(ZZ_pEX, x); }

// prob min poly

void ProbMinPolyTower(ZZ_pX& h, const ZZ_pEX& g, const ZZ_pEXModulus& F,
                      long m);

inline ZZ_pX ProbMinPolyTower(const ZZ_pEX& g, const ZZ_pEXModulus& F,
                      long m)
   { ZZ_pX x; ProbMinPolyTower(x, g, F, m); NTL_OPT_RETURN(ZZ_pX, x); }

inline void ProbMinPolyTower(ZZ_pX& h, const ZZ_pEX& g, 
                             const ZZ_pEXModulus& F)
   { ProbMinPolyTower(h, g, F, deg(F)*ZZ_pE::degree()); }

inline ZZ_pX ProbMinPolyTower(const ZZ_pEX& g, const ZZ_pEXModulus& F)
   { ZZ_pX x; ProbMinPolyTower(x, g, F); NTL_OPT_RETURN(ZZ_pX, x); }


// min poly


void MinPolyTower(ZZ_pX& h, const ZZ_pEX& g, const ZZ_pEXModulus& F,
                      long m);

inline ZZ_pX MinPolyTower(const ZZ_pEX& g, const ZZ_pEXModulus& F,
                      long m)
   { ZZ_pX x; MinPolyTower(x, g, F, m); NTL_OPT_RETURN(ZZ_pX, x); }

inline void MinPolyTower(ZZ_pX& h, const ZZ_pEX& g, const ZZ_pEXModulus& F)
   { MinPolyTower(h, g, F, deg(F)*ZZ_pE::degree()); }


inline ZZ_pX MinPolyTower(const ZZ_pEX& g, const ZZ_pEXModulus& F)
   { ZZ_pX x; MinPolyTower(x, g, F); NTL_OPT_RETURN(ZZ_pX, x); }

// irred poly


void IrredPolyTower(ZZ_pX& h, const ZZ_pEX& g, const ZZ_pEXModulus& F,
                      long m);

inline ZZ_pX IrredPolyTower(const ZZ_pEX& g, const ZZ_pEXModulus& F,
                      long m)
   { ZZ_pX x; IrredPolyTower(x, g, F, m); NTL_OPT_RETURN(ZZ_pX, x); }

inline void IrredPolyTower(ZZ_pX& h, const ZZ_pEX& g, const ZZ_pEXModulus& F)
   { IrredPolyTower(h, g, F, deg(F)*ZZ_pE::degree()); }


inline ZZ_pX IrredPolyTower(const ZZ_pEX& g, const ZZ_pEXModulus& F)
   { ZZ_pX x; IrredPolyTower(x, g, F); NTL_OPT_RETURN(ZZ_pX, x); }

/*****************************************************************

                   Traces, norms, resultants

******************************************************************/

void TraceVec(vec_ZZ_pE& S, const ZZ_pEX& f);

inline vec_ZZ_pE TraceVec(const ZZ_pEX& f)
   { vec_ZZ_pE x; TraceVec(x, f); NTL_OPT_RETURN(vec_ZZ_pE, x); }


void TraceMod(ZZ_pE& x, const ZZ_pEX& a, const ZZ_pEXModulus& F);

inline ZZ_pE TraceMod(const ZZ_pEX& a, const ZZ_pEXModulus& F)
   { ZZ_pE x; TraceMod(x, a, F); NTL_OPT_RETURN(ZZ_pE, x); }

void TraceMod(ZZ_pE& x, const ZZ_pEX& a, const ZZ_pEX& f);

inline ZZ_pE TraceMod(const ZZ_pEX& a, const ZZ_pEX& f)
   { ZZ_pE x; TraceMod(x, a, f); NTL_OPT_RETURN(ZZ_pE, x); }





void NormMod(ZZ_pE& x, const ZZ_pEX& a, const ZZ_pEX& f);

inline ZZ_pE NormMod(const ZZ_pEX& a, const ZZ_pEX& f)
   { ZZ_pE x; NormMod(x, a, f); NTL_OPT_RETURN(ZZ_pE, x); }

void resultant(ZZ_pE& rres, const ZZ_pEX& a, const ZZ_pEX& b);

inline ZZ_pE resultant(const ZZ_pEX& a, const ZZ_pEX& b)
   { ZZ_pE x; resultant(x, a, b); NTL_OPT_RETURN(ZZ_pE, x); }


NTL_CLOSE_NNS

#endif