gf2x.txt

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

GF2X InvMod(const GF2X& a, const GF2X& f);
// x = a^{-1} % f, error is a is not invertible

long InvModStatus(GF2X& x, const GF2X& a, const GF2X& f);
// if (a, f) = 1, returns 0 and sets x = a^{-1} % f; otherwise,
// returns 1 and sets x = (a, f)


// for modular exponentiation, see below



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

                     Modular Arithmetic with Pre-Conditioning

If you need to do a lot of arithmetic modulo a fixed f, build
GF2XModulus F for f.  This pre-computes information about f that
speeds up subsequent computations.

As an example, the following routine computes the product modulo f of a vector
of polynomials.

#include <NTL/GF2X.h>

void product(GF2X& x, const vec_GF2X& v, const GF2X& f)
{
   GF2XModulus F(f);
   GF2X res;
   res = 1;
   long i;
   for (i = 0; i < v.length(); i++)
      MulMod(res, res, v[i], F); 
   x = res;
}


Note that automatic conversions are provided so that a GF2X can
be used wherever a GF2XModulus is required, and a GF2XModulus
can be used wherever a GF2X is required.

The GF2XModulus routines optimize several important special cases:

  - f = X^n + X^k + 1, where k <= min((n+1)/2, n-NTL_BITS_PER_LONG)

  - f = X^n + X^{k_3} + X^{k_2} + X^{k_1} + 1,
      where k_3 <= min((n+1)/2, n-NTL_BITS_PER_LONG)

  - f = X^n + g, where deg(g) is small


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

class GF2XModulus {
public:
   GF2XModulus(); // initially in an unusable state
   ~GF2XModulus();

   GF2XModulus(const GF2XModulus&);  // copy

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

   GF2XModulus(const GF2X& f); // initialize with f, deg(f) > 0

   operator const GF2X& () const; 
   // read-only access to f, implicit conversion operator

   const GF2X& val() const; 
   // read-only access to f, explicit notation

   long WordLength() const;
   // returns word-length of resisues
};

void build(GF2XModulus& F, const GF2X& f);
// pre-computes information about f and stores it in F; deg(f) > 0.
// Note that the declaration GF2XModulus F(f) is equivalent to
// GF2XModulus F; build(F, f).

// In the following, f refers to the polynomial f supplied to the
// build routine, and n = deg(f).

long deg(const GF2XModulus& F);  // return deg(f)

void MulMod(GF2X& x, const GF2X& a, const GF2X& b, const GF2XModulus& F);
GF2X MulMod(const GF2X& a, const GF2X& b, const GF2XModulus& F);
// x = (a * b) % f; deg(a), deg(b) < n

void SqrMod(GF2X& x, const GF2X& a, const GF2XModulus& F);
GF2X SqrMod(const GF2X& a, const GF2XModulus& F);
// x = a^2 % f; deg(a) < n

void MulByXMod(GF2X& x, const GF2X& a, const GF2XModulus& F);
GF2X MulByXMod(const GF2X& a, const GF2XModulus& F);
// x = (a * X) mod F

void PowerMod(GF2X& x, const GF2X& a, const ZZ& e, const GF2XModulus& F);
GF2X PowerMod(const GF2X& a, const ZZ& e, const GF2XModulus& F);

void PowerMod(GF2X& x, const GF2X& a, long e, const GF2XModulus& F);
GF2X PowerMod(const GF2X& a, long e, const GF2XModulus& F);

// x = a^e % f; deg(a) < n (e may be negative)

void PowerXMod(GF2X& x, const ZZ& e, const GF2XModulus& F);
GF2X PowerXMod(const ZZ& e, const GF2XModulus& F);

void PowerXMod(GF2X& x, long e, const GF2XModulus& F);
GF2X PowerXMod(long e, const GF2XModulus& F);

// x = X^e % f (e may be negative)


void rem(GF2X& x, const GF2X& a, const GF2XModulus& F);
// x = a % f

void DivRem(GF2X& q, GF2X& r, const GF2X& a, const GF2XModulus& F);
// q = a/f, r = a%f

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

// operator notation:

GF2X operator/(const GF2X& a, const GF2XModulus& F);
GF2X operator%(const GF2X& a, const GF2XModulus& F);

GF2X& operator/=(GF2X& x, const GF2XModulus& F);
GF2X& operator%=(GF2X& x, const GF2XModulus& F);


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

                             vectors of GF2X's

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

NTL_vector_decl(GF2X,vec_GF2X)
// vec_GF2X

NTL_eq_vector_decl(GF2X,vec_GF2X)
// == and !=

NTL_io_vector_decl(GF2X,vec_GF2X)
// I/O operators


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

                              Modular Composition

Modular composition is the problem of computing g(h) mod f for
polynomials f, g, and h.

The algorithm employed is that of Brent & Kung (Fast algorithms for
manipulating formal power series, JACM 25:581-595, 1978), which uses
O(n^{1/2}) modular polynomial multiplications, and O(n^2) scalar
operations.



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

void CompMod(GF2X& x, const GF2X& g, const GF2X& h, const GF2XModulus& F);
GF2X CompMod(const GF2X& g, const GF2X& h, const GF2XModulus& F);
// x = g(h) mod f; deg(h) < n

void Comp2Mod(GF2X& x1, GF2X& x2, const GF2X& g1, const GF2X& g2,
              const GF2X& h, const GF2XModulus& F);
// xi = gi(h) mod f (i=1,2), deg(h) < n.

void CompMod3(GF2X& x1, GF2X& x2, GF2X& x3, 
              const GF2X& g1, const GF2X& g2, const GF2X& g3,
              const GF2X& h, const GF2XModulus& F);
// xi = gi(h) mod f (i=1..3), deg(h) < n


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

                     Composition with Pre-Conditioning

If a single h is going to be used with many g's then you should build
a GF2XArgument for h, and then use the compose routine below.  The
routine build computes and stores h, h^2, ..., h^m mod f.  After this
pre-computation, composing a polynomial of degree roughly n with h
takes n/m multiplies mod f, plus n^2 scalar multiplies.  Thus,
increasing m increases the space requirement and the pre-computation
time, but reduces the composition time.

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


struct GF2XArgument {
   vec_GF2X H;
};

void build(GF2XArgument& H, const GF2X& h, const GF2XModulus& F, long m);
// Pre-Computes information about h.  m > 0, deg(h) < n

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

GF2X CompMod(const GF2X& g, const GF2XArgument& H, 
             const GF2XModulus& F);


extern long GF2XArgBound;

// Initially 0.  If this is set to a value greater than zero, then
// composition routines will allocate a table of no than about
// GF2XArgBound KB.  Setting this value affects all compose routines
// and the power projection and minimal polynomial routines below, 
// and indirectly affects many routines in GF2XFactoring.

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

                     Power Projection routines

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

void project(GF2& x, const vec_GF2& a, const GF2X& b);
GF2 project(const vec_GF2& a, const GF2X& b);
// x = inner product of a with coefficient vector of b


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

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

// Computes the vector 

//   (project(a, 1), project(a, h), ..., project(a, h^{k-1} % f).  

// Restriction: must have a.length <= deg(F) and deg(h) < deg(F).
// This operation is really the "transpose" of the modular composition 
// operation.

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

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

// same as above, but uses a pre-computed GF2XArgument


// lower-level routines for transposed modular multiplication:

class GF2XTransMultiplier { /* ... */ };

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

// build a GF2XTransMultiplier to use in the following routine:

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

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

// Computes the vector

//   project(a, b), project(a, (b*X)%f), ..., project(a, (b*X^{n-1})%f)

// Restriction: must have a.length() <= deg(F) and deg(b) < deg(F).
// This is really the transpose of modular multiplication.
// Input may have "high order" zeroes stripped.
// Output always has high order zeroes stripped.


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

                              Minimum Polynomials

All of these routines implement the algorithm from [Shoup, J. Symbolic
Comp. 17:371-391, 1994] and [Shoup, J. Symbolic Comp. 20:363-397,
1995], based on transposed modular composition and the
Berlekamp/Massey algorithm.

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


void MinPolySeq(GF2X& h, const vec_GF2& a, long m);
// computes the minimum polynomial of a linealy generated sequence; m
// is a bound on the degree of the polynomial; required: a.length() >=
// 2*m

void ProbMinPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F, long m);
GF2X ProbMinPolyMod(const GF2X& g, const GF2XModulus& F, long m);

void ProbMinPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F);
GF2X ProbMinPolyMod(const GF2X& g, const GF2XModulus& F);

// computes the monic minimal polynomial if (g mod f).  m = a bound on
// the degree of the minimal polynomial; in the second version, this
// argument defaults to n.  The algorithm is probabilistic; it always
// returns a divisor of the minimal polynomial, possibly a proper divisor.

void MinPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F, long m);
GF2X MinPolyMod(const GF2X& g, const GF2XModulus& F, long m);

void MinPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F);
GF2X MinPolyMod(const GF2X& g, const GF2XModulus& F);

// same as above, but guarantees that result is correct

void IrredPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F, long m);
GF2X IrredPolyMod(const GF2X& g, const GF2XModulus& F, long m);

void IrredPolyMod(GF2X& h, const GF2X& g, const GF2XModulus& F);
GF2X IrredPolyMod(const GF2X& g, const GF2XModulus& F);

// same as above, but assumes that F is irreducible, or at least that
// the minimal poly of g is itself irreducible.  The algorithm is
// deterministic (and is always correct).


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

                                Traces

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


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

void TraceMod(GF2& x, const GF2X& a, const GF2X& f);
GF2 TraceMod(const GF2X& a, const GF2X& f);
// x = Trace(a mod f); deg(a) < deg(f)


void TraceVec(vec_GF2& S, const GF2X& f);
vec_GF2 TraceVec(const GF2X& f);
// S[i] = Trace(X^i mod f), i = 0..deg(f)-1; 0 < deg(f)

// The above routines implement the asymptotically fast trace
// algorithm from [von zur Gathen and Shoup, Computational Complexity,
// 1992].


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

                           Miscellany

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


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

void GF2X::normalize();  
// f.normalize() strips leading zeros from f.rep.

void GF2X::SetMaxLength(long n);
// f.SetMaxLength(n) pre-allocate spaces for n coefficients.  The
// polynomial that f represents is unchanged.

void GF2X::kill();
// f.kill() sets f to 0 and frees all memory held by f.  Equivalent to
// f.rep.kill().

GF2X::GF2X(INIT_SIZE_TYPE, long n);
// GF2X(INIT_SIZE, n) initializes to zero, but space is pre-allocated
// for n coefficients

static const GF2X& zero();
// GF2X::zero() is a read-only reference to 0

void swap(GF2X& x, GF2X& y); 
// swap x and y (via "pointer swapping")