zzx.txt

数值算法库for Windows

\**************************************************************************/


void GCD(ZZX& d, const ZZX& a, const ZZX& b);
ZZX GCD(const ZZX& a, const ZZX& b); 
// d = gcd(a, b), LeadCoeff(d) >= 0.  Uses a modular algorithm.


void XGCD(ZZ& r, ZZX& s, ZZX& t, const ZZX& a, const ZZX& b, 
          long deterministic=0);
// r = resultant of a and b; if r != 0, then computes s and t such
// that: a*s + b*t = r; otherwise s and t not affected.  if
// !deterministic, then resultant computation may use a randomized
// strategy that errs with probability no more than 2^{-80}.



/**************************************************************************\

                               Input/Output

I/O format:

   [a_0 a_1 ... a_n],

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


\**************************************************************************/


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


/**************************************************************************\

                             Some utility routines

\**************************************************************************/


long deg(const ZZX& a);  returns degree of a; deg(0) == -1

const ZZ& coeff(const ZZX& a, long i);
// returns a read-only reference to a.rep[i], or zero if i not in
// range

const ZZ& LeadCoeff(const ZZX& a);
// read-only reference to leading term of a, or zero if a == 0

const ZZ& ConstTerm(const ZZX& a);
// read-only reference to constant term of a, or zero if a == 0

void SetCoeff(ZZX& x, long i, const ZZ& a);
void SetCoeff(ZZX& x, long i, long a);
// makes coefficient of X^i equal to a; error is raised if i < 0

void SetCoeff(ZZX& x, long i);
// makes coefficient of X^i equal to 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

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

long MaxBits(const ZZX& f);
// returns max NumBits of coefficients of f

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

void reverse(ZZX& x, const ZZX& a);
ZZX reverse(const ZZX& a);

// x = reverse of a[0]..a[hi] (hi >= -1);
// hi defaults to deg(a) in second version


void VectorCopy(vec_ZZ& x, const ZZX& a, long n);
vec_ZZ VectorCopy(const ZZX& a, long n);
// x = copy of coefficient vector of a of length exactly n.
// input is truncated or padded with zeroes as appropriate.



/**************************************************************************\

                       Arithmetic mod X^n

All routines require n >= 0, otherwise an error is raised.

\**************************************************************************/


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

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

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

void InvTrunc(ZZX& x, const ZZX& a, long n);
ZZX InvTrunc(const ZZX& a, long n);
// computes x = a^{-1} % X^m.  Must have ConstTerm(a) invertible.




/**************************************************************************\

                               Modular Arithmetic

The modulus f must be monic with deg(f) > 0, 
and other arguments must have smaller degree.

\**************************************************************************/

void MulMod(ZZX& x, const ZZX& a, const ZZX& b, const ZZX& f);
ZZX MulMod(const ZZX& a, const ZZX& b, const ZZX& f);
// x = a * b mod f

void SqrMod(ZZX& x, const ZZX& a, const ZZX& f);
ZZX SqrMod(const ZZX& a, const ZZX& f);
// x = a^2 mod f

void MulByXMod(ZZX& x, const ZZX& a, const ZZX& f);
ZZX MulByXMod(const ZZX& a, const ZZX& f);
// x = a*X mod f


/**************************************************************************\

                  traces, norms, resultants, discriminants,
                   minimal and characteristic polynomials

\**************************************************************************/


void TraceMod(ZZ& res, const ZZX& a, const ZZX& f);
ZZ TraceMod(const ZZX& a, const ZZX& f);
// res = trace of (a mod f).  f must be monic, 0 < deg(f), deg(a) <
// deg(f)

void TraceVec(vec_ZZ& S, const ZZX& f);
vec_ZZ TraceVec(const ZZX& f);
// S[i] = Trace(X^i mod f), for i = 0..deg(f)-1.
// f must be a monic polynomial.


// The following routines use a modular approach.

void resultant(ZZ& res, const ZZX& a, const ZZX& b, long deterministic=0);
ZZ resultant(const ZZX& a, const ZZX& b, long deterministic=0);
// res = resultant of a and b. If !deterministic, then it may use a
// randomized strategy that errs with probability no more than
// 2^{-80}.



void NormMod(ZZ& res, const ZZX& a, const ZZX& f, long deterministic=0);
ZZ NormMod(const ZZX& a, const ZZX& f, long deterministic=0);
// res = norm of (a mod f).  f must be monic, 0 < deg(f), deg(a) <
// deg(f). If !deterministic, then it may use a randomized strategy
// that errs with probability no more than 2^{-80}.



void discriminant(ZZ& d, const ZZX& a, long deterministic=0);
ZZ discriminant(const ZZX& a, long deterministic=0);
// d = discriminant of a = (-1)^{m(m-1)/2} resultant(a, a')/lc(a),
// where m = deg(a). If !deterministic, then it may use a randomized
// strategy that errs with probability no more than 2^{-80}.


void CharPolyMod(ZZX& g, const ZZX& a, const ZZX& f, long deterministic=0);
ZZX CharPolyMod(const ZZX& a, const ZZX& f, long deterministic=0);
// g = char poly of (a mod f).  f must be monic.  If !deterministic,
// then it may use a randomized strategy that errs with probability no
// more than 2^{-80}.


void MinPolyMod(ZZX& g, const ZZX& a, const ZZX& f);
ZZX MinPolyMod(const ZZX& a, const ZZX& f);
// g = min poly of (a mod f).  f must be monic, 0 < deg(f), deg(a) <
// deg(f).  May use a probabilistic strategy that errs with
// probability no more than 2^{-80}.




/**************************************************************************\

                  Incremental Chinese Remaindering

\**************************************************************************/

long CRT(ZZX& a, ZZ& prod, const zz_pX& A);
long CRT(ZZX& a, ZZ& prod, const ZZ_pX& A);
// Incremental Chinese Remaindering: If p is the current zz_p/ZZ_p modulus with
// (p, prod) = 1; Computes a' such that a' = a mod prod and a' = A mod p,
// with coefficients in the interval (-p*prod/2, p*prod/2]; 
// Sets a := a', prod := p*prod, and returns 1 if a's value changed.





/**************************************************************************\

                                vectors of ZZX's

\**************************************************************************/

NTL_vector_decl(ZZX,vec_ZZX)
// vec_ZZX

NTL_eq_vector_decl(ZZX,vec_ZZX)
// == and !=

NTL_io_vector_decl(ZZX,vec_ZZX)
// I/O operators


/**************************************************************************\

                                Miscellany


A ZZX f is represented as a vec_ZZ, which can be accessed as
f.rep.  The constant term is f.rep[0] and the leading coefficient is
f.rep[f.rep.length()-1], except if f is zero, in which case
f.rep.length() == 0.  Note that the leading coefficient is always
nonzero (unless f is zero).  One can freely access and modify f.rep,
but one should always ensure that the leading coefficient is nonzero,
which can be done by invoking f.normalize().



\**************************************************************************/


void clear(ZZX& x); // x = 0
void set(ZZX& x); // x = 1

void ZZX::normalize();
// f.normalize() strips leading zeros from f.rep.

void ZZX::SetMaxLength(long n);
// f.SetMaxLength(n) pre-allocate spaces for n coefficients.  The
// polynomial that f represents is unchanged.

void ZZX::kill();
// f.kill() sets f to 0 and frees all memory held by f.  Equivalent to
// f.rep.kill().

ZZX::ZZX(INIT_SIZE_TYPE, long n);
// ZZX(INIT_SIZE, n) initializes to zero, but space is pre-allocated
// for n coefficients

static const ZZX& zero();
// ZZX::zero() is a read-only reference to 0

void swap(ZZX& x, ZZX& y); 
// swap x & y (by swapping pointers)