zz.h

可以根据NTL库进RSA加密、解密算法的实现

#ifndef NTL_ZZ__H
#define NTL_ZZ__H



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

   LIP INTERFACE 

   The class ZZ implements signed, arbitrary length integers.

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


#include <NTL/lip.h>
#include <NTL/tools.h>

NTL_OPEN_NNS




class ZZ {
public:

NTL_verylong rep; // This is currently public for "emergency" situations
                   // May be private in future versions.


ZZ() 
// initial value is 0.

{ rep = 0; }


ZZ(INIT_SIZE_TYPE, long k)
// initial value is 0, but space is pre-allocated so that numbers
// x with x.size() <= k can be stored without re-allocation.
// Call with ZZ(INIT_SIZE, k).
// The purpose for the INIT_SIZE argument is to prevent automatic
// type conversion from long to ZZ, which would be tempting, but wrong.


{
   rep = 0;
   NTL_zsetlength(&rep, k); 
}

ZZ(const ZZ& a)
// initial value is a.

{
   rep = 0;
   NTL_zcopy(a.rep, &rep);
}


ZZ(INIT_VAL_TYPE, long a) { rep = 0; NTL_zintoz(a, &rep); }
ZZ(INIT_VAL_TYPE, int a) { rep = 0; NTL_zintoz(a, &rep); }

ZZ(INIT_VAL_TYPE, unsigned long a) { rep = 0; NTL_zuintoz(a, &rep); }
ZZ(INIT_VAL_TYPE, unsigned int a) { rep = 0; NTL_zuintoz((unsigned long) a, &rep); }

inline ZZ(INIT_VAL_TYPE, const char *);
inline ZZ(INIT_VAL_TYPE, float);
inline ZZ(INIT_VAL_TYPE, double);


ZZ& operator=(const ZZ& a) { NTL_zcopy(a.rep, &rep); return *this; }

ZZ& operator=(long a) { NTL_zintoz(a, &rep); return *this; }


~ZZ() { NTL_zfree(&rep); }

void kill()
// force the space held by this ZZ to be released.
// The value then becomes 0.

{ NTL_zfree(&rep); }

void SetSize(long k)
// pre-allocates space for k-digit numbers (base 2^NTL_ZZ_NBITS);  
// does not change the value.

{ NTL_zsetlength(&rep, k); }

long size() const
   { return NTL_zsize(rep); }

// returns the number of (NTL_ZZ_NBIT-bit) digits of |a|; the size of 0 is 0.


long SinglePrecision() const
   { return NTL_zsptest(rep); }

// tests if less than NTL_SP_BOUND in absolute value

long WideSinglePrecision() const
   { return NTL_zwsptest(rep); }

// tests if less than NTL_WSP_BOUND in absolute value

static const ZZ& zero();


ZZ(ZZ& x, INIT_TRANS_TYPE) { rep = x.rep; x.rep = 0; }
// used to cheaply hand off memory management of return value,
// without copying, assuming compiler implements the
// "return value optimization"

};



const ZZ& ZZ_expo(long e);


inline void clear(ZZ& x)
// x = 0

   { NTL_zzero(&x.rep); }

inline void set(ZZ& x)
// x = 1

   { NTL_zone(&x.rep); }


inline void swap(ZZ& x, ZZ& y)
// swap the values of x and y (swaps pointers only)

   { NTL_zswap(&x.rep, &y.rep); }


inline double log(const ZZ& a)
   { return NTL_zlog(a.rep); }




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

   Conversion routines.

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



inline void conv(ZZ& x, const ZZ& a) { x = a; }
inline ZZ to_ZZ(const ZZ& a) { return a; }

inline void conv(ZZ& x, long a) { NTL_zintoz(a, &x.rep); }
inline ZZ to_ZZ(long a) { return ZZ(INIT_VAL, a); }

inline void conv(ZZ& x, int a) { NTL_zintoz(long(a), &x.rep); }
inline ZZ to_ZZ(int a) { return ZZ(INIT_VAL, a); }

inline void conv(ZZ& x, unsigned long a) { NTL_zuintoz(a, &x.rep); }
inline ZZ to_ZZ(unsigned long a) { return ZZ(INIT_VAL, a); }

inline void conv(ZZ& x, unsigned int a) { NTL_zuintoz((unsigned long)(a), &x.rep); }
inline ZZ to_ZZ(unsigned int a) { return ZZ(INIT_VAL, a); }

void conv(ZZ& x, const char *s);
inline ZZ::ZZ(INIT_VAL_TYPE, const char *s) {  rep = 0; conv(*this, s); }
inline ZZ to_ZZ(const char *s) { return ZZ(INIT_VAL, s); }

inline void conv(ZZ& x, double a) { NTL_zdoubtoz(a, &x.rep); }
inline ZZ::ZZ(INIT_VAL_TYPE, double a) { rep = 0; conv(*this, a); }
inline ZZ to_ZZ(double a) { return ZZ(INIT_VAL, a); }

inline void conv(ZZ& x, float a) { NTL_zdoubtoz(double(a), &x.rep); }
inline ZZ::ZZ(INIT_VAL_TYPE, float a) { rep = 0; conv(*this, a); }
inline ZZ to_ZZ(float a) { return ZZ(INIT_VAL, a); }

inline void conv(long& x, const ZZ& a) { x = NTL_ztoint(a.rep); }
inline long to_long(const ZZ& a)  { return NTL_ztoint(a.rep); }

inline void conv(int& x, const ZZ& a) 
   { unsigned int res = (unsigned int) NTL_ztouint(a.rep); 
     x = NTL_UINT_TO_INT(res); }

inline int to_int(const ZZ& a)  
   { unsigned int res = (unsigned int) NTL_ztouint(a.rep); 
     return NTL_UINT_TO_INT(res); }

inline void conv(unsigned long& x, const ZZ& a) { x = NTL_ztouint(a.rep); }
inline unsigned long to_ulong(const ZZ& a)  { return NTL_ztouint(a.rep); }

inline void conv(unsigned int& x, const ZZ& a) 
   { x = (unsigned int)(NTL_ztouint(a.rep)); }
inline unsigned int to_uint(const ZZ& a)  
   { return (unsigned int)(NTL_ztouint(a.rep)); }

inline void conv(double& x, const ZZ& a) { x = NTL_zdoub(a.rep); }
inline double to_double(const ZZ& a) { return NTL_zdoub(a.rep); }

inline void conv(float& x, const ZZ& a) { x = float(NTL_zdoub(a.rep)); }
inline float to_float(const ZZ& a) { return float(NTL_zdoub(a.rep)); }

inline void ZZFromBytes(ZZ& x, const unsigned char *p, long n)
   { NTL_zfrombytes(&x.rep, p, n); }

inline ZZ ZZFromBytes(const unsigned char *p, long n)
   { ZZ x; ZZFromBytes(x, p, n); NTL_OPT_RETURN(ZZ, x); }

inline void BytesFromZZ(unsigned char *p, const ZZ& a, long n)
   { NTL_zbytesfromz(p, a.rep, n); }




// ****** comparisons


inline long sign(const ZZ& a)
// returns the sign of a (-1, 0, or 1).

   { return NTL_zsign(a.rep); }


inline long compare(const ZZ& a, const ZZ& b)
// returns the sign of a-b (-1, 0, or 1).

{
   return NTL_zcompare(a.rep, b.rep);
}

inline long IsZero(const ZZ& a)
// zero test

   { return NTL_ziszero(a.rep); }


inline long IsOne(const ZZ& a)
   { return NTL_zisone(a.rep); }
// test for 1
   

/* the usual comparison operators */

inline long operator==(const ZZ& a, const ZZ& b)
  { return NTL_zcompare(a.rep, b.rep) == 0; }
inline long operator!=(const ZZ& a, const ZZ& b)
  { return NTL_zcompare(a.rep, b.rep) != 0; }
inline long operator<(const ZZ& a, const ZZ& b)
  { return NTL_zcompare(a.rep, b.rep) < 0; }
inline long operator>(const ZZ& a, const ZZ& b)
  { return NTL_zcompare(a.rep, b.rep) > 0; }
inline long operator<=(const ZZ& a, const ZZ& b)
  { return NTL_zcompare(a.rep, b.rep) <= 0; }
inline long operator>=(const ZZ& a, const ZZ& b)
  { return NTL_zcompare(a.rep, b.rep) >= 0; }

/* single-precision versions of the above */

inline long compare(const ZZ& a, long b) { return NTL_zscompare(a.rep, b); }
inline long compare(long a, const ZZ& b) { return -NTL_zscompare(b.rep, a); }

inline long operator==(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) == 0; }
inline long operator!=(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) != 0; }
inline long operator<(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) < 0; }
inline long operator>(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) > 0; }
inline long operator<=(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) <= 0; }
inline long operator>=(const ZZ& a, long b) { return NTL_zscompare(a.rep, b) >= 0; }


inline long operator==(long a, const ZZ& b) { return b == a; }
inline long operator!=(long a, const ZZ& b) { return b != a; }
inline long operator<(long a, const ZZ& b) { return b > a; }
inline long operator>(long a, const ZZ& b) { return b < a; }
inline long operator<=(long a, const ZZ& b) { return b >= a; }
inline long operator>=(long a, const ZZ& b) { return b <= a; }

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

                 Addition

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


inline void add(ZZ& x, const ZZ& a, const ZZ& b)
// x = a + b

   { NTL_zadd(a.rep, b.rep, &x.rep); }

inline void sub(ZZ& x, const ZZ& a, const ZZ& b)
// x = a - b

   { NTL_zsub(a.rep, b.rep, &x.rep); }

inline void SubPos(ZZ& x, const ZZ& a, const ZZ& b)
// x = a - b;  assumes a >= b >= 0.

   { NTL_zsubpos(a.rep, b.rep, &x.rep); }

inline void negate(ZZ& x, const ZZ& a)
// x = -a

   { NTL_zcopy(a.rep, &x.rep); NTL_znegate(&x.rep); }

inline void abs(ZZ& x, const ZZ& a)
// x = |a|
{ NTL_zcopy(a.rep, &x.rep); NTL_zabs(&x.rep); }


/* single-precision versions of the above */

inline void add(ZZ& x, const ZZ& a, long b)
   { NTL_zsadd(a.rep, b, &x.rep); }

inline void add(ZZ& x, long a, const ZZ& b) { add(x, b, a); }


void sub(ZZ& x, const ZZ& a, long b);
void sub(ZZ& x, long a, const ZZ& b);

/* operator/function notation */

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

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

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

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

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

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

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

inline ZZ abs(const ZZ& a)
  { ZZ x; abs(x, a); NTL_OPT_RETURN(ZZ, x); }

/* op= notation */

inline ZZ& operator+=(ZZ& x, const ZZ& a)
  { add(x, x, a); return x; }

inline ZZ& operator+=(ZZ& x, long a)
  { add(x, x, a); return x; }

inline ZZ& operator-=(ZZ& x, const ZZ& a)
  { sub(x, x, a); return x; }

inline ZZ& operator-=(ZZ& x, long a)
  { sub(x, x, a); return x; }

/* inc/dec */

inline ZZ& operator++(ZZ& x) { add(x, x, 1); return x; }

inline void operator++(ZZ& x, int) { add(x, x, 1); }

inline ZZ& operator--(ZZ& x) { add(x, x, -1); return x; }

inline void operator--(ZZ& x, int) { add(x, x, -1); }



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

                 Multiplication.

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


inline void mul(ZZ& x, const ZZ& a, const ZZ& b)
// x = a * b

   { NTL_zmul(a.rep, b.rep, &x.rep); }


inline void sqr(ZZ& x, const ZZ& a)
// x = a*a

   { NTL_zsq(a.rep, &x.rep); }

inline ZZ sqr(const ZZ& a)
   { ZZ x; sqr(x, a); NTL_OPT_RETURN(ZZ, x); }


/* single-precision versions */

inline void mul(ZZ& x, const ZZ& a, long b)
   { NTL_zsmul(a.rep, b, &x.rep); }

inline void mul(ZZ& x, long a, const ZZ& b)
    { mul(x, b, a); }

/* operator notation */

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

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

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

/* op= notation */

inline ZZ& operator*=(ZZ& x, const ZZ& a)
  { mul(x, x, a); return x; }

inline ZZ& operator*=(ZZ& x, long a)
  { mul(x, x, a); return x; }


// Special routines for implementing CRT in ZZ_pX arithmetic


inline void ZZ_p_crt_struct_init(void **crt_struct, long n, const ZZ& p, 
                                 const long *primes)
    { NTL_crt_struct_init(crt_struct, n, p.rep, primes); }

inline void ZZ_p_crt_struct_insert(void *crt_struct, long i, const ZZ& m)
   { NTL_crt_struct_insert(crt_struct, i, m.rep); }

inline void ZZ_p_crt_struct_free(void *crt_struct)
   { NTL_crt_struct_free(crt_struct); }

inline void ZZ_p_crt_struct_eval(void *crt_struct, ZZ& t, const long *a)
   { NTL_crt_struct_eval(crt_struct, &t.rep, a); }

inline long ZZ_p_crt_struct_special(void *crt_struct)
   { return NTL_crt_struct_special(crt_struct); }

// Special routines for fast remaindering


inline void ZZ_p_rem_struct_init(void **rem_struct, long n, 
                                 const ZZ& p, long *primes)
   { NTL_rem_struct_init(rem_struct, n, p.rep, primes); }

inline void ZZ_p_rem_struct_free(void *rem_struct)
   { NTL_rem_struct_free(rem_struct); }


inline void ZZ_p_rem_struct_eval(void *rem_struct, long *x, const ZZ& a)
   { NTL_rem_struct_eval(rem_struct, x, a.rep); }



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

                    Division

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


inline void DivRem(ZZ& q, ZZ& r, const ZZ& a, const ZZ& b)
// q = [a/b], r = a - b*q
// |r| < |b|, and if r != 0, sign(r) = sign(b)

   { NTL_zdiv(a.rep, b.rep, &q.rep, &r.rep); }



inline void div(ZZ& q, const ZZ& a, const ZZ& b)
// q = a/b

   { NTL_zdiv(a.rep, b.rep, &q.rep, 0); }

inline void rem(ZZ& r, const ZZ& a, const ZZ& b)
// r = a%b

   { NTL_zmod(a.rep, b.rep, &r.rep); }


inline void QuickRem(ZZ& r, const ZZ& b)
// r = r%b
// assumes b > 0 and r >=0
// division is performed in place and may cause r to be re-allocated.

   { NTL_zquickmod(&r.rep, b.rep); }

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

long divide(const ZZ& a, const ZZ& b);
// if b | a, returns 1; otherwise returns 0.


/* non-standard single-precision versions */

inline long DivRem(ZZ& q, const ZZ& a, long b)
   { return NTL_zsdiv(a.rep, b, &q.rep); } 

inline long rem(const ZZ& a, long b)
   { return NTL_zsmod(a.rep, b); }


/* single precision versions */

inline void div(ZZ& q, const ZZ& a, long b)
   { (void) NTL_zsdiv(a.rep, b, &q.rep); }


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

long divide(const ZZ& a, long b);
// if b | a, returns 1; otherwise returns 0.


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

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

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

inline long operator%(const ZZ& a, long b)
   { return rem(a, b); }

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

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

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


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

                        GCD's

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


inline void GCD(ZZ& d, const ZZ& a, const ZZ& b)
// d = gcd(a, b)