ntl-6.0.0.tar.gz_rsa

/**************************************************************************\ MODULE: zz_pEX SUMMARY: The class zz_pEX represents polynomials over zz_pE, and so can be used, for example, for arithmentic in GF(p^n)[X]. However, except where mathematically necessary (e.g., GCD computations), zz_pE need not be a field. \**************************************************************************/ #include <NTL/lzz_pE.h> #include <NTL/vec_lzz_pE.h> class zz_pEX { public: zz_pEX(); // initial value 0 zz_pEX(const zz_pEX& a); // copy zz_pEX& operator=(const zz_pEX& a); // assignment zz_pEX& operator=(const zz_pE& a); zz_pEX& operator=(const zz_p& a); zz_pEX& operator=(long a); ~zz_pEX(); // destructor zz_pEX(long i, const zz_pE& c); // initilaize to X^i*c zz_pEX(long i, const zz_p& c); zz_pEX(long i, long c); typedef zz_pE coeff_type; // ... }; /**************************************************************************\ Accessing coefficients The degree of a polynomial f is obtained as deg(f), where the zero polynomial, by definition, has degree -1. A polynomial f is represented as a coefficient vector. Coefficients may be accesses in one of two ways. The safe, high-level method is to call the function coeff(f, i) to get the coefficient of X^i in the polynomial f, and to call the function SetCoeff(f, i, a) to set the coefficient of X^i in f to the scalar a. One can also access the coefficients more directly via a lower level interface. The coefficient of X^i in f may be accessed using subscript notation f[i]. In addition, one may write f.SetLength(n) to set the length of the underlying coefficient vector to n, and f.SetMaxLength(n) to allocate space for n coefficients, without changing the coefficient vector itself. After setting coefficients using this low-level interface, one must ensure that leading zeros in the coefficient vector are stripped afterwards by calling the function f.normalize(). NOTE: the coefficient vector of f may also be accessed directly as f.rep; however, this is not recommended. Also, for a properly normalized polynomial f, we have f.rep.length() == deg(f)+1, and deg(f) >= 0 => f.rep[deg(f)] != 0. \**************************************************************************/ long deg(const zz_pEX& a); // return deg(a); deg(0) == -1. const zz_pE& coeff(const zz_pEX& a, long i); // returns the coefficient of X^i, or zero if i not in range const zz_pE& LeadCoeff(const zz_pEX& a); // returns leading term of a, or zero if a == 0 const zz_pE& ConstTerm(const zz_pEX& a); // returns constant term of a, or 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); // makes coefficient of X^i equal to a; error is raised if i < 0 void SetCoeff(zz_pEX& x, long i); // makes coefficient of X^i equal to 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 zz_pE& zz_pEX::operator[](long i); const zz_pE& zz_pEX::operator[](long i) const; // indexing operators: f[i] is the coefficient of X^i --- // i should satsify i >= 0 and i <= deg(f). // No range checking (unless NTL_RANGE_CHECK is defined). void zz_pEX::SetLength(long n); // f.SetLength(n) sets the length of the inderlying coefficient // vector to n --- after this call, indexing f[i] for i = 0..n-1 // is valid. void zz_pEX::normalize(); // f.normalize() strips leading zeros from coefficient vector of f void zz_pEX::SetMaxLength(long n); // f.SetMaxLength(n) pre-allocate spaces for n coefficients. The // polynomial that f represents is unchanged. /**************************************************************************\ Comparison \**************************************************************************/ long operator==(const zz_pEX& a, const zz_pEX& b); long operator!=(const zz_pEX& a, const zz_pEX& b); long IsZero(const zz_pEX& a); // test for 0 long IsOne(const zz_pEX& a); // test for 1 // PROMOTIONS: ==, != promote {long,zz_p,zz_pE} to zz_pEX on (a, b). /**************************************************************************\ Addition \**************************************************************************/ // operator notation: zz_pEX operator+(const zz_pEX& a, const zz_pEX& b); zz_pEX operator-(const zz_pEX& a, const zz_pEX& b); zz_pEX operator-(const zz_pEX& a); zz_pEX& operator+=(zz_pEX& x, const zz_pEX& a); zz_pEX& operator+=(zz_pEX& x, const zz_pE& a); zz_pEX& operator+=(zz_pEX& x, const zz_p& a); zz_pEX& operator+=(zz_pEX& x, long a); zz_pEX& operator++(zz_pEX& x); // prefix void operator++(zz_pEX& x, int); // postfix zz_pEX& operator-=(zz_pEX& x, const zz_pEX& a); zz_pEX& operator-=(zz_pEX& x, const zz_pE& a); zz_pEX& operator-=(zz_pEX& x, const zz_p& a); zz_pEX& operator-=(zz_pEX& x, long a); zz_pEX& operator--(zz_pEX& x); // prefix void operator--(zz_pEX& x, int); // postfix // procedural versions: void add(zz_pEX& x, const zz_pEX& a, const zz_pEX& b); // x = a + b void sub(zz_pEX& x, const zz_pEX& a, const zz_pEX& b); // x = a - b void negate(zz_pEX& x, const zz_pEX& a); // x = - a // PROMOTIONS: +, -, add, sub promote {long,zz_p,zz_pE} to zz_pEX on (a, b). /**************************************************************************\ Multiplication \**************************************************************************/ // operator notation: zz_pEX operator*(const zz_pEX& a, const zz_pEX& b); zz_pEX& operator*=(zz_pEX& x, const zz_pEX& a); zz_pEX& operator*=(zz_pEX& x, const zz_pE& a); zz_pEX& operator*=(zz_pEX& x, const zz_p& a); zz_pEX& operator*=(zz_pEX& x, long a); // procedural versions: 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); // x = a^2 zz_pEX sqr(const zz_pEX& a); // PROMOTIONS: *, mul promote {long,zz_p,zz_pE} to zz_pEX on (a, b). void power(zz_pEX& x, const zz_pEX& a, long e); // x = a^e (e >= 0) zz_pEX power(const zz_pEX& a, long e); /**************************************************************************\ Shift Operations LeftShift by n means multiplication by X^n RightShift by n means division by X^n A negative shift amount reverses the direction of the shift. \**************************************************************************/ // operator notation: zz_pEX operator<<(const zz_pEX& a, long n); zz_pEX operator>>(const zz_pEX& a, long n); zz_pEX& operator<<=(zz_pEX& x, long n); zz_pEX& operator>>=(zz_pEX& x, long n); // procedural versions: void LeftShift(zz_pEX& x, const zz_pEX& a, long n); zz_pEX LeftShift(const zz_pEX& a, long n); void RightShift(zz_pEX& x, const zz_pEX& a, long n); zz_pEX RightShift(const zz_pEX& a, long n); /**************************************************************************\ Division \**************************************************************************/ // operator notation: zz_pEX operator/(const zz_pEX& a, const zz_pEX& b); zz_pEX operator/(const zz_pEX& a, const zz_pE& b); zz_pEX operator/(const zz_pEX& a, const zz_p& b); zz_pEX operator/(const zz_pEX& a, long b); zz_pEX operator%(const zz_pEX& a, const zz_pEX& b); zz_pEX& operator/=(zz_pEX& x, const zz_pEX& a); zz_pEX& operator/=(zz_pEX& x, const zz_pE& a); zz_pEX& operator/=(zz_pEX& x, const zz_p& a); zz_pEX& operator/=(zz_pEX& x, long a); zz_pEX& operator%=(zz_pEX& x, const zz_pEX& a); // procedural versions: 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&