vec_gf2.txt

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

/**************************************************************************\

MODULE: vec_GF2

SUMMARY:

a vec_GF2 is a vector of GF2s that behaves much like generic NTL vectors
(see vector.txt), but there are some differences.

For efficiency, elements of a vec_GF2 are "packed" into a word.
One may use subscript notation v[i] or v(i) as an r-value
in an expression, and as an l-value in the following contexts:
   * on the left-hand side of an assignment operator,  
   * on the left-hand side of +=, -=, *=, /=, 
   * and as an argument to ++ and --.

One may not use the expression v[i] or v(i) to initialize 
a non-const reference parameter.  

For example, if v, w are vec_GF2's, you can write:

   v[i] = 0;
   v[i] = v[j] + w[k];
   v[i] += 1;
   v[i]++;
   v[i] += w[i];

It is perhaps helpful to describe how this is implemented,
without going into all the details.
The type of a subscript-expression is "subscript_GF2" or
"const_subscript_GF2", the latter chosen if the vector is read-only.
Both of these "helper" types have automatic conversions 
operators to GF2.  Moreover, assignment and increment operators
are defined for "subscript_GF2" (but not for "const_subscript_GF2").
These operators return references to themselves, so one can
iterate assignment operators as usual (as usual in NTL, 
the return type of post-increment/decrement is void).

As an alternative, one can use the get and put methods below to access
vector elements.

There is one subtle but important difference in the semantics
of vec_GF2 and that of generic NTL vectors.  With a vec_GF2, whenever its
length is increased (via SetLength), the "new" bits are always 0.
For example, if v.length() == 20, then 

   v.SetLength(10); v.setLength(20);

will effectively clear bits 10..19 of v.
This is quite different from the semantics of generic NTL vectors, where
the above sequence would not change the value of v at all.
One has to be aware of this difference, but it will not matter
in most ordinary circumstances.


\**************************************************************************/



class vec_GF2 {

public:

   vec_GF2(); // 0 length vector
   vec_GF2(INIT_SIZE_TYPE, long n); // initialize to length n
                                      // usage: vec_GF2(INIT_SIZE, n)

   vec_GF2(const vec_GF2& a); // copy constructor
   vec_GF2& operator=(const vec_GF2& a); // assignment
   ~vec_GF2(); // destructor

   void SetLength(long n); // set length to n bits
   void SetMaxLength(long n); // allocate space for n bits

   long length(); // bit length
   long MaxLength(); // max allocated bit length
   // SIZE INVARIANT: length() <= MaxLength() < 2^(NTL_BITS_PER_LONG-4)

   void FixLength(long n); // fix length to n bits
      // can only be applied after default initialization or kill

   long fixed(); // test if length has been fixed

   void kill(); // free space and make length 0

   GF2 get(long i) const; // fetch value at index i (indexing from 0)

   void put(long i, GF2 a); // write value a to index i (indexing from 0)
   void put(long i, long a); 

   // Here are the subscripting operators, defined using the
   // "helper" classes subscript_GF2 and const_subscript_GF2.

   subscript_GF2 operator[](long i);

   subscript_GF2 operator()(long i);

   const_subscript_GF2 operator[](long i) const;

   const_subscript_GF2 operator()(long i) const;

};


void swap(vec_GF2& x, vec_GF2& y);
// swap x and y (fast pointer swap)

void append(vec_GF2& v, GF2 a);
// append a to v

void append(vec_GF2& v, const vec_GF2& a);
// append a to v

// equality operators:

long operator==(const vec_GF2& a, const vec_GF2& b);
long operator!=(const vec_GF2& a, const vec_GF2& b);


// I/O operators:

ostream& operator<<(ostream& s, const vec_GF2& a);
istream& operator>>(istream& s, vec_GF2& a);

// The I/O format is [a_0 a_1 ... a_{n-1}], where each a_i is "0" or "1".
// On input, the a_i may be arbitrary integers, which are reduced mod 2.

// utility routines:

void clear(vec_GF2& x); // clear all bits--length unchanged
long IsZero(const vec_GF2& a); // test if all bits are zero

void shift(vec_GF2& x, const vec_GF2& a, long n);
vec_GF2 shift(const vec_GF2& a, long n);
// x = a shifted n places, where n may be positive or negative.
// Generally, x[i] = a[i-n], so positive n shifts to a higher index.
// The length of x is set to the length of a, and bits 
// are zero-filled or discarded as necessary.

void reverse(vec_GF2& x, const vec_GF2& a); // c = a reversed
vec_GF2 reverse(const vec_GF2& a);

long weight(const vec_GF2& a); // return number of 1 bits in a

void random(vec_GF2& x, long n);  // x = random vector of length n
vec_GF2 random_vec_GF2(long n);


// arithmetic operations over GF(2):

void add(vec_GF2& x, const vec_GF2& a, const vec_GF2& b);
void sub(vec_GF2& x, const vec_GF2& a, const vec_GF2& b);
void negate(vec_GF2& x, const vec_GF2& a);

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

void mul(vec_GF2& x, GF2 a, const vec_GF2& b);
void mul(vec_GF2& x, long a, const vec_GF2& b);
// x = a * b

void InnerProduct(GF2& x, const vec_GF2& a, const vec_GF2& b);
// vectors may differ in length

void VectorCopy(vec_GF2& x, const vec_GF2& a, long n);
vec_GF2 VectorCopy(const vec_GF2& a, long n);
// x = a copy of a of length exactly n.
// The input is truncated or padded with zeroes, as necessary.



// arithmetic operator notation:

vec_GF2 operator+(const vec_GF2& a, const vec_GF2& b);
vec_GF2 operator-(const vec_GF2& a, const vec_GF2& b);
vec_GF2 operator-(const vec_GF2& a);

// scalar mul:

vec_GF2 operator*(const vec_GF2& a, GF2 b);
vec_GF2 operator*(const vec_GF2& a, long b);

vec_GF2 operator*(GF2 a, const vec_GF2& b); 
vec_GF2 operator*(long a, const vec_GF2& b); 

// inner product: 

inline GF2 operator*(const vec_GF2& a, const vec_GF2& b); 

// assignment operator notation:

vec_GF2& operator+=(vec_GF2& x, const vec_GF2& a);
vec_GF2& operator-=(vec_GF2& x, const vec_GF2& a);

vec_GF2& operator*=(vec_GF2& x, GF2 a);
vec_GF2& operator*=(vec_GF2& x, long a);