gf2x.h

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

   vec_GF2X stab;
   _ntl_ulong **stab_ptr;
   long *stab_cnt;

   _ntl_ulong *stab1;

   GF2X h0, f0;

   vec_GF2 tracevec;

}; 


inline long deg(const GF2XModulus& F) { return F.n; }


void build(GF2XModulus& F, const GF2X& f);

void rem(GF2X& r, const GF2X& a, const GF2XModulus& F);
   
void DivRem(GF2X& q, GF2X& r, const GF2X& a, const GF2XModulus& F);

void div(GF2X& q, const GF2X& a, const GF2XModulus& F);

void PlainDivRem(GF2X& q, GF2X& r, const GF2X& a, const GF2X& b);
void PlainDiv(GF2X& q, const GF2X& a, const GF2X& b);
void PlainRem(GF2X& r, const GF2X& a, const GF2X& b);


void MulMod(GF2X& c, const GF2X& a, const GF2X& b, const GF2XModulus& F);
inline GF2X MulMod(const GF2X& a, const GF2X& b, const GF2XModulus& F)
   { GF2X x; MulMod(x, a, b, F); NTL_OPT_RETURN(GF2X, x); }

void SqrMod(GF2X& c, const GF2X& a, const GF2XModulus& F);
inline GF2X SqrMod(const GF2X& a, const GF2XModulus& F)
   { GF2X x; SqrMod(x, a, F); NTL_OPT_RETURN(GF2X, x); }

void MulByXMod(GF2X& c, const GF2X& a, const GF2XModulus& F);
inline GF2X MulByXMod(const GF2X& a, const GF2XModulus& F)
   { GF2X x; MulByXMod(x, a, F); NTL_OPT_RETURN(GF2X, x); }



void MulMod(GF2X& c, const GF2X& a, const GF2X& b, const GF2X& f);
inline GF2X MulMod(const GF2X& a, const GF2X& b, const GF2X& f)
   { GF2X x; MulMod(x, a, b, f); NTL_OPT_RETURN(GF2X, x); } 

void SqrMod(GF2X& c, const GF2X& a, const GF2X& f);
inline GF2X SqrMod(const GF2X& a, const GF2X& f)
   { GF2X x; SqrMod(x, a, f); NTL_OPT_RETURN(GF2X, x); } 

void MulByXMod(GF2X& c, const GF2X& a, const GF2X& f);
inline GF2X MulByXMod(const GF2X& a, const GF2X& f)
   { GF2X x; MulByXMod(x, a, f); NTL_OPT_RETURN(GF2X, x); } 


void InvMod(GF2X& c, const GF2X& a, const GF2X& f);
inline GF2X InvMod(const GF2X& a, const GF2X& f)
   { GF2X x; InvMod(x, a, f); NTL_OPT_RETURN(GF2X, x); } 

long InvModStatus(GF2X& c, const GF2X& a, const GF2X& f);

inline long InvModStatus(GF2X& c, const GF2X& a, const GF2XModulus& F)
   { return InvModStatus(c, a, F.f); }


void PowerMod(GF2X& h, const GF2X& g, const ZZ& e, const GF2XModulus& F);
inline void PowerMod(GF2X& x, const GF2X& g, long e, const GF2XModulus& F)
   { PowerMod(x, g, ZZ_expo(e), F); } 

void PowerXMod(GF2X& hh, const ZZ& e, const GF2XModulus& F);
inline void PowerXMod(GF2X& x, long e, const GF2XModulus& F)
   { PowerXMod(x, ZZ_expo(e), F); } 

inline GF2X PowerMod(const GF2X& g, const ZZ& e, const GF2XModulus& F)
   { GF2X x; PowerMod(x, g, e, F); NTL_OPT_RETURN(GF2X, x); }

inline GF2X PowerMod(const GF2X& g, long e, const GF2XModulus& F)
   { GF2X x; PowerMod(x, g, e, F); NTL_OPT_RETURN(GF2X, x); }

inline GF2X PowerXMod(const ZZ& e, const GF2XModulus& F)
   { GF2X x; PowerXMod(x, e, F); NTL_OPT_RETURN(GF2X, x); }

inline GF2X PowerXMod(long e, const GF2XModulus& F)
   { GF2X x; PowerXMod(x, e, F); NTL_OPT_RETURN(GF2X, x); }



inline GF2X operator%(const GF2X& a, const GF2XModulus& F)
   { GF2X x; rem(x, a, F); NTL_OPT_RETURN(GF2X, x); }

inline GF2X& operator%=(GF2X& x, const GF2XModulus& F)
   { rem(x, x, F); return x; }


inline GF2X operator/(const GF2X& a, const GF2XModulus& F)
   { GF2X x; div(x, a, F); NTL_OPT_RETURN(GF2X, x); }

inline GF2X& operator/=(GF2X& x, const GF2XModulus& F)
   { div(x, x, F); return x; }



void DivRem(GF2X& q, GF2X& r, const GF2X& a, const GF2X& b);

void div(GF2X& q, const GF2X& a, const GF2X& b);

void div(GF2X& q, const GF2X& a, GF2 b);
void div(GF2X& q, const GF2X& a, long b);

void rem(GF2X& r, const GF2X& a, const GF2X& b);




inline GF2X operator/(const GF2X& a, const GF2X& b)
   { GF2X x; div(x, a, b); NTL_OPT_RETURN(GF2X, x); }

inline GF2X operator/(const GF2X& a, GF2 b)
   { GF2X x; div(x, a, b); NTL_OPT_RETURN(GF2X, x); }

inline GF2X operator/(const GF2X& a, long b)
   { GF2X x; div(x, a, b); NTL_OPT_RETURN(GF2X, x); }

inline GF2X& operator/=(GF2X& x, GF2 b)
   { div(x, x, b); return x; }

inline GF2X& operator/=(GF2X& x, long b)
   { div(x, x, b); return x; }

inline GF2X& operator/=(GF2X& x, const GF2X& b)
   { div(x, x, b); return x; }


inline GF2X operator%(const GF2X& a, const GF2X& b)
   { GF2X x; rem(x, a, b); NTL_OPT_RETURN(GF2X, x); }

inline GF2X& operator%=(GF2X& x, const GF2X& b)
   { rem(x, x, b); return x; }


void GCD(GF2X& d, const GF2X& a, const GF2X& b);
inline GF2X GCD(const GF2X& a, const GF2X& b)
   { GF2X x; GCD(x, a, b); NTL_OPT_RETURN(GF2X, x); }

void XGCD(GF2X& d, GF2X& s, GF2X& t, const GF2X& a, const GF2X& b);
   
void diff(GF2X& c, const GF2X& a);
inline GF2X diff(const GF2X& a)
   { GF2X x; diff(x, a); NTL_OPT_RETURN(GF2X, x); }

void conv(GF2X& c, long a);
void conv(GF2X& c, GF2 a);
void conv(GF2X& x, const vec_GF2& a);
inline void conv(GF2X& x, const ZZ& a)
   { conv(x, to_GF2(a)); }

void conv(vec_GF2& x, const GF2X& a);

inline GF2X to_GF2X(long a)
   { GF2X x; conv(x, a); NTL_OPT_RETURN(GF2X, x); }

inline GF2X to_GF2X(GF2 a)
   { GF2X x; conv(x, a); NTL_OPT_RETURN(GF2X, x); }

inline GF2X to_GF2X(const vec_GF2& a)
   { GF2X x; conv(x, a); NTL_OPT_RETURN(GF2X, x); }

inline GF2X to_GF2X(const ZZ& a)
   { GF2X x; conv(x, a); NTL_OPT_RETURN(GF2X, x); }

inline vec_GF2 to_vec_GF2(const GF2X& a)
   { vec_GF2 x; conv(x, a); NTL_OPT_RETURN(vec_GF2, x); }

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

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

void VectorCopy(vec_GF2& x, const GF2X& a, long n);

inline vec_GF2 VectorCopy(const GF2X& a, long n)
   { vec_GF2 x; VectorCopy(x, a, n); NTL_OPT_RETURN(vec_GF2, x);  }


void MulTrunc(GF2X& c, const GF2X& a, const GF2X& b, long n);
inline GF2X MulTrunc(const GF2X& a, const GF2X& b, long n)
   { GF2X x; MulTrunc(x, a, b, n); NTL_OPT_RETURN(GF2X, x); }

void SqrTrunc(GF2X& c, const GF2X& a, long n);
inline GF2X SqrTrunc(const GF2X& a, long n)
   { GF2X x; SqrTrunc(x, a, n); NTL_OPT_RETURN(GF2X, x); }

long divide(GF2X& q, const GF2X& a, const GF2X& b);

long divide(const GF2X& a, const GF2X& b);


/*** modular composition routines and data structures ***/

struct GF2XArgument {
   vec_GF2X H;
};


void CompMod(GF2X& x, const GF2X& g, 
             const GF2XArgument& A, const GF2XModulus& F);

inline GF2X CompMod(const GF2X& g, 
             const GF2XArgument& A, const GF2XModulus& F)
   { GF2X x; CompMod(x, g, A, F); NTL_OPT_RETURN(GF2X, x); }

void build(GF2XArgument& A, const GF2X& h, const GF2XModulus& F, long m);

void CompMod(GF2X& x, const GF2X& g, const GF2X& h, const GF2XModulus& F);
inline GF2X CompMod(const GF2X& g, const GF2X& h, const GF2XModulus& F)
   { GF2X x; CompMod(x, g, h, F); NTL_OPT_RETURN(GF2X, x); }

void Comp2Mod(GF2X& x1, GF2X& x2, const GF2X& g1, const GF2X& g2,
              const GF2X& h, const GF2XModulus& F);

void Comp3Mod(GF2X& x1, GF2X& x2, GF2X& x3, 
              const GF2X& g1, const GF2X& g2, const GF2X& g3,
              const GF2X& h, const GF2XModulus& F);


void MinPolySeq(GF2X& h, const vec_GF2& a, long m);
inline GF2X MinPolySeq(const vec_GF2& a, long m)
   { GF2X x; MinPolySeq(x, a, m); NTL_OPT_RETURN(GF2X, x); }

void ProbMinPolyMod(GF2X& hh, const GF2X& g, const GF2XModulus& F);
inline GF2X ProbMinPolyMod(const GF2X& g, const GF2XModulus& F)
   { GF2X x; ProbMinPolyMod(x, g, F); NTL_OPT_RETURN(GF2X, x); }

void ProbMinPolyMod(GF2X& hh, const GF2X& g, const GF2XModulus& F, long m);
inline GF2X ProbMinPolyMod(const GF2X& g, const GF2XModulus& F, long m)
   { GF2X x; ProbMinPolyMod(x, g, F, m); NTL_OPT_RETURN(GF2X, x); }

void MinPolyMod(GF2X& hh, const GF2X& g, const GF2XModulus& F);
inline GF2X MinPolyMod(const GF2X& g, const GF2XModulus& F)
   { GF2X x; MinPolyMod(x, g, F); NTL_OPT_RETURN(GF2X, x); }

void MinPolyMod(GF2X& hh, const GF2X& g, const GF2XModulus& F, long m);
inline GF2X MinPolyMod(const GF2X& g, const GF2XModulus& F, long m)
   { GF2X x; MinPolyMod(x, g, F, m); NTL_OPT_RETURN(GF2X, x); }

void IrredPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F);
inline GF2X IrredPolyMod(const GF2X& g, const GF2XModulus& F)
   { GF2X x; IrredPolyMod(x, g, F); NTL_OPT_RETURN(GF2X, x); }

void IrredPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F, long m);
inline GF2X IrredPolyMod(const GF2X& g, const GF2XModulus& F, long m)
   { GF2X x; IrredPolyMod(x, g, F, m); NTL_OPT_RETURN(GF2X, x); }


// undocumented stuff:

void MinPolyInternal(GF2X& h, const GF2X& x, long m);


struct GF2XTransMultiplier {
   GF2X f0, fbi, b;
   long shamt, shamt_fbi, shamt_b;
};

void build(GF2XTransMultiplier& B, const GF2X& b, const GF2XModulus& F);

void UpdateMap(vec_GF2& x, const vec_GF2& a, const GF2XTransMultiplier& B,
               const GF2XModulus& F);

inline vec_GF2 UpdateMap(const vec_GF2& a, 
                       const GF2XTransMultiplier& B, const GF2XModulus& F)
   { vec_GF2 x; UpdateMap(x, a, B, F); NTL_OPT_RETURN(vec_GF2, x); }

inline void project(GF2& x, const vec_GF2& a, const GF2X& b)
   { x = to_GF2(InnerProduct(a.rep, b.xrep)); }

inline GF2 project(const vec_GF2& a, const GF2X& b)
   { return to_GF2(InnerProduct(a.rep, b.xrep)); }


void ProjectPowers(vec_GF2& x, const vec_GF2& a, long k, 
                   const GF2XArgument& H, const GF2XModulus& F);

inline vec_GF2 ProjectPowers(const vec_GF2& a, long k, 
                          const GF2XArgument& H, const GF2XModulus& F)
   { vec_GF2 x; ProjectPowers(x, a, k, H, F); 
     NTL_OPT_RETURN(vec_GF2, x); }

void ProjectPowers(vec_GF2& x, const vec_GF2& a, long k, const GF2X& h, 
                   const GF2XModulus& F);

inline vec_GF2 ProjectPowers(const vec_GF2& a, long k, 
                          const GF2X& H, const GF2XModulus& F)
   { vec_GF2 x; ProjectPowers(x, a, k, H, F); 
     NTL_OPT_RETURN(vec_GF2, x); }

void TraceVec(vec_GF2& S, const GF2X& f);

inline vec_GF2 TraceVec(const GF2X& f)
   { vec_GF2 x; TraceVec(x, f); NTL_OPT_RETURN(vec_GF2, x); }


void TraceMod(GF2& x, const GF2X& a, const GF2XModulus& F);

inline GF2 TraceMod(const GF2X& a, const GF2XModulus& F)
   { GF2 x; TraceMod(x, a, F); return x; }

void TraceMod(GF2& x, const GF2X& a, const GF2X& f);

inline GF2 TraceMod(const GF2X& a, const GF2X& f)
   { GF2 x; TraceMod(x, a, f); return x; }



void GF2XFromBytes(GF2X& x, const unsigned char *p, long n);
inline GF2X GF2XFromBytes(const unsigned char *p, long n)
   { GF2X x; GF2XFromBytes(x, p, n); NTL_OPT_RETURN(GF2X, x); }

void BytesFromGF2X(unsigned char *p, const GF2X& a, long n);

inline long NumBits(const GF2X& a)
   { return deg(a) + 1; }

inline long NumBytes(const GF2X& a)
   { return (NumBits(a) + 7)/8; }


NTL_CLOSE_NNS

#endif