zzx.h

密码大家Shoup写的数论算法c语言实现

#ifndef NTL_ZZX__H
#define NTL_ZZX__H

#include <NTL/vec_ZZ.h>
#include <NTL/lzz_pX.h>
#include <NTL/ZZ_pX.h>

NTL_OPEN_NNS


class ZZX {

public:

vec_ZZ rep;


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

          Constructors, Destructors, and Assignment

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


ZZX()
//  initial value 0

   { }


ZZX(INIT_SIZE_TYPE, long n) 
// initial value 0, but space is pre-allocated for n coefficients

   { rep.SetMaxLength(n); }

ZZX(const ZZX& a) : rep(a.rep) { }
// initial value is a


ZZX& operator=(const ZZX& a) 
   { rep = a.rep; return *this; }

~ZZX() { }

void normalize();
// strip leading zeros

void SetMaxLength(long n) 
// pre-allocate space for n coefficients.
// Value is unchanged

   { rep.SetMaxLength(n); }


void kill() 
// free space held by this polynomial.  Value becomes 0.

   { rep.kill(); }

static const ZZX& zero();

inline ZZX(long i, const ZZ& c);
inline ZZX(long i, long c);


inline ZZX& operator=(long a);
inline ZZX& operator=(const ZZ& a);


ZZX(ZZX& x, INIT_TRANS_TYPE) : rep(x.rep, INIT_TRANS) { }

};




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

                           input and output

I/O format:

   [a_0 a_1 ... a_n],

represents the polynomial a_0 + a_1*X + ... + a_n*X^n.

On output, all coefficients will be integers between 0 and p-1,
amd a_n not zero (the zero polynomial is [ ]).
Leading zeroes are stripped.

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


NTL_SNS istream& operator>>(NTL_SNS istream& s, ZZX& x);
NTL_SNS ostream& operator<<(NTL_SNS ostream& s, const ZZX& a);




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

                   Some utility routines

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


inline long deg(const ZZX& a) { return a.rep.length() - 1; }
// degree of a polynomial.
// note that the zero polynomial has degree -1.

const ZZ& coeff(const ZZX& a, long i);
// zero if i not in range

void GetCoeff(ZZ& x, const ZZX& a, long i);
// x = a[i], or zero if i not in range

const ZZ& LeadCoeff(const ZZX& a);
// zero if a == 0

const ZZ& ConstTerm(const ZZX& a);
// zero if a == 0

void SetCoeff(ZZX& x, long i, const ZZ& a);
// x[i] = a, error is raised if i < 0

void SetCoeff(ZZX& x, long i, long a);

inline ZZX::ZZX(long i, const ZZ& a)
   { SetCoeff(*this, i, a); }

inline ZZX::ZZX(long i, long a)
   { SetCoeff(*this, i, a); }

void SetCoeff(ZZX& x, long i);
// x[i] = 1, error is raised if i < 0

void SetX(ZZX& x);
// x is set to the monomial X

long IsX(const ZZX& a);
// test if x = X

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

   { x.rep.SetLength(0); }

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

   { x.rep.SetLength(1); set(x.rep[0]); }

inline void swap(ZZX& x, ZZX& y)
// swap x & y (only pointers are swapped)

   { swap(x.rep, y.rep); }

void trunc(ZZX& x, const ZZX& a, long m);
// x = a % X^m

inline ZZX trunc(const ZZX& a, long m)
   { ZZX x; trunc(x, a, m); NTL_OPT_RETURN(ZZX, x); }

void RightShift(ZZX& x, const ZZX& a, long n);
// x = a/X^n

inline ZZX RightShift(const ZZX& a, long n)
   { ZZX x; RightShift(x, a, n); NTL_OPT_RETURN(ZZX, x); }

void LeftShift(ZZX& x, const ZZX& a, long n);
// x = a*X^n

inline ZZX LeftShift(const ZZX& a, long n)
   { ZZX x; LeftShift(x, a, n); NTL_OPT_RETURN(ZZX, x); }


#ifndef NTL_TRANSITION

inline ZZX operator>>(const ZZX& a, long n)
   { ZZX x; RightShift(x, a, n); NTL_OPT_RETURN(ZZX, x); }

inline ZZX operator<<(const ZZX& a, long n)
   { ZZX x; LeftShift(x, a, n); NTL_OPT_RETURN(ZZX, x); }

inline ZZX& operator<<=(ZZX& x, long n) 
   { LeftShift(x, x, n); return x; }

inline ZZX& operator>>=(ZZX& x, long n) 
   { RightShift(x, x, n); return x; }

#endif


void diff(ZZX& x, const ZZX& a);
// x = derivative of a

inline ZZX diff(const ZZX& a)
   { ZZX x; diff(x, a); NTL_OPT_RETURN(ZZX, x); }

void InvTrunc(ZZX& x, const ZZX& a, long m);
// computes x = a^{-1} % X^m
// constant term must be non-zero

inline ZZX InvTrunc(const ZZX& a, long m)
   { ZZX x; InvTrunc(x, a, m); NTL_OPT_RETURN(ZZX, x); }

void MulTrunc(ZZX& x, const ZZX& a, const ZZX& b, long n);
// x = a * b % X^n

inline ZZX MulTrunc(const ZZX& a, const ZZX& b, long n)
   { ZZX x; MulTrunc(x, a, b, n); NTL_OPT_RETURN(ZZX, x); }

void SqrTrunc(ZZX& x, const ZZX& a, long n);
// x = a^2 % X^n

inline ZZX SqrTrunc(const ZZX& a, long n)
   { ZZX x; SqrTrunc(x, a, n); NTL_OPT_RETURN(ZZX, x); }

void reverse(ZZX& c, const ZZX& a, long hi);

inline ZZX reverse(const ZZX& a, long hi)
   { ZZX x; reverse(x, a, hi); NTL_OPT_RETURN(ZZX, x); }

inline void reverse(ZZX& c, const ZZX& a)
{  reverse(c, a, deg(a)); }

inline ZZX reverse(const ZZX& a)
   { ZZX x; reverse(x, a); NTL_OPT_RETURN(ZZX, x); }


inline void VectorCopy(vec_ZZ& x, const ZZX& a, long n)
   { VectorCopy(x, a.rep, n); }

inline vec_ZZ VectorCopy(const ZZX& a, long n)
   { return VectorCopy(a.rep, n); }







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

                        conversion routines

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


void conv(ZZX& x, long a);
inline ZZX to_ZZX(long a)
   { ZZX x; conv(x, a); NTL_OPT_RETURN(ZZX, x); }

inline ZZX& ZZX::operator=(long a)
   { conv(*this, a); return *this; }

void conv(ZZX& x, const ZZ& a);
inline ZZX to_ZZX(const ZZ& a)
   { ZZX x; conv(x, a); NTL_OPT_RETURN(ZZX, x); }

inline ZZX& ZZX::operator=(const ZZ& a)
   { conv(*this, a); return *this; }

void conv(ZZX& x, const vec_ZZ& a);
inline ZZX to_ZZX(const vec_ZZ& a)
   { ZZX x; conv(x, a); NTL_OPT_RETURN(ZZX, x); }

void conv(zz_pX& x, const ZZX& a);
inline zz_pX to_zz_pX(const ZZX& a)
   { zz_pX x; conv(x, a); NTL_OPT_RETURN(zz_pX, x); }

void conv(ZZ_pX& x, const ZZX& a);
inline ZZ_pX to_ZZ_pX(const ZZX& a)
   { ZZ_pX x; conv(x, a); NTL_OPT_RETURN(ZZ_pX, x); }

void conv(ZZX& x, const ZZ_pX& a);
inline ZZX to_ZZX(const ZZ_pX& a)
   { ZZX x; conv(x, a); NTL_OPT_RETURN(ZZX, x); }

void conv(ZZX& x, const zz_pX& a);
inline ZZX to_ZZX(const zz_pX& a)
   { ZZX x; conv(x, a); NTL_OPT_RETURN(ZZX, x); }



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

                        Comparison

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

long IsZero(const ZZX& a); 

long IsOne(const ZZX& a);

long operator==(const ZZX& a, const ZZX& b);

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

long operator==(const ZZX& a, const ZZ& b);
long operator==(const ZZX& a, long b);

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

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


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

                         Addition

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

void add(ZZX& x, const ZZX& a, const ZZX& b);
// x = a + b

void sub(ZZX& x, const ZZX& a, const ZZX& b);
// x = a - b

void negate(ZZX& x, const ZZX& a);
// x = -a

// scalar versions


void add(ZZX & x, const ZZX& a, const ZZ& b); // x = a + b
void add(ZZX& x, const ZZX& a, long b);

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


void sub(ZZX & x, const ZZX& a, const ZZ& b); // x = a - b
void sub(ZZX& x, const ZZX& a, long b);

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


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

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

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

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

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


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