source: git/ntl/doc/GF2E.txt @ 199b5c

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

MODULE: GF2E

SUMMARY:

The class GF2E is used to represent polynomials in F_2[X] modulo a
polynomial P.  The modulus P may be any polynomial with deg(P) > 0,
not necessarily irreducible.  

Objects of the class GF2E are represented as a GF2X of degree < deg(P).

An executing program maintains a "current modulus", which is set to P
using GF2E::init(P).  The current modulus *must* be initialized before
any GF2E constructors are invoked.

The modulus may be changed, and a mechanism is provided for saving and
restoring a modulus (see classes GF2EBak and GF2EContext below).


NOTE: if P is a trinomial X^n + X^k + 1, or a pentanomial
X^n + X^k3 + X^k2 + X^k1 + 1, or of the form X^n + g, where
g has low degree, then performance will be somewhat improved.
Such polynomials are constructed by the routines
BuildSparseIrred and BuildIrred in GF2XFactoring.


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

#include <NTL/GF2X.h>

class GF2E {
public:
   
   GF2E(); // initial value 0

   GF2E(const GF2E& a); // copy constructor
   
   GF2E& operator=(const GF2E& a); // assignment
   GF2E& operator=(GF2 a); // assignment
   GF2E& operator=(long a); // assignment
   
   ~GF2E(); // destructor

   void init(const GF2X& P);
   // GF2E::init(P) initializes the current modulus to P;
   // required: deg(P) >= 1.
   
   static const GF2XModulus& modulus();
   // GF2E::modulus() yields read-only reference to the current modulus 

   static long degree();
   // GF2E::degree() returns deg(P)
};


const GF2X& rep(const GF2E& a); // read-only access to representation of a



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

                                  Comparison

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

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

long IsZero(const GF2E& a);  // test for 0
long IsOne(const GF2E& a);  // test for 1

// PROMOTIONS: ==, != promote {long, GF2} to GF2E on (a, b).


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

                                    Addition 

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

// operator notation:

GF2E operator+(const GF2E& a, const GF2E& b);

GF2E operator-(const GF2E& a, const GF2E& b);
GF2E operator-(const GF2E& a);

GF2E& operator+=(GF2E& x, const GF2E& a);
GF2E& operator+=(GF2E& x, GF2 a);
GF2E& operator+=(GF2E& x, long a);

GF2E& operator++(GF2E& x); // prefix
void operator++(GF2E& x, int); // postfix

GF2E& operator-=(GF2E& x, const GF2E& a);
GF2E& operator-=(GF2E& x, GF2 a);
GF2E& operator-=(GF2E& x, long a);

GF2E& operator--(GF2E& x); // prefix
void operator--(GF2E& x, int); // postfix

// procedural versions:

void add(GF2E& x, const GF2E& a, const GF2E& b); // x = a + b
void sub(GF2E& x, const GF2E& a, const GF2E& b); // x = a - b = a + b
void negate(GF2E& x, const GF2E& a); // x = - a = a

// PROMOTIONS: +, -, add, sub promote {long, GF2} to GF2E on (a, b).


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

                                  Multiplication 

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


// operator notation:

GF2E operator*(const GF2E& a, const GF2E& b);

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

// procedural versions:


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

void sqr(GF2E& x, const GF2E& a); // x = a^2
GF2E sqr(const GF2E& a); 

// PROMOTIONS: *, mul promote {long, GF2} to GF2E on (a, b).


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

                                     Division

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


// operator notation:

GF2E operator/(const GF2E& a, const GF2E& b);

GF2E& operator/=(GF2E& x, const GF2E& a);
GF2E& operator/=(GF2E& x, GF2 a);
GF2E& operator/=(GF2E& x, long a);


// procedural versions:

void div(GF2E& x, const GF2E& a, const GF2E& b);
// x = a/b.  If b is not invertible, an error is raised.

void inv(GF2E& x, const GF2E& a);
GF2E inv(const GF2E& a);
// x = 1/a

PROMOTIONS: /, div promote {long, GF2} to GF2E on (a, b).


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

                                  Exponentiation

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



void power(GF2E& x, const GF2E& a, const ZZ& e); 
GF2E power(const GF2E& a, const ZZ& e);

void power(GF2E& x, const GF2E& a, long e); 
GF2E power(const GF2E& a, long e);

// x = a^e (e may be negative)



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

                               Random Elements

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


void random(GF2E& x);
GF2E random_GF2E();
// x = random element in GF2E.

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

                                  Traces

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


void trace(GF2& x, const GF2E& a);  // x = trace of a
GF2 trace(const GF2E& a);



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

                                Input/Output

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


ostream& operator<<(ostream& s, const GF2E& a);

istream& operator>>(istream& s, GF2E& x);
// a GF2X is read and reduced mod p


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

                       Modulus Switching 

A class GF2EBak is provided for "backing up" the current modulus.

Here is what you do to save the current modulus, temporarily
set it to something new, and then restore it:

   GF2EBak bak;
   bak.save();   // save current modulus (if any)

   GF2E::init(P);  // set modulus to desired value P

      // ...

   bak.restore(); // restore old modulus (if any)

Note that between the save and restore, you may have several calls to
GF2E::init, each of which simply clobbers the previous modulus.

The GF2EBak interface is good for implementing simple stack-like
modulus "context switching".  For more general context switching,
see GF2EContext below.

..........................................................................

When the current modulus is changed, there may be extant
GF2E objects. If the old modulus was saved and then later restored, 
these objects can be used again as if the modulus had never changed.  
Note, however, that if a GF2E object is created under one modulus 
and then used in any way (except destroyed) under another, 
program behavior is not predictable.  This condition is not
explicitly checked for, but an error is likely to be raised.
One should also not presume that things will work properly
if the modulus is changed, but its value happens to be the same---
one should restore the same "context", from either a GF2EBak
or a GF2EContext object.  This is anyway more efficient.

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




class GF2EBak {
public:

   // To describe this logic, think of a GF2EBak object
   // of having two components: a modulus Q (possibly "null") and 
   // an "auto-restore bit" b.

   // There is also a global current modulus P (initially "null").

   GF2EBak();  // Q = "null", b = 0

   ~GF2EBak();  // if (b) P = Q

   void save();  // Q = P, b = 1 
   void restore();  // P = Q, b = 0


private:
   GF2EBak(const GF2EBak&);  // copy disabled
   void operator=(const GF2EBak&);  // assignment disabled
};


// more general context switching:

class GF2EContext {

// A GF2EContext object has a modulus Q (possibly "null"),
// but has no auto-restore bit like a GF2EBak object.
// However, these objects can be initialized and copied with
// complete generality.

// As above, P is the current global modulus (initially "null")

public:

GF2EContext(); // Q = "null"
GF2EContext(const GF2X& new_Q); // Q = new_Q

void save(); // Q = P
void restore() const; // P = Q

GF2EContext(const GF2EContext&);  // copy
GF2EContext& operator=(const GF2EContext&); // assignment
~GF2EContext(); // destructor


};


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

                               Miscellany

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

void clear(GF2E& x); // x = 0
void set(GF2E& x); // x = 1

static const GF2E& GF2E::zero();
// GF2E::zero() yields a read-only reference to zero

static long GF2X::WordLength();
// GF2E::size() returns # of words needed to store a polynomial of
// degree < GF2E::degree()

void swap(GF2E& x, GF2E& y);
// swap x and y (done by "pointer swapping", if possible).

static ZZ& GF2E::cardinality();
// yields the cardinality, i.e., 2^{GF2E::degree()}