lzz_pex.h

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

#ifndef NTL_zz_pEX__H
#define NTL_zz_pEX__H

#include <NTL/vec_lzz_pE.h>

NTL_OPEN_NNS

class zz_pEX {

public:

vec_zz_pE rep;


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

          Constructors, Destructors, and Assignment

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


zz_pEX()
//  initial value 0

   { }


zz_pEX(INIT_SIZE_TYPE, long n) { rep.SetMaxLength(n); }

~zz_pEX() { }

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 zz_pEX& zero();

inline zz_pEX(long i, const zz_pE& c);
inline zz_pEX(long i, const zz_p& c);
inline zz_pEX(long i, long c);


inline zz_pEX& operator=(long a);
inline zz_pEX& operator=(const zz_p& a);
inline zz_pEX& operator=(const zz_pE& a);

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


};


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




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

                   Some utility routines

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


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

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

const zz_pE& LeadCoeff(const zz_pEX& a);
// zero if a == 0

const zz_pE& ConstTerm(const zz_pEX& a);
// zero if a == 0

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

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

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

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

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

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

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

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

   { x.rep.SetLength(0); }

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

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

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

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

void random(zz_pEX& x, long n);
inline zz_pEX random_zz_pEX(long n)
   { zz_pEX x; random(x, n); NTL_OPT_RETURN(zz_pEX, x); }
// generate a random polynomial of degree < n 

void trunc(zz_pEX& x, const zz_pEX& a, long m);
inline zz_pEX trunc(const zz_pEX& a, long m)
   { zz_pEX x; trunc(x, a, m);  NTL_OPT_RETURN(zz_pEX, x); }
// x = a % X^m

void RightShift(zz_pEX& x, const zz_pEX& a, long n);
inline zz_pEX RightShift(const zz_pEX& a, long n)
   { zz_pEX x; RightShift(x, a, n);  NTL_OPT_RETURN(zz_pEX, x); }
// x = a/X^n

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

#ifndef NTL_TRANSITION

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

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

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

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

#endif



void diff(zz_pEX& x, const zz_pEX& a);
inline zz_pEX diff(const zz_pEX& a)
   { zz_pEX x; diff(x, a);  NTL_OPT_RETURN(zz_pEX, x); }
// x = derivative of a



void MakeMonic(zz_pEX& x);

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

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

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

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

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

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






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

                        conversion routines

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



void conv(zz_pEX& x, long a);

void conv(zz_pEX& x, const ZZ& a);

void conv(zz_pEX& x, const zz_p& a);
void conv(zz_pEX& x, const zz_pX& a);
void conv(zz_pEX& x, const zz_pE& a);


void conv(zz_pEX& x, const vec_zz_pE& a);

inline zz_pEX to_zz_pEX(long a)
   { zz_pEX x; conv(x, a); NTL_OPT_RETURN(zz_pEX, x); }

inline zz_pEX to_zz_pEX(const ZZ& a)
   { zz_pEX x; conv(x, a); NTL_OPT_RETURN(zz_pEX, x); }

inline zz_pEX to_zz_pEX(const zz_p& a)
   { zz_pEX x; conv(x, a); NTL_OPT_RETURN(zz_pEX, x); }

inline zz_pEX to_zz_pEX(const zz_pX& a)
   { zz_pEX x; conv(x, a); NTL_OPT_RETURN(zz_pEX, x); }

inline zz_pEX to_zz_pEX(const zz_pE& a)
   { zz_pEX x; conv(x, a); NTL_OPT_RETURN(zz_pEX, x); }

inline zz_pEX to_zz_pEX(const vec_zz_pE& a)
   { zz_pEX x; conv(x, a); NTL_OPT_RETURN(zz_pEX, x); }

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

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

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


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

                        Comparison

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

long IsZero(const zz_pEX& a); 

long IsOne(const zz_pEX& a);

inline long operator==(const zz_pEX& a, const zz_pEX& b)
{ return a.rep == b.rep; }

long operator==(const zz_pEX& a, long b);
long operator==(const zz_pEX& a, const zz_p& b);
long operator==(const zz_pEX& a, const zz_pE& b);

inline long operator==(long a, const zz_pEX& b)
   { return (b == a); }
inline long operator==(const zz_p& a, const zz_pEX& b)
   { return (b == a); }
inline long operator==(const zz_pE& a, const zz_pEX& b)
   { return (b == a); }

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


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

                         Addition

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

void add(zz_pEX& x, const zz_pEX& a, const zz_pEX& b);

void sub(zz_pEX& x, const zz_pEX& a, const zz_pEX& b);

void negate(zz_pEX& x, const zz_pEX& a);

// scalar versions

void add(zz_pEX & x, const zz_pEX& a, long b); 
void add(zz_pEX & x, const zz_pEX& a, const zz_p& b); 
void add(zz_pEX & x, const zz_pEX& a, const zz_pE& b); 

inline void add(zz_pEX& x, const zz_pE& a, const zz_pEX& b)
   { add(x, b, a); }
inline void add(zz_pEX& x, const zz_p& a, const zz_pEX& b)
   { add(x, b, a); }
inline void add(zz_pEX& x, long a, const zz_pEX& b)
   { add(x, b, a); }

void sub(zz_pEX & x, const zz_pEX& a, long b); 
void sub(zz_pEX & x, const zz_pEX& a, const zz_p& b); 
void sub(zz_pEX & x, const zz_pEX& a, const zz_pE& b); 

void sub(zz_pEX& x, const zz_pE& a, const zz_pEX& b);
void sub(zz_pEX& x, const zz_p& a, const zz_pEX& b);
void sub(zz_pEX& x, long a, const zz_pEX& b);



inline zz_pEX operator+(const zz_pEX& 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_pE& b)
   { zz_pEX x; add(x, a, b); NTL_OPT_RETURN(zz_pEX, x); }

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

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

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

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

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); }