lzz_px.h

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

#ifndef NTL_zz_pX__H
#define NTL_zz_pX__H

#include <NTL/vector.h>
#include <NTL/lzz_p.h>
#include <NTL/vec_lzz_p.h>

NTL_OPEN_NNS

// some cross-over points

#define NTL_zz_pX_MOD_CROSSOVER (zz_pX_mod_crossover[zz_pInfo->PrimeCnt])
#define NTL_zz_pX_MUL_CROSSOVER (zz_pX_mul_crossover[zz_pInfo->PrimeCnt])
#define NTL_zz_pX_NEWTON_CROSSOVER (zz_pX_newton_crossover[zz_pInfo->PrimeCnt])
#define NTL_zz_pX_DIV_CROSSOVER (zz_pX_div_crossover[zz_pInfo->PrimeCnt])
#define NTL_zz_pX_HalfGCD_CROSSOVER (zz_pX_halfgcd_crossover[zz_pInfo->PrimeCnt])
#define NTL_zz_pX_GCD_CROSSOVER (zz_pX_gcd_crossover[zz_pInfo->PrimeCnt])
#define NTL_zz_pX_BERMASS_CROSSOVER (zz_pX_bermass_crossover[zz_pInfo->PrimeCnt])
#define NTL_zz_pX_TRACE_CROSSOVER (zz_pX_trace_crossover[zz_pInfo->PrimeCnt])

extern long zz_pX_mod_crossover[];
extern long zz_pX_mul_crossover[];
extern long zz_pX_newton_crossover[];
extern long zz_pX_div_crossover[];
extern long zz_pX_halfgcd_crossover[];
extern long zz_pX_gcd_crossover[];
extern long zz_pX_bermass_crossover[];
extern long zz_pX_trace_crossover[];



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

                         zz_pX

The class zz_pX implements polynomial arithmetic modulo p.
Polynomials are represented as vec_zz_p's.
If f is a zz_pX, then f.rep is a vec_zz_p.
The zero polynomial is represented as a zero length vector.
Otherwise. f.rep[0] is the constant-term, and f.rep[f.rep.length()-1]
is the leading coefficient, which is always non-zero.
The member f.rep is public, so the vector representation is fully
accessible.
Use the member function normalize() to strip leading zeros.

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

class zz_pX {

public:

vec_zz_p rep;

typedef vec_zz_p VectorBaseType;


public:

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

          Constructors, Destructors, and Assignment

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


zz_pX()
//  initial value 0

   { }


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

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

inline zz_pX(long i, zz_p c);
inline zz_pX(long i, long c);

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

inline zz_pX& operator=(long a);
inline zz_pX& operator=(zz_p a);

~zz_pX() { }

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

zz_pX(zz_pX& 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 [ ]).
On input, the coefficients are arbitrary integers which are
then reduced modulo p, and leading zeros stripped.

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


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




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

                   Some utility routines

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


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

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

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

zz_p LeadCoeff(const zz_pX& a);
// zero if a == 0

zz_p ConstTerm(const zz_pX& a);
// zero if a == 0

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

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

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

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

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

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

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

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

   { x.rep.SetLength(0); }

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

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

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

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

void random(zz_pX& x, long n);
inline zz_pX random_zz_pX(long n)
   { zz_pX x; random(x, n); NTL_OPT_RETURN(zz_pX, x); }

// generate a random polynomial of degree < n 

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

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

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

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

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

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


#ifndef NTL_TRANSITION

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

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

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

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

#endif



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

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

void MakeMonic(zz_pX& x);
// makes x monic

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

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

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

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


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

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




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

                        conversion routines

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



void conv(zz_pX& x, long a);

inline zz_pX to_zz_pX(long a)
   { zz_pX x; conv(x, a); NTL_OPT_RETURN(zz_pX, x); }


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

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

void conv(zz_pX& x, zz_p a);

inline zz_pX to_zz_pX(zz_p a)
   { zz_pX x; conv(x, a); NTL_OPT_RETURN(zz_pX, x); }


void conv(zz_pX& x, const vec_zz_p& a);

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

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

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



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

                        Comparison

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

long IsZero(const zz_pX& a); 

long IsOne(const zz_pX& a);

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

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

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

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



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

                         Addition

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

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

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

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

// scalar versions

void add(zz_pX & x, const zz_pX& a, zz_p b); // x = a + b
inline void add(zz_pX& x, const zz_pX& a, long b) { add(x, a, to_zz_p(b)); }

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

void sub(zz_pX & x, const zz_pX& a, zz_p b); // x = a - b
inline void sub(zz_pX& x, const zz_pX& a, long b) { sub(x, a, to_zz_p(b)); }

void sub(zz_pX& x, zz_p a, const zz_pX& b);
inline void sub(zz_pX& x, long a, const zz_pX& b) { sub(x, to_zz_p(a), b); }

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

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

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

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

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


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

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

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

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

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


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

inline zz_pX& operator+=(zz_pX& x, zz_p b)
   { add(x, x, b); return x; }

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

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

inline zz_pX& operator-=(zz_pX& x, zz_p b)
   { sub(x, x, b); return x; }

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