zz_pex.h

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

inline ZZ_pEX operator+(long a, const ZZ_pEX& b)
   { ZZ_pEX x; add(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }


inline ZZ_pEX operator-(const ZZ_pEX& a, const ZZ_pEX& b)
   { ZZ_pEX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator-(const ZZ_pEX& a, const ZZ_pE& b)
   { ZZ_pEX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator-(const ZZ_pEX& a, const ZZ_p& b)
   { ZZ_pEX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator-(const ZZ_pEX& a, long b)
   { ZZ_pEX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator-(const ZZ_pE& a, const ZZ_pEX& b)
   { ZZ_pEX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator-(const ZZ_p& a, const ZZ_pEX& b)
   { ZZ_pEX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator-(long a, const ZZ_pEX& b)
   { ZZ_pEX x; sub(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }


inline ZZ_pEX& operator+=(ZZ_pEX& x, const ZZ_pEX& b)
   { add(x, x, b); return x; }

inline ZZ_pEX& operator+=(ZZ_pEX& x, const ZZ_pE& b)
   { add(x, x, b); return x; }

inline ZZ_pEX& operator+=(ZZ_pEX& x, const ZZ_p& b)
   { add(x, x, b); return x; }

inline ZZ_pEX& operator+=(ZZ_pEX& x, long b)
   { add(x, x, b); return x; }

inline ZZ_pEX& operator-=(ZZ_pEX& x, const ZZ_pEX& b)
   { sub(x, x, b); return x; }

inline ZZ_pEX& operator-=(ZZ_pEX& x, const ZZ_pE& b)
   { sub(x, x, b); return x; }

inline ZZ_pEX& operator-=(ZZ_pEX& x, const ZZ_p& b)
   { sub(x, x, b); return x; }

inline ZZ_pEX& operator-=(ZZ_pEX& x, long b)
   { sub(x, x, b); return x; }


inline ZZ_pEX operator-(const ZZ_pEX& a) 
   { ZZ_pEX x; negate(x, a); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX& operator++(ZZ_pEX& x) { add(x, x, 1); return x; }
inline void operator++(ZZ_pEX& x, int) { add(x, x, 1); }
inline ZZ_pEX& operator--(ZZ_pEX& x) { sub(x, x, 1); return x; }
inline void operator--(ZZ_pEX& x, int) { sub(x, x, 1); }



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

                        Multiplication

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


void mul(ZZ_pEX& x, const ZZ_pEX& a, const ZZ_pEX& b);
// x = a * b

void sqr(ZZ_pEX& x, const ZZ_pEX& a);
inline ZZ_pEX sqr(const ZZ_pEX& a) 
   { ZZ_pEX x; sqr(x, a); NTL_OPT_RETURN(ZZ_pEX, x); }
// x = a^2


void mul(ZZ_pEX & x, const ZZ_pEX& a, long b); 
void mul(ZZ_pEX & x, const ZZ_pEX& a, const ZZ_p& b); 
void mul(ZZ_pEX & x, const ZZ_pEX& a, const ZZ_pE& b); 

inline void mul(ZZ_pEX& x, long a, const ZZ_pEX& b)
   { mul(x, b, a); }
inline void mul(ZZ_pEX& x, const ZZ_p& a, const ZZ_pEX& b)
   { mul(x, b, a); }
inline void mul(ZZ_pEX& x, const ZZ_pE& a, const ZZ_pEX& b)
   { mul(x, b, a); }

void MulTrunc(ZZ_pEX& x, const ZZ_pEX& a, const ZZ_pEX& b, long n);
inline ZZ_pEX MulTrunc(const ZZ_pEX& a, const ZZ_pEX& b, long n)
   { ZZ_pEX x; MulTrunc(x, a, b, n); NTL_OPT_RETURN(ZZ_pEX, x); }
// x = a * b % X^n

void SqrTrunc(ZZ_pEX& x, const ZZ_pEX& a, long n);
inline ZZ_pEX SqrTrunc(const ZZ_pEX& a, long n)
   { ZZ_pEX x; SqrTrunc(x, a, n); NTL_OPT_RETURN(ZZ_pEX, x); }
// x = a*a % X^n


inline ZZ_pEX operator*(const ZZ_pEX& a, const ZZ_pEX& b)
   { ZZ_pEX x; mul(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator*(const ZZ_pEX& a, const ZZ_pE& b)
   { ZZ_pEX x; mul(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator*(const ZZ_pEX& a, const ZZ_p& b)
   { ZZ_pEX x; mul(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator*(const ZZ_pEX& a, long b)
   { ZZ_pEX x; mul(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator*(const ZZ_pE& a, const ZZ_pEX& b)
   { ZZ_pEX x; mul(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator*(const ZZ_p& a, const ZZ_pEX& b)
   { ZZ_pEX x; mul(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX operator*(long a, const ZZ_pEX& b)
   { ZZ_pEX x; mul(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }

inline ZZ_pEX& operator*=(ZZ_pEX& x, const ZZ_pEX& b)
   { mul(x, x, b); return x; }

inline ZZ_pEX& operator*=(ZZ_pEX& x, const ZZ_pE& b)
   { mul(x, x, b); return x; }

inline ZZ_pEX& operator*=(ZZ_pEX& x, const ZZ_p& b)
   { mul(x, x, b); return x; }

inline ZZ_pEX& operator*=(ZZ_pEX& x, long b)
   { mul(x, x, b); return x; }


void power(ZZ_pEX& x, const ZZ_pEX& a, long e);
inline ZZ_pEX power(const ZZ_pEX& a, long e)
   { ZZ_pEX x; power(x, a, e); NTL_OPT_RETURN(ZZ_pEX, x); }





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

                      Division

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

void DivRem(ZZ_pEX& q, ZZ_pEX& r, const ZZ_pEX& a, const ZZ_pEX& b);
// q = a/b, r = a%b

void div(ZZ_pEX& q, const ZZ_pEX& a, const ZZ_pEX& b);
void div(ZZ_pEX& q, const ZZ_pEX& a, const ZZ_pE& b);
void div(ZZ_pEX& q, const ZZ_pEX& a, const ZZ_p& b);
void div(ZZ_pEX& q, const ZZ_pEX& a, long b);
// q = a/b

void rem(ZZ_pEX& r, const ZZ_pEX& a, const ZZ_pEX& b);
// r = a%b

long divide(ZZ_pEX& q, const ZZ_pEX& a, const ZZ_pEX& b);
// if b | a, sets q = a/b and returns 1; otherwise returns 0

long divide(const ZZ_pEX& a, const ZZ_pEX& b);
// if b | a, sets q = a/b and returns 1; otherwise returns 0

void InvTrunc(ZZ_pEX& x, const ZZ_pEX& a, long m);
inline ZZ_pEX InvTrunc(const ZZ_pEX& a, long m)
   { ZZ_pEX x; InvTrunc(x, a, m); NTL_OPT_RETURN(ZZ_pEX, x); }
// computes x = a^{-1} % X^m 
// constant term must be invertible


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

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

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

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

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

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

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

inline ZZ_pEX& operator/=(ZZ_pEX& x, long b)
   { div(x, x, b); return x; }


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

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



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

                         GCD's

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


void GCD(ZZ_pEX& x, const ZZ_pEX& a, const ZZ_pEX& b);
inline ZZ_pEX GCD(const ZZ_pEX& a, const ZZ_pEX& b)
   { ZZ_pEX x; GCD(x, a, b); NTL_OPT_RETURN(ZZ_pEX, x); }
// x = GCD(a, b),  x is always monic (or zero if a==b==0).

void XGCD(ZZ_pEX& d, ZZ_pEX& s, ZZ_pEX& t, const ZZ_pEX& a, const ZZ_pEX& b);
// d = gcd(a,b), a s + b t = d 


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

             Modular Arithmetic without pre-conditioning

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

// arithmetic mod f.
// all inputs and outputs are polynomials of degree less than deg(f).
// ASSUMPTION: f is assumed monic, and deg(f) > 0.
// NOTE: if you want to do many computations with a fixed f,
//       use the ZZ_pEXModulus data structure and associated routines below.



void MulMod(ZZ_pEX& x, const ZZ_pEX& a, const ZZ_pEX& b, const ZZ_pEX& f);
inline ZZ_pEX MulMod(const ZZ_pEX& a, const ZZ_pEX& b, const ZZ_pEX& f)
   { ZZ_pEX x; MulMod(x, a, b, f); NTL_OPT_RETURN(ZZ_pEX, x); }
// x = (a * b) % f

void SqrMod(ZZ_pEX& x, const ZZ_pEX& a, const ZZ_pEX& f);
inline ZZ_pEX SqrMod(const ZZ_pEX& a, const ZZ_pEX& f)
   { ZZ_pEX x; SqrMod(x, a, f); NTL_OPT_RETURN(ZZ_pEX, x); }
// x = a^2 % f

void MulByXMod(ZZ_pEX& x, const ZZ_pEX& a, const ZZ_pEX& f);
inline ZZ_pEX MulByXMod(const ZZ_pEX& a, const ZZ_pEX& f)
   { ZZ_pEX x; MulByXMod(x, a, f); NTL_OPT_RETURN(ZZ_pEX, x); }
// x = (a * X) mod f

void InvMod(ZZ_pEX& x, const ZZ_pEX& a, const ZZ_pEX& f);
inline ZZ_pEX InvMod(const ZZ_pEX& a, const ZZ_pEX& f)
   { ZZ_pEX x; InvMod(x, a, f); NTL_OPT_RETURN(ZZ_pEX, x); }
// x = a^{-1} % f, error is a is not invertible

long InvModStatus(ZZ_pEX& x, const ZZ_pEX& a, const ZZ_pEX& f);
// if (a, f) = 1, returns 0 and sets x = a^{-1} % f
// otherwise, returns 1 and sets x = (a, f)





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

        Modular Arithmetic with Pre-conditioning

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


// If you need to do a lot of arithmetic modulo a fixed f,
// build ZZ_pEXModulus F for f.  This pre-computes information about f
// that speeds up the computation a great deal.

class ZZ_pEXModulus {
public:
   ZZ_pEXModulus();
   ~ZZ_pEXModulus();

   ZZ_pEXModulus(const ZZ_pEX& ff);

   ZZ_pEX f;   // the modulus

   operator const ZZ_pEX& () const { return f; }
   const ZZ_pEX& val() const { return f; }

   long n; //  deg(f)

   long method;

   ZZ_pEX h0;
   ZZ_pE hlc;
   ZZ_pEX f0;

   vec_ZZ_pE tracevec; // mutable

}; 



inline long deg(const ZZ_pEXModulus& F) { return F.n; }


void build(ZZ_pEXModulus& F, const ZZ_pEX& f);

void rem(ZZ_pEX& r, const ZZ_pEX& a, const ZZ_pEXModulus& F);
   
void DivRem(ZZ_pEX& q, ZZ_pEX& r, const ZZ_pEX& a, const ZZ_pEXModulus& F);

void div(ZZ_pEX& q, const ZZ_pEX& a, const ZZ_pEXModulus& F);

void MulMod(ZZ_pEX& c, const ZZ_pEX& a, const ZZ_pEX& b, 
            const ZZ_pEXModulus& F);
inline ZZ_pEX MulMod(const ZZ_pEX& a, const ZZ_pEX& b, 
            const ZZ_pEXModulus& F)
   { ZZ_pEX x; MulMod(x, a, b, F); NTL_OPT_RETURN(ZZ_pEX, x); }

void SqrMod(ZZ_pEX& c, const ZZ_pEX& a, const ZZ_pEXModulus& F);
inline ZZ_pEX SqrMod(const ZZ_pEX& a, const ZZ_pEXModulus& F)
   { ZZ_pEX x; SqrMod(x, a, F); NTL_OPT_RETURN(ZZ_pEX, x); }


void PowerMod(ZZ_pEX& h, const ZZ_pEX& g, const ZZ& e, const ZZ_pEXModulus& F);

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

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

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

void PowerXMod(ZZ_pEX& hh, const ZZ& e, const ZZ_pEXModulus& F);