gf2x.h

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

#ifndef NTL_GF2X__H
#define NTL_GF2X__H

#include <NTL/vector.h>
#include <NTL/ZZ.h>
#include <NTL/WordVector.h>
#include <NTL/vec_GF2.h>

NTL_OPEN_NNS


class GF2X {
public:

WordVector xrep;

typedef vec_GF2 VectorBaseType;


GF2X() { }
~GF2X() { }

GF2X(INIT_SIZE_TYPE, long n);

GF2X& operator=(const GF2X& a) { xrep = a.xrep; return *this; }

inline GF2X& operator=(GF2 a);
inline GF2X& operator=(long a);

void normalize();

static const GF2X& zero();

void kill() { xrep.kill(); }

void SetMaxLength(long n);

static long HexOutput;

inline GF2X(long i, GF2 c);
inline GF2X(long i, long c);

GF2X(GF2X& x, INIT_TRANS_TYPE) : xrep(x.xrep, INIT_TRANS) { }

};


long IsZero(const GF2X& a);

long IsOne(const GF2X& a); 

long IsX(const GF2X& a);

GF2 coeff(const GF2X& a, long i);

GF2 LeadCoeff(const GF2X& a);

GF2 ConstTerm(const GF2X& a);


inline void clear(GF2X& x) 
{ x.xrep.ZeroLength(); }

void set(GF2X& x);

void SetX(GF2X& x);

void SetCoeff(GF2X& x, long i);

void SetCoeff(GF2X& x, long i, GF2 a);
void SetCoeff(GF2X& x, long i, long a);

inline GF2X::GF2X(long i, GF2 a)
   { SetCoeff(*this, i, a); }

inline GF2X::GF2X(long i, long a)
   { SetCoeff(*this, i, a); }

void swap(GF2X& a, GF2X& b);

long deg(const GF2X& aa);

long weight(const GF2X& a);
   
long operator==(const GF2X& a, const GF2X& b);

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

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

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

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


NTL_SNS istream & operator>>(NTL_SNS istream& s, GF2X& a);

NTL_SNS ostream& operator<<(NTL_SNS ostream& s, const GF2X& a);




void random(GF2X& x, long n);
inline GF2X random_GF2X(long n)
   { GF2X x; random(x, n); NTL_OPT_RETURN(GF2X, x); }




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

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

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

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

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

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

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

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

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


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

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

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

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

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


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

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

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

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

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

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


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

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


void mul(GF2X& c, const GF2X& a, const GF2X& b);

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

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

void MulByX(GF2X& x, const GF2X& a);
inline GF2X MulByX(const GF2X& a) 
   { GF2X x; MulByX(x, a); NTL_OPT_RETURN(GF2X, x); }


void sqr(GF2X& c, const GF2X& a);

inline GF2X sqr(const GF2X& a)
   { GF2X x; sqr(x, a); NTL_OPT_RETURN(GF2X, x); }

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


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

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

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

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

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

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

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

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

void power(GF2X& x, const GF2X& a, long e);  // x = a^e (e >= 0)
inline GF2X power(const GF2X& a, long e)
   { GF2X x; power(x, a, e); NTL_OPT_RETURN(GF2X, x); }



NTL_vector_decl(GF2X,vec_GF2X)

NTL_io_vector_decl(GF2X,vec_GF2X)

NTL_eq_vector_decl(GF2X,vec_GF2X)


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

void ShiftAdd(GF2X& c, const GF2X& a, long n);


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


#ifndef NTL_TRANSITION

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

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

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

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

#endif



void CopyReverse(GF2X& c, const GF2X& a, long hi);
// c[0..hi] = reverse(a[0..hi]), with zero fill as necessary

inline void reverse(GF2X& c, const GF2X& a, long hi)
{  CopyReverse(c, a, hi); }

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

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


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

void InvTrunc(GF2X& c, const GF2X& a, long e);


inline GF2X InvTrunc(const GF2X& a, long e)
   { GF2X x; InvTrunc(x, a, e); NTL_OPT_RETURN(GF2X, x); }


class GF2XModulus {

public:
   GF2XModulus();
   ~GF2XModulus();

   GF2XModulus(const GF2XModulus&);  
   GF2XModulus& operator=(const GF2XModulus&); 

   GF2XModulus(const GF2X& ff);

   GF2X f;   // the modulus

   operator const GF2X& () const { return f; }
   const GF2X& val() const { return f; }

   long n; //  deg(f)
   long sn; //  f.xrep.length()
   long posn; //  n - NTL_BITS_PER_LONG*(sn-1);

   long k3; // used for trinomials and pentanomials
   long k2; 
   long k1;

   long size; // word length of residues

   long WordLength() const { return size; }

   _ntl_ulong msk; // mask of high bits of residues

   long method;