gf2ex.h

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

#ifndef NTL_GF2EX__H
#define NTL_GF2EX__H

#include <NTL/vector.h>
#include <NTL/GF2E.h>
#include <NTL/vec_GF2E.h>
#include <NTL/FFT.h>
#include <NTL/GF2XVec.h>


NTL_OPEN_NNS


class GF2EX {

public:

vec_GF2E rep;


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

          Constructors, Destructors, and Assignment

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


GF2EX() { }


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

GF2EX(const GF2EX& a) : rep(a.rep) { }


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

~GF2EX() { }

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



inline GF2EX& operator=(long a);
inline GF2EX& operator=(GF2 a);
inline GF2EX& operator=(const GF2E& a);

inline GF2EX(long i, long a);
inline GF2EX(long i, GF2 a);
inline GF2EX(long i, const GF2E& a);

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


};




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

                           input and output

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


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




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

                   Some utility routines

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


inline long deg(const GF2EX& a) { return a.rep.length() - 1; }

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

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

const GF2E& LeadCoeff(const GF2EX& a);
// zero if a == 0

const GF2E& ConstTerm(const GF2EX& a);
// zero if a == 0

void SetCoeff(GF2EX& x, long i, const GF2E& a);
void SetCoeff(GF2EX& x, long i, GF2 a);
void SetCoeff(GF2EX& x, long i, long a);
// x[i] = a, error is raised if i < 0

inline GF2EX::GF2EX(long i, const GF2E& a) { SetCoeff(*this, i, a); }
inline GF2EX::GF2EX(long i, GF2 a) { SetCoeff(*this, i, a); }
inline GF2EX::GF2EX(long i, long a) { SetCoeff(*this, i, a); }

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

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

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

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

   { x.rep.SetLength(0); }

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

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

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

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

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

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

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

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

#ifndef NTL_TRANSITION

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

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

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

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

#endif



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



void MakeMonic(GF2EX& x);

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

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

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

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

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

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




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

                        conversion routines

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



void conv(GF2EX& x, long a);
void conv(GF2EX& x, GF2 a);
void conv(GF2EX& x, const GF2E& a);
void conv(GF2EX& x, const ZZ& a);

#ifndef NTL_TRANSITION
void conv(GF2EX& x, const GF2X& a);
#endif

void conv(GF2EX& x, const vec_GF2E& a);

inline GF2EX to_GF2EX(long a)
   { GF2EX x; conv(x, a); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX to_GF2EX(GF2 a)
   { GF2EX x; conv(x, a); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX to_GF2EX(const GF2E& a)
   { GF2EX x; conv(x, a); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX to_GF2EX(const ZZ& a)
   { GF2EX x; conv(x, a); NTL_OPT_RETURN(GF2EX, x); }

#ifndef NTL_TRANSITION
inline GF2EX to_GF2EX(GF2X& a)
   { GF2EX x; conv(x, a); NTL_OPT_RETURN(GF2EX, x); }
#endif

inline GF2EX to_GF2EX(const vec_GF2E& a)
   { GF2EX x; conv(x, a); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX& GF2EX::operator=(const GF2E& a) { conv(*this, a); return *this; }
inline GF2EX& GF2EX::operator=(GF2 a) { conv(*this, a); return *this; }
inline GF2EX& GF2EX::operator=(long a) { conv(*this, a); return *this; }




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

                        Comparison

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

long IsZero(const GF2EX& a); 

long IsOne(const GF2EX& a);

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

long operator==(const GF2EX& a, const GF2E& b);
long operator==(const GF2EX& a, GF2 b);
long operator==(const GF2EX& a, long b);

inline long operator==(const GF2E& a, const GF2EX& b) { return b == a; }
inline long operator==(GF2 a, const GF2EX& b) { return b == a; }
inline long operator==(long a, const GF2EX& b) { return b == a; }

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

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

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


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

                         Addition

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

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

void add(GF2EX& x, const GF2EX& a, const GF2E& b);
void add(GF2EX& x, const GF2EX& a, GF2 b);
void add(GF2EX& x, const GF2EX& a, long);

inline void add(GF2EX& x, const GF2E& a, const GF2EX& b) { add(x, b, a); }
inline void add(GF2EX& x, GF2 a, const GF2EX& b) { add(x, b, a); }
inline void add(GF2EX& x, long a, const GF2EX& b) { add(x, b, a); }

inline void sub(GF2EX& x, const GF2EX& a, const GF2EX& b) { add(x, a, b); }

inline void sub(GF2EX& x, const GF2EX& a, const GF2E& b) { add(x, a, b); }
inline void sub(GF2EX& x, const GF2EX& a, GF2 b) { add(x, a, b); }
inline void sub(GF2EX& x, const GF2EX& a, long b) { add(x, a, b); }

inline void sub(GF2EX& x, const GF2E& a, const GF2EX& b) { add(x, a, b); }
inline void sub(GF2EX& x, GF2 a, const GF2EX& b) { add(x, a, b); }
inline void sub(GF2EX& x, long a, const GF2EX& b) { add(x, a, b); }

inline void negate(GF2EX& x, const GF2EX& a) { x = a; }




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

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

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

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

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

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

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


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

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

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

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

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

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

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


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

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

inline GF2EX& operator+=(GF2EX& x, GF2 b)
   { add(x, x, b); return x; }

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

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

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

inline GF2EX& operator-=(GF2EX& x, GF2 b)
   { sub(x, x, b); return x; }

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


inline GF2EX operator-(const GF2EX& a) 
   { GF2EX x; negate(x, a); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX& operator++(GF2EX& x) { add(x, x, 1); return x; }
inline void operator++(GF2EX& x, int) { add(x, x, 1); }
inline GF2EX& operator--(GF2EX& x) { sub(x, x, 1); return x; }
inline void operator--(GF2EX& x, int) { sub(x, x, 1); }


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

                        Multiplication

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


void mul(GF2EX& x, const GF2EX& a, const GF2EX& b);
// x = a * b

void sqr(GF2EX& x, const GF2EX& a);
inline GF2EX sqr(const GF2EX& a)
   { GF2EX x; sqr(x, a); NTL_OPT_RETURN(GF2EX, x); }
// x = a^2

void mul(GF2EX & x, const GF2EX& a, const GF2E& b);
void mul(GF2EX & x, const GF2EX& a, GF2 b);
void mul(GF2EX & x, const GF2EX& a, long b);

inline void mul(GF2EX& x, const GF2E& a, const GF2EX& b) { mul(x, b, a); }
inline void mul(GF2EX& x, GF2 a, const GF2EX& b) { mul(x, b, a); }
inline void mul(GF2EX& x, long a, const GF2EX& b) { mul(x, b, a); }

void MulTrunc(GF2EX& x, const GF2EX& a, const GF2EX& b, long n);
inline GF2EX MulTrunc(const GF2EX& a, const GF2EX& b, long n)
   { GF2EX x; MulTrunc(x, a, b, n); NTL_OPT_RETURN(GF2EX, x); }
// x = a * b % X^n

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


inline GF2EX operator*(const GF2EX& a, const GF2EX& b)
   { GF2EX x; mul(x, a, b); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX operator*(const GF2EX& a, const GF2E& b)
   { GF2EX x; mul(x, a, b); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX operator*(const GF2EX& a, GF2 b)
   { GF2EX x; mul(x, a, b); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX operator*(const GF2EX& a, long b)
   { GF2EX x; mul(x, a, b); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX operator*(const GF2E& a, const GF2EX& b)
   { GF2EX x; mul(x, a, b); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX operator*(GF2 a, const GF2EX& b)
   { GF2EX x; mul(x, a, b); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX operator*(long a, const GF2EX& b)
   { GF2EX x; mul(x, a, b); NTL_OPT_RETURN(GF2EX, x); }

inline GF2EX& operator*=(GF2EX& x, const GF2EX& b)
   { mul(x, x, b); return x; }

inline GF2EX& operator*=(GF2EX& x, const GF2E& b)
   { mul(x, x, b); return x; }

inline GF2EX& operator*=(GF2EX& x, GF2 b)
   { mul(x, x, b); return x; }

inline GF2EX& operator*=(GF2EX& x, long b)
   { mul(x, x, b); return x; }


void power(GF2EX& x, const GF2EX& a, long e);
inline GF2EX power(const GF2EX& a, long e)
   { GF2EX x; power(x, a, e); NTL_OPT_RETURN(GF2EX, x); }




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

                      Division

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

void DivRem(GF2EX& q, GF2EX& r, const GF2EX& a, const GF2EX& b);
// q = a/b, r = a%b

void div(GF2EX& q, const GF2EX& a, const GF2EX& b);
void div(GF2EX& q, const GF2EX& a, const GF2E& b);
void div(GF2EX& q, const GF2EX& a, GF2 b);
void div(GF2EX& q, const GF2EX& a, long b);
// q = a/b

void rem(GF2EX& r, const GF2EX& a, const GF2EX& b);
// r = a%b

long divide(GF2EX& q, const GF2EX& a, const GF2EX& b);
// if b | a, sets q = a/b and returns 1; otherwise returns 0

long divide(const GF2EX& a, const GF2EX& b);
// if b | a, sets q = a/b and returns 1; otherwise returns 0

void InvTrunc(GF2EX& x, const GF2EX& a, long m);
inline GF2EX InvTrunc(const GF2EX& a, long m)
   { GF2EX x; InvTrunc(x, a, m); NTL_OPT_RETURN(GF2EX, x); }

// computes x = a^{-1} % X^m