NTL库（VS2015环境下）数论C++函数库

/**************************************************************************\ MODULE: ZZ SUMMARY: The class ZZ is used to represent signed, arbitrary length integers. Routines are provided for all of the basic arithmetic operations, as well as for some more advanced operations such as primality testing. Space is automatically managed by the constructors and destructors. This module also provides routines for generating small primes, and fast routines for performing modular arithmetic on single-precision numbers. \**************************************************************************/ #include <NTL/tools.h> class ZZ { public: ZZ(); // initial value is 0 ZZ(const ZZ& a); // copy constructor explicit ZZ(long a); // promotion constructor ~ZZ(); // destructor ZZ& operator=(const ZZ& a); // assignment operator ZZ& operator=(long a); // typedefs to aid in generic programming typedef ZZ_p residue_type; typedef ZZX poly_type; // ... }; // NOTE: A ZZ is represented as a sequence of "zzigits", // where each zzigit is between 0 and 2^{NTL_ZZ_NBITS-1}. // NTL_ZZ_NBITS is macros defined in <NTL/ZZ.h>. // SIZE INVARIANT: the number of bits in a ZZ is always less than // 2^(NTL_BITS_PER_LONG-4). /**************************************************************************\ Comparison \**************************************************************************/ // The usual comparison operators: long operator==(const ZZ& a, const ZZ& b); long operator!=(const ZZ& a, const ZZ& b); long operator<(const ZZ& a, const ZZ& b); long operator>(const ZZ& a, const ZZ& b); long operator<=(const ZZ& a, const ZZ& b); long operator>=(const ZZ& a, const ZZ& b); // other stuff: long sign(const ZZ& a); // returns sign of a (-1, 0, +1) long IsZero(const ZZ& a); // test for 0 long IsOne(const ZZ& a); // test for 1 long compare(const ZZ& a, const ZZ& b); // returns sign of a-b (-1, 0, or 1). // PROMOTIONS: the comparison operators and the function compare // support promotion from long to ZZ on (a, b). /**************************************************************************\ Addition \**************************************************************************/ // operator notation: ZZ operator+(const ZZ& a, const ZZ& b); ZZ operator-(const ZZ& a, const ZZ& b); ZZ operator-(const ZZ& a); // unary - ZZ& operator+=(ZZ& x, const ZZ& a); ZZ& operator+=(ZZ& x, long a); ZZ& operator-=(ZZ& x, const ZZ& a); ZZ& operator-=(ZZ& x, long a); ZZ& operator++(ZZ& x); // prefix void operator++(ZZ& x, int); // postfix ZZ& operator--(ZZ& x); // prefix void operator--(ZZ& x, int); // postfix // procedural versions: void add(ZZ& x, const ZZ& a, const ZZ& b); // x = a + b void sub(ZZ& x, const ZZ& a, const ZZ& b); // x = a - b void SubPos(ZZ& x, const ZZ& a, const ZZ& b); // x = a-b; assumes a >= b >= 0. void negate(ZZ& x, const ZZ& a); // x = -a void abs(ZZ& x, const ZZ& a); // x = |a| ZZ abs(const ZZ& a); // PROMOTIONS: binary +, -, as well as the procedural versions add, sub // support promotions from long to ZZ on (a, b). /**************************************************************************\ Multiplication \**************************************************************************/ // operator notation: ZZ operator*(const ZZ& a, const ZZ& b); ZZ& operator*=(ZZ& x, const ZZ& a); ZZ& operator*=(ZZ& x, long a); // procedural versions: void mul(ZZ& x, const ZZ& a, const ZZ& b); // x = a * b void sqr(ZZ& x, const ZZ& a); // x = a*a ZZ sqr(const ZZ& a); // PROMOTIONS: operator * and procedure mul support promotion // from long to ZZ on (a, b). /**************************************************************************\ Combined Multiply and Add \**************************************************************************/ void MulAddTo(ZZ& x, const ZZ& a, const ZZ& b); // x += a*b void MulAddTo(ZZ& x, const ZZ& a, long b); // x += a*b void MulSubFrom(ZZ& x, const ZZ& a, const ZZ& b); // x -= a*b void MulSubFrom(ZZ& x, const ZZ& a, long b); // x -= a*b // NOTE: these are provided for both convenience and efficiency. // The single-precision versions may be significantly // faster than the code sequence // mul(tmp, a, b); add(x, x, tmp); /**************************************************************************\ Division \**************************************************************************/ // operator notation: ZZ operator/(const ZZ& a, const ZZ& b); ZZ operator/(const ZZ& a, long b); ZZ operator%(const ZZ& a, const ZZ& b); long operator%(const ZZ& a, long b); ZZ& operator/=(ZZ& x, const ZZ& b); ZZ& operator/=(ZZ& x, long b); ZZ& operator%=(ZZ& x, const ZZ& b); // procedural versions: void DivRem(ZZ& q, ZZ& r, const ZZ& a, const ZZ& b); // q = floor(a/b), r = a - b*q. // This implies that: // |r| < |b|, and if r != 0, sign(r) = sign(b) void div(ZZ& q, const ZZ& a, const ZZ& b); // q = floor(a/b) void rem(ZZ& r, const ZZ& a, const ZZ& b); // q = floor(a/b), r = a - b*q // single-precision variants: long DivRem(ZZ& q, const ZZ& a, long b); // q = floor(a/b), r = a - b*q, return value is r. long rem(const ZZ& a, long b); // q = floor(a/b), r = a - b*q, return value is r. // divisibility testing: long divide(ZZ& q, const ZZ& a, const ZZ& b); 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, const ZZ& b); long divide(const ZZ& a, long b); // if b | a, returns 1; otherwise returns 0. /**************************************************************************\ GCD's \**************************************************************************/ void GCD(ZZ& d, const ZZ& a, const ZZ& b); ZZ GCD(const ZZ& a, const ZZ& b); // d = gcd(a, b) (which is always non-negative). Uses a binary GCD // algorithm. void XGCD(ZZ& d, ZZ& s, ZZ& t, const ZZ& a, const ZZ& b); // d = gcd(a, b) = a*s + b*t. // The coefficients s and t are defined according to the standard // Euclidean algorithm applied to |a| and |b|, with the signs then // adjusted according to the signs of a and b. // The implementation may or may not Euclid's algorithm, // but the coefficients a and t are always computed as if // it did. // special-purpose single-precision variants: long GCD(long a, long b); // return value is gcd(a, b) (which is always non-negative) void XGCD(long& d, long& s, long& t, long a, long b); // d = gcd(a, b) = a*s + b*t. // The coefficients s and t are defined according to the standard // Euclidean algorithm applied to |a| and |b|, with the signs then // adjusted according to the signs of a and b. /**************************************************************************\ Modular Arithmetic The following routines perform arithmetic mod n, where n > 1. All arguments (other than exponents) are assumed to be in the range 0..n-1. Some routines may check this and raise an error if this does not hold. Others may not, and the behaviour is unpredictable in this case. \**************************************************************************/ void AddMod(ZZ& x, const ZZ& a, const ZZ& b, const ZZ& n); // x = (a+b)%n ZZ AddMod(const ZZ& a, const ZZ& b, const ZZ& n); void SubMod(ZZ& x, const ZZ& a, const ZZ& b, const ZZ& n); // x = (a-b)%n ZZ SubMod(const ZZ& a, const ZZ& b, const ZZ& n); void NegateMod(ZZ& x, const ZZ& a, const ZZ& n); // x = -a % n ZZ NegateMod(